为什么在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 70           0           04           4           48           0           112          4           516          0           220          4           624          0           328          4           0注意，当使用素数模和非素数模时，几乎完全分布。然而，虽然上面的例子大部分是人为的，但一般的原则是，当处理输入模式，使用素数模数将得到最佳分布。

Answer 2

不管值多少钱，有效Java第二版放弃数学问题，只说选择31的原因是：因为它是一个奇怪的素数，使用素数是“传统的”它也比2的幂小一倍，这允许按位优化以下是全文的引文第9项：始终覆盖hashCode当你覆盖equals:之所以选择31值，是因为它是一个奇数素数。如果它是偶数，乘法溢出，信息就会丢失，因为乘2等于移动。使用质数的优点不太清楚，但它是传统的。31的一个很好的性质是乘法可以被移位(第15.19节)和减法以获得更好的性能：&nbsp;31&nbsp;*&nbsp;i&nbsp;==&nbsp;(i&nbsp;<<&nbsp;5)&nbsp;-&nbsp;i现代VM自动进行这种优化。虽然本项中的配方产生了相当好的哈希函数，但它不产生最先进的哈希函数，Java平台库也没有在版本1.6时提供此类哈希函数。编写这样的散列函数是一个研究主题，最好留给数学家和理论计算机科学家。也许该平台的稍后版本将为其类和实用方法提供最先进的哈希函数，从而使普通程序员能够构造此类哈希函数。同时，本项所述的技术应足以适用于大多数应用程序。简单地说，可以说，使用具有众多除数的乘数会产生更多的结果。散列碰撞..因为为了有效地散列，我们想要最小化碰撞的次数，所以我们尝试使用一个乘法器，它有较少的除数。根据定义，素数有两个截然不同的正因子。相关问题来自一个字段的Java hashCode-菜谱，加上使用ApacheCommonsLang的构建器的示例将对象的哈希码定义为所有类变量哈希码的和、乘法、或其他值是否不正确？绝对初学者的比特转移指南？