18

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

有人可以对此有所了解吗？评论告诉我们为什么这段代码在这里，但我想了解这如何改善不良哈希值以及它如何保证位置具有有限数量的冲突。这些神奇的数字是什么意思？

4

1 回答 1

22

为了使它有意义，它必须与对 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 的不同数字的数量现在显着有界，因为二进制表示中任何地方出现的任何差异都被压缩到对分桶重要的位中。

于 2011-10-27T20:50:46.140 回答