HashMap和TreeMap有什么区别？

Question

我开始学习Java。在什么情况下我会使用HashMap而不是TreeMap？

- kkdas02

---

StackOverflow不仅为问题提出者提供帮助，也为其他寻求答案的人提供了便利。所以，如果我在这里找到一个答案，而这个答案也存在于我没有的某本书中，那么这完全没关系。 - Konrad Höffner

Answer 1

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

HashMap 则没有此类保证。因此，在遍历 HashMap 键时，无法确定它们的顺序。

HashMap 通常情况下更高效，所以只要不关心键的顺序，就应该使用它。

- TM.

---

HashMap 更加时间高效。TreeMap 更加空间高效。 - erickson

TreeMap仅适用于可比较的对象，HashMap仅适用于具有合适的hashCode()实现的对象。 - Thilo

@erickson：您能否发布一个支持这个说法的参考链接吗？ - Adriano

"TreeMap" 的搜索复杂度为 O(log(N))，而带有良好 hashCode() 方法的 "HashMap" 的复杂度为 O(1)。 - benweet

HashMap允许空键和空值（只允许一个空键）。如果TreeMap使用自然排序或其比较器，则不允许空键，将抛出异常。 - madhu_karnati

Answer 2

HashMap 是使用哈希表实现的，而 TreeMap 是使用红黑树实现的。实际上，HashMap 和 TreeMap 的主要区别反映了哈希和二叉树之间的主要区别，也就是在迭代时，TreeMap 保证可以按照键的顺序进行遍历，这个顺序由元素的 compareTo() 方法或者 TreeMap 构造函数中设置的比较器决定。

请查看下面的图表。

- pierrotlefou

---

这是否意味着在TreeMap中随机获取比HashMap更快？ - ucMedia

Answer 3

总结：

• HashMap：查找数组结构，基于hashCode()和equals()的实现，插入和查找时间复杂度为O(1)，未排序
• TreeMap：树形结构，基于compareTo()的实现，插入和查找时间复杂度为O(log(N))，已排序

引用自：HashMap vs. TreeMap

- Sirius

---

HashMap的复杂度为O(1+a)。取决于hashCode函数，“a”在最坏情况下可能达到“n”。 - 30thh

Answer 4

通常情况下使用HashMap，但在需要键按顺序排序时（需要迭代键时）可以使用TreeMap。

- nanda

---

有没有现实世界的例子，其中键是否排序很重要？ - triplej

Answer 5

我将讲解Java中的HashMap和TreeMap的实现：

• HashMap -- 实现基本的映射接口

  1. 由存储条目的链表组成的桶数组实现
  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. 提供有序的迭代。higherKey()，lowerKey()可用于获取给定键的后继和前驱。

综上，HashMap和TreeMap之间最大的区别在于TreeMap实现了NavigableMap<K,V>，提供了有序迭代的功能。除此之外，HashMap和TreeMap都是Java Collection框架的成员。您可以查看Java的源代码以了解更多它们的实现细节。

- user2060386

Answer 6

你几乎总是使用HashMap，只有当你需要按特定顺序排列键时才应该使用TreeMap。

- Jorn

Answer 7

HashMap 用于快速查找，而 TreeMap 用于对 map 进行排序迭代。

- fastcodejava

Answer 8

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

- Dhwanit

---

如果您真的想要这个，可以为映射制作一个装饰器，在涉及键输入的所有内容中，将其全部转换为大写/小写，并委托给装饰后的映射。通过这样做，拥有“不区分大小写”的哈希表并不那么困难。无论如何，这个答案可能有点题外话：您只谈到了treemap的一个非常特定的用例，我不认为它作为hashmap/treemap之间的比较有多大意义。 - Adrian Shum