Java的HashMap冲突解决方法

Question

根据我在stackoverflow和其他网站上的阅读，Java使用链表来解决哈希冲突。

这将确保在插入、获取和删除的最坏情况下，复杂度为O(n)。

为什么Java不使用自平衡二叉搜索树（如AVL、红黑树等）来保证在插入、获取和删除的最坏情况下，复杂度为O(log n)呢？

- Amir Omidi

---

惊喜：Java 8在处理哈希冲突时使用了平衡树：http://javarevisited.blogspot.sg/2016/01/how-does-java-hashmap-or-linkedhahsmap-handles.html?m=1 - Tim Biegeleisen

主要原因是HashMap不需要其元素类型为Comparable。但是新的Java 8实现将在运行时检查元素是否可比较，并在可比较时使用平衡树。这很棘手（仅因为一个元素针对其自身类型是可比较的，并不意味着它针对HashMap中所有其他键类型都是可比较的）-可能这就是为什么早些时候没有这样做的原因。 - Erwin Bolwidt

Answer 1

当链表中的元素数量足够大时，Java 8确实使用链表。

但对于少量元素来说，链表会增加显著的内存和性能开销。对于非常少量的元素，链表的效率非常高，在99％的情况下，这些元素正是哈希桶所期望的。此外，确定如何排序二叉树并不明显，必须对Comparable的元素进行特殊处理，通过未使用的哈希码位进行排序...这变得复杂起来。

- Louis Wasserman

---

哦，哇，我没有想得那么深。谢谢，现在完全明白了！ - Amir Omidi

Answer 2

大部分情况下，桶(bucket)中只会有非常少的元素；通常是零个或一个。在这些情况下，一个简单的哈希桶(hash bucket)结构能够保证O(1)；使用O(log n)的二叉搜索树(BST)虽然在一些次优边缘情况下可能会节省时间，但性能提升微乎其微，甚至会变差。同时还会产生显著的内存开销。Java 8确实尽力检测到链表不再是最佳选择并转换为BST；但如果这种行为频繁发生，则表示哈希和HashMap被错误地使用了。

阅读JDK源代码时可以了解到许多实现细节。以下是从Oracle的java.util.HashMap顶部摘录的简要内容：

/*
 * Implementation notes.
 *
 * This map usually acts as a binned (bucketed) hash table, but
 * when bins get too large, they are transformed into bins of
 * TreeNodes, each structured similarly to those in
 * java.util.TreeMap. Most methods try to use normal bins, but
 * relay to TreeNode methods when applicable (simply by checking
 * instanceof a node).  Bins of TreeNodes may be traversed and
 * used like any others, but additionally support faster lookup
 * when overpopulated. However, since the vast majority of bins in
 * normal use are not overpopulated, checking for existence of
 * tree bins may be delayed in the course of table methods.
 * [...]

看一下HashMap#getNode和HashMap.Node的实现，我们可以看到每个桶最初都是一个非常简单的链表——比java.util.LinkedList还要简单，它实际上是一个双向链表。

根据注释，当一个列表增长到一定大小时，它会被转换成一棵树。很难准确地说出HashMap.TreeNode中发生了什么，因为代码不是很自我描述，但它似乎是一个简单的红黑树。

- Zenexer

---

谢谢！我想我看的是Java 7及更早版本的评论。 :) - Amir Omidi