当许多键具有相同的哈希码时，Java 8的HashMap如何退化为平衡树？

Question

当许多键具有相同的哈希码时，Java 8的HashMap如何退化为平衡树？我读到说键应该实现Comparable来定义排序。 HashMap如何结合哈希和自然排序来实现树？对于不实现Comparable的类，或者当多个非相互可比较的Comparable实现是映射中的键时怎么办？

- Thennam

Answer 1

HashMap的实现说明注释比我自己写的更好地描述了HashMap的操作。了解树节点及其顺序的相关部分如下：

该映射通常作为一个箱式散列表，但当箱子太大时，它们会转换成TreeNodes的箱子，每个TreeNodes的结构与java.util.TreeMap中的类似。[...] TreeNodes的箱子可以像其他箱子一样遍历和使用，但在过度填充时还支持更快的查找。 [...]

树形箱（即元素全部为TreeNodes的箱）首先按hashCode排序，但在出现冲突的情况下，如果两个元素属于相同的“C implements Comparable”类型，则使用它们的compareTo方法进行排序。（我们通过反射谨慎地检查泛型类型以验证这一点--请参见方法comparableClassFor）。树箱的增加复杂性值得提供最坏情况下O(log n)操作，当键具有不同的哈希或可排序时。因此，在hashCode()方法返回分布较差的值或许多键共享hashCode的情况下，性能会逐渐降低，只要它们也是可比较的。（如果这两种情况都不适用，则与不采取预防措施相比，我们可能会浪费大约两倍的时间和空间。但已知的唯一情况是由于糟糕的用户编程实践导致的，其已经如此缓慢，以至于这几乎没有任何区别。）

当两个对象具有相等的哈希码但不可相互比较时，将调用方法tieBreakOrder来打破平局。首先通过对getClass().getName()进行字符串比较，然后通过比较System.identityHashCode来解决。

实际的树构建始于treeifyBin，当桶达到TREEIFY_THRESHOLD (目前为8)时开始，假设哈希表的容量至少为MIN_TREEIFY_CAPACITY(目前为64)。这是一个基本上正常的红黑树实现(向CLR致谢),但有一些复杂的部分来支持以与哈希桶相同的方式进行遍历(例如，removeTreeNode)。

- Jeffrey Bosboom

---

但是如果对象中没有重写hashcode()，那么它仍然会调用System.identityHashCode()来查找哈希桶。那么如果键没有重写hashcode()并且调用了tieBreakOrder会发生什么？或者它会被调用吗？ - Rohit Sachan

@RohitSachan 如果键类型使用默认的身份语义，那么任何桶都很难变得足够满以转换为树形桶，因为身份哈希码是良好分布的。但是对于这种情况没有特殊处理，所以是的，tieBreakOrder 仍然会调用 identityHashCode 进行排序。 - Jeffrey Bosboom

@Rohit Sachan：如果每次优化尝试都失败了，它就必须采用与Java 8之前版本相同的链表行为。 - Holger

@NateGlenn find 在非可比较情况下似乎会双向查找（最后的 else-if 和 else），但我需要通过调试器来确认。这就引出了一个问题，为什么在这种情况下需要排序呢？ - Jeffrey Bosboom

@NateGlenn 推测：String 是最常见的JDK控制类型。每多检查一个类，在特殊情况下所获得的好处就越少，而在一般情况下成本则会增加，也许只有String是最佳的折衷方案。请注意，String是final的，因此不是用于子类防御。这可能是为了防止基于哈希碰撞的DoS攻击；String的hashCode并不总是最优的。曾经有一个巨大的字符串列表散列为MIN_VALUE，其中包括“polygenelubricants”。我想其他值的碰撞也是可能的。 - Jeffrey Bosboom

Answer 2

阅读代码。它主要是一个红黑树。

实际上，它并不需要实现Comparable，但如果可用的话可以使用它（例如参见find方法）。

- Frédéric Dumont

Answer 3

HashMap有它自己的哈希方法，它对内部对象应用了一个补充的 2 位长度哈希以避免出现问题：

对给定的哈希码应用补充哈希函数，这可以防止低质量哈希函数的影响。这是至关重要的，因为HashMap使用二次幂长度哈希表，否则会出现哈希码在较低位不同的碰撞。注意：空键始终映射到哈希值0，因此索引0。

如果您想查看实现过程，请查看HashMap类源代码。

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

- Jordi Castilla

---

实际上并不是这样的。hash 函数可以减少但不能消除冲突，所以 HashMap 仍然需要处理具有相同哈希值的键。 - Frédéric Dumont

你链接的是旧版本的源代码。查看Java 8代码，你会发现它不再进行补充重新哈希。那个方法已经不存在了。 - Stephen C

静态最终整数哈希（Object key）-它存在。（JDK 16） - skyho