Java HashMap 实现中的 hash（）方法的诀窍是什么？

hashmap java hash

2022-09-02 22:17:31

可能的副本：
理解奇怪的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

答案 1

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

此实现只是许多可能功能中的一个令人满意的选项。

答案 2

此功能有助于更好地避免中的冲突。HashMap

如果你有良好的实现，你仍然可能会因为检测对象的桶而发生冲突。hashCodehashCode % size

例：

假设您的大小为。HashMap20

您计算了 for 并得到。存储桶是。hashCode()object1401401 % 20 = 1
您计算了 for 并得到。存储桶是hashCode()object236013601 % 20 = 1
您计算了 for 并得到。存储桶是。hashCode()object316011601 % 20 = 1

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

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

hash = 395,bucket = 395 % 20 = 15
hash = 3820,bucket = 3820 % 20 = 0
hash = 1577,bucket = 1577 % 20 = 17

显然，作为附加步骤应用，我们得到了三个不同的存储桶，这些存储桶保留了对对象的恒定时间访问。hash

Java HashMap 实现中的 hash（） 方法的诀窍是什么？

Java HashMap 实现中的 hash（）方法的诀窍是什么？