OpenJDK的重组机制

Question

在搜索HashMap实现后,在http://www.docjar.com/html/api/java/util/HashMap.java.html上找到此代码.

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

有人可以对此有所了解吗？评论告诉我们为什么这个代码在这里,但我想了解这是如何改善错误的哈希值以及它如何保证位置具有有限的碰撞数量.这些神奇数字意味着什么？

Answer 1

为了使它具有任何意义,它必须与对HashMap如何将内容分配到存储桶的理解相结合.这是一个简单的函数,通过它选择一个桶索引:

static int indexFor(int h, int length) {
    return h & (length-1);
}

所以你可以看到,默认表大小为16时,只有哈希的4个最低有效位实际上对分配桶很重要!(16 - 1 = 15,用1111b掩盖哈希值)

如果你的hashCode函数返回,这显然是坏消息:

10101100110101010101111010111111

01111100010111011001111010111111

11000000010100000001111010111111
//etc etc etc

这样的哈希函数不会以其作者可见的任何方式"坏".但是,如果你将它与地图分配桶的方式结合起来,繁荣,MapFail(tm).

如果你记住h是32位数字,那些根本就不是幻数.它系统地将数字中最重要的位向右扫描到最低有效位.其目的是使得当以二进制查看时在"跨越"它的任何地方出现的数量的"差异"在最低有效位中变得可见.

碰撞变得有限,因为具有相同相关LSB的不同数字的数量现在显着受限,因为在二进制表示中的任何地方发生的任何差异被压缩到对于桶的重要的位中.