Java HashMap实现中hash()方法的技巧是什么？

Question

可能重复:
了解奇怪的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);   
} 

我不太了解这种实现的算法原理.我可以参考的任何解释或任何资源？谢谢 !

UPDATE

谢谢大家的答案和资源.实际上我理解哈希是如何工作的,但不是知道这个代码将如何确保a bounded number of collisions,正如评论所说.有理论上的验证吗？

Answer 1

主要目标是为类似的输入参数生成非常不同的值,并最大限度地减少冲突次数. http://en.wikipedia.org/wiki/Hash_function

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

Answer 2

此功能有助于更好地避免碰撞HashMap.

如果你有很好的hashCode实现,你仍然可以因为你需要hashCode % size检测对象的存储桶而发生冲突.

例:

假设,你的尺寸HashMap就是20.

1. 你计算了hashCode()for object1和get 401.斗是401 % 20 = 1.
2. 你计算了hashCode()for object2和get 3601.斗是3601 % 20 = 1
3. 你计算了hashCode()for object3和get 1601.斗是1601 % 20 = 1.

因此,即使您有三个不同的hashCodes,您也​​可以为所有三个对象获得一个存储桶,这意味着您的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作为额外步骤应用我们得到三个不同的桶,保持对对象的恒定时间访问.