Java HashMap 和 TreeMap 有什么区别？

What is the difference between a HashMap and a TreeMap?

提问by kkdas02

I started learning Java. When would I use a HashMap over a TreeMap?

我开始学习Java。我什么时候会在 TreeMap 上使用 HashMap？

采纳答案by TM.

TreeMapis an example of a SortedMap, which means that the order of the keys can be sorted, and when iterating over the keys, you can expect that they will be in order.

TreeMap是 a 的一个例子SortedMap，这意味着可以对键的顺序进行排序，并且在迭代键时，您可以期望它们是有序的。

HashMapon the other hand, makes no such guarantee. Therefore, when iterating over the keys of a HashMap, you can't be sure what order they will be in.

HashMap另一方面，不做这样的保证。因此，在迭代 a 的键时HashMap，您无法确定它们的顺序。

HashMapwill be more efficient in general, so use it whenever you don't care about the order of the keys.

HashMap一般来说会更有效率，所以只要你不关心键的顺序就可以使用它。

回答by nanda

Use HashMapmost of the times but use TreeMapwhen you need the key to be sorted (when you need to iterate the keys).

用HashMap大部分的时间，但使用TreeMap时需要重点进行排序（当你需要遍历键）。

回答by Jorn

You almost always use HashMap, you should only use TreeMapif you need your keys to be in a specific order.

您几乎总是使用HashMap，只有TreeMap在需要按特定顺序排列密钥时才应该使用。

回答by fastcodejava

HashMapis used for fast lookup, whereas TreeMapis used for sorted iterations over the map.

HashMap用于快速查找，而TreeMap用于地图上的排序迭代。

回答by Sirius

To sum up:

总结：

• HashMap: Lookup-array structure, based on hashCode(), equals() implementations, O(1) runtime complexity for inserting and searching, unsorted
• TreeMap: Tree structure, based on compareTo() implementation, O(log(N)) runtime complexity for inserting and searching, sorted

• HashMap：Lookup-array 结构，基于 hashCode()、equals() 实现，O(1) 的插入和搜索运行时复杂度，未排序
• TreeMap：树结构，基于compareTo()实现，O(log(N)) 运行时复杂度插入和搜索，排序

Taken from: HashMap vs. TreeMap

摘自：HashMap 与 TreeMap

回答by Dhwanit

Along with sorted key store one another difference is with TreeMap, developer can give (String.CASE_INSENSITIVE_ORDER) with String keys, so then the comparator ignores case of key while performing comparison of keys on map access. This is not possible to give such option with HashMap - it is always case sensitive comparisons in HashMap.

与排序键存储的另一个区别是与 TreeMap 不同的是，开发人员可以给 (String.CASE_INSENSITIVE_ORDER) 和 String 键，这样比较器在映射访问时执行键比较时会忽略键的大小写。使用 HashMap 不可能提供这样的选项 - 在 HashMap 中的比较总是区分大小写。

回答by user2060386

I'll talk about the HashMapand TreeMapimplementation in Java:

我将谈谈Java中的HashMap和TreeMap实现：

• HashMap -- implement basic map interface

  1. implemented by an array of buckets, each bucket is a LinkedList of entries
  2. running time of basic operations: put(), average O(1), worst case O(n), happens when the table is resized; get(), remove(), average O(1)
  3. not synchronized, to synchronize it: Map m = Collections.synchronizedMap(new HashMap(...));
  4. Iteration order of the map is unpredictable.

• TreeMap -- implement navigable map interface

  1. implemented by a red-black tree
  2. running time of basic operations: put(), get(), remove(), worst case O(lgn)
  3. not synchronized, to synchronize it: SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
  4. provide ordered iteration. higherKey(), lowerKey() can be used to get the successor and predecessor of a given key.

• HashMap -- 实现基本的地图接口

  1. 由一个bucket数组实现，每个bucket是一个条目的LinkedList
  2. 基本操作的运行时间：put()，平均 O(1)，最坏情况 O(n)，在调整表大小时发生；get(), remove(), 平均 O(1)
  3. 不同步，同步它： Map m = Collections.synchronizedMap(new HashMap(...));
  4. 地图的迭代顺序是不可预测的。

• TreeMap -- 实现可导航的地图接口

  1. 由红黑树实现
  2. 基本操作的运行时间：put()、get()、remove()，最坏情况 O(lgn)
  3. 不同步，同步它： SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
  4. 提供有序迭代。highKey()、lowerKey() 可用于获取给定键的后继和前驱。

To sum, the biggest difference between HashMap and TreeMap is that TreeMap implements NavigableMap<K,V>, which provide the feature of ordered iteration. Besides, both HashMap and TreeMap are members of Java Collection framework. You can investigate the source code of Javato know more about their implementations.

综上所述，HashMap 和 TreeMap 最大的区别在于 TreeMap 实现了NavigableMap<K,V>，提供了有序迭代的特性。此外，HashMap 和 TreeMap 都是 Java Collection 框架的成员。您可以调查Java的源代码以了解有关其实现的更多信息。

回答by pierrotlefou

HashMapis implemented by Hash Table while TreeMapis implemented by Red-Black tree. The main difference between HashMapand TreeMapactually reflect the main difference between a Hashand a Binary Tree, that is, when iterating, TreeMap guarantee can the key order which is determined by either element's compareTo() method or a comparator set in the TreeMap's constructor.

HashMap由 Hash TableTreeMap实现，而由Red-Black tree. 之间的主要区别HashMap和TreeMap实际反映的主要区别Hash和一个Binary Tree，即，当迭代，TreeMap的保证可以键顺序由或元素的的compareTo（）方法或在树形图的构造的比较器组来确定。

Take a look at following diagram.

看看下图。