18

可能重复：
理解奇怪的 Java 哈希函数 

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);   
}

我不太明白这个实现的算法原理。我可以参考任何解释或任何资源？谢谢 ！

更新

感谢所有人的答案和资源。实际上，我了解哈希的工作原理，但不知道为什么此代码将确保a bounded number of collisions，如评论所述。有没有理论上的验证？

4

3 回答 3

5

此功能只是有助于更好地避免HashMap.

如果你有很好的hashCode实现，你仍然会因为你hashCode % size检测对象的桶而发生碰撞。

例子：

假设，你的大小HashMap是20。

  1. 您计算了hashCode()forobject1和 get 401。桶是401 % 20 = 1.
  2. 您计算了hashCode()forobject2和 get 3601。桶是3601 % 20 = 1
  3. 您计算了hashCode()forobject3和 get 1601。桶是1601 % 20 = 1.

因此，即使您有三个不同的 hashCode，您也会为所有三个对象获得一个桶，这意味着您的 HashMap 的复杂性O(n)而不是O(1).

如果我们将函数hash应用于所有获得的哈希码，我们得到

  1. hash = 395,bucket = 395 % 20 = 15
  2. hash = 3820,bucket = 3820 % 20 = 0
  3. hash = 1577,bucket = 1577 % 20 = 17

很明显，hash作为附加步骤，我们得到了三个不同的存储桶，它们可以保持对对象的恒定时间访问。

于 2012-11-19T10:51:34.593 回答
5

主要目标是为相似的输入参数生成非常不同的值并最小化碰撞次数。 http://en.wikipedia.org/wiki/Hash_function

这种实现只是许多可能功能中令人满意的一种选择。

于 2012-11-19T10:07:52.347 回答
3

>>> 运算符是位移位，但被视为无符号。

^ 是 XOR（异或）

所以这条线

h ^= (h >>> 20) ^ (h >>> 12);

表示 xor 原始与 h 位移 20 位， XOR 与 h 位移 12 位

然后

h ^ (h >>> 7) ^ (h >>> 4);

上面的 h，xor h 移位 7 位，xor h 移位 4 位。我不是 100% 确定它为什么会这样设置

于 2012-11-19T10:18:00.407 回答