为什么在hashCode中使用素数？

Question

为什么在hashCode中使用素数？我只是想知道为什么素数在一个类的hashCode()方法？例如，当使用Eclipse生成hashCode()方法总是存在素数。31使用：public int hashCode() {      final int prime = 31;      //...}参考资料：下面是关于Hashcode的一个很好的入门文章和关于我发现的散列是如何工作的文章(C#，但概念是可转移的)：Eric Lippert的GetHashCode()指南和规则

Answer 1

选择素数是为了在散列桶中最好地分配数据。如果输入的分布是随机且分布均匀的，那么哈希码/模的选择就无关紧要了。只有当输入有某种模式时，它才会产生影响。

在处理内存位置时，通常是这样的。例如，所有32位整数都与可被4整除的地址对齐。请查看下表，以可视化使用素数与非素数模数的效果：

Input       Modulo 8    Modulo 7

0           0           0

4           4           4

8           0           1

12          4           5

16          0           2

20          4           6

24          0           3

28          4           0

注意，当使用素数模和非素数模时，几乎完全分布。

然而，虽然上面的例子大部分是人为的，但一般的原则是，当处理输入模式，使用素数模数将得到最佳分布。

Answer 2

不管值多少钱，有效Java第二版放弃数学问题，只说选择31的原因是：

• 因为它是一个奇怪的素数，使用素数是“传统的”
• 它也比2的幂小一倍，这允许按位优化

以下是全文的引文第9项：始终覆盖hashCode当你覆盖equals:

之所以选择31值，是因为它是一个奇数素数。如果它是偶数，乘法溢出，信息就会丢失，因为乘2等于移动。使用质数的优点不太清楚，但它是传统的。

31的一个很好的性质是乘法可以被移位(第15.19节)和减法以获得更好的性能：

 31 * i == (i << 5) - i

现代VM自动进行这种优化。

---

虽然本项中的配方产生了相当好的哈希函数，但它不产生最先进的哈希函数，Java平台库也没有在版本1.6时提供此类哈希函数。编写这样的散列函数是一个研究主题，最好留给数学家和理论计算机科学家。

也许该平台的稍后版本将为其类和实用方法提供最先进的哈希函数，从而使普通程序员能够构造此类哈希函数。同时，本项所述的技术应足以适用于大多数应用程序。

简单地说，可以说，使用具有众多除数的乘数会产生更多的结果。散列碰撞..因为为了有效地散列，我们想要最小化碰撞的次数，所以我们尝试使用一个乘法器，它有较少的除数。根据定义，素数有两个截然不同的正因子。

相关问题

• 来自一个字段的Java hashCode

  -菜谱，加上使用ApacheCommonsLang的构建器的示例

• 将对象的哈希码定义为所有类变量哈希码的和、乘法、或其他值是否不正确？

• 绝对初学者的比特转移指南？