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

Question

当许多密钥具有相同的哈希码时,Java 8的HashMap如何退化为平衡树？我读到了键应该实现Comparable来定义一个顺序.HashMap如何结合散列和自然排序来实现树？那些没有实现的类Comparable,或者当多个不可相互比较的Comparable实现是同一个映射中的键时呢？

Answer 1

HashMap中的实现注释注释是对HashMap操作的更好描述,而不是我自己编写的.理解树节点及其排序的相关部分是:

此映射通常充当分箱(分区)哈希表,但是当分箱变得太大时,它们将转换为TreeNodes的分区,每个分区的结构与java.util.TreeMap中的类似.[...] TreeNodes的Bins可以像其他任何一样遍历和使用,但是当人口过多时还支持更快的查找.[...]

树容器(即其元素都是TreeNode的容器)主要由hashCode排序,但在tie的情况下,如果两个元素具有相同的"C类实现可比较"类型,则它们的compareTo方法用于排序.(我们保守地通过反射来检查泛型类型以验证这一点 - 请参阅方法equivalentClassFor).当密钥具有不同的哈希值或可订购时,增加树容器的复杂性值得提供最坏情况的O(log n)操作.因此,在hashCode()方法返回值很差的意外或恶意用法中,性能会优雅地降级分布式,以及许多密钥共享hashCode的那些,只要它们也是可比较的.(如果这些都不适用,与不采取任何预防措施相比,我们可能在时间和空间上浪费大约两倍.但是,唯一已知的案例源于糟糕的用户编程实践,这些实践已经非常缓慢,这几乎没有什么区别.)

当两个对象具有相同的哈希码但不能相互比较时,tieBreakOrder调用方法来打破平局,首先通过getClass().getName()(!)上的字符串比较,然后通过比较System.identityHashCode.

假设哈希表至少具有容量(当前为64)treeifyBin,则实际的树构建从bin到达TREEIFY_THRESHOLD(当前为8)开始MIN_TREEIFY_CAPACITY.这是一个大多数正常的红黑树实现(贷记CLR),并且有一些复杂性来支持遍历,就像哈希箱一样(例如removeTreeNode).

Answer 2

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

将补充哈希函数应用于给定的 hashCode，以防止质量较差的哈希函数。这一点很关键，因为HashMap 使用二次方长度的哈希表，否则会遇到低位相同的 hashCode 的冲突。注意：空键总是映射到散列 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);
}