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

我并不完全理解这个实现的算法原理。是否有任何解释或资源可以参考？谢谢！

更新

感谢大家提供的答案和资源。实际上，我知道哈希是如何工作的，但不知道为什么这段代码会确保有限数量的碰撞，正如注释中所说的那样。是否有任何理论验证？

- l4rmbr

---

https://dev59.com/2Wox5IYBdhLWcg3wOx_9 - xiaofeng.li

原则是a) 伪随机重新排列数字的位数b) 不使用太多CPU c) 同时提供均匀分布。这以一种紧凑的方式通过选择4、7、12、16、19、20、24和27位范围的组合来移动数字。 - Peter Lawrey

这篇文章：- what-hashing-function-does-java-use-to-implement-hashtable-class 可能会对你有所帮助。 - Rohit Jain

Answer 1

主要目标是针对相似的输入参数生成非常不同的值，并尽量减少碰撞的次数。

http://en.wikipedia.org/wiki/Hash_function

这个实现只是许多可能函数中的一种满意的选择。

- Nikolay Kuznetsov

Answer 2

这个函数帮助更好地避免在HashMap中的冲突。即使你有很好的hashCode实现，由于采用了hashCode％size来检测对象的bucket，仍然可能会产生冲突。例如，假设您的HashMap大小为20： 1. 您计算了object1的hashCode()并得到401。Bucket是401％20 = 1。 2. 您计算了object2的hashCode()并得到3601。Bucket是3601％20 = 1。 3. 您计算了object3的hashCode()并得到1601。Bucket是1601％20 = 1。

因此，即使您具有三个不同的hashCodes，您也会获得所有三个对象的一个桶，这意味着您的HashMap的复杂度为O(n)而不是O(1)。如果我们将函数哈希应用于所有获得的哈希码，我们将获得三个不同的bucket，从而保护对对象的恒定时间访问。

- mishadoff

Answer 3

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

^ 表示异或（eXclusive or）

因此该行代码的含义是：

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

这句话的意思是将原始数据按位异或（XOR）20位和12位左移的哈希值进行异或运算。

然后......

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

以上代码中的h，进行异或运算后分别向左移动7位和4位。但我不完全确定为什么要这样设置。

- exussum