OpenJDK的重述机制

hashmap java hash bit-manipulation openjdk

2022-09-02 21:37:29

在搜索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       }

有人能对此有所了解吗？注释告诉我们为什么这个代码在这里，但我想了解这如何改善一个糟糕的哈希值，以及它如何保证位置具有有限的冲突次数。这些神奇的数字是什么意思？

答案 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

这样的哈希函数不太可能以其作者可见的任何方式“坏”。但是，如果您将其与地图分配桶，boom，MapFail（tm）的方式相结合。

如果你记住h是一个32位数字，那么这些根本不是幻数。它系统地将数字中最重要的位向右排成最不重要的位。目的是使以二进制形式查看时“跨”任何地方出现的数字的“差异”在最低有效位上变得可见。

冲突之所以有界，是因为具有相同相关 LSB 的不同数字的数量现在明显有界，因为二进制表示形式中任何位置发生的任何差异都会被压缩到对存储桶很重要的位中。

答案 2