为什么在hashCode中使用素数？

Question

我只是想知道为什么在类的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

因为您需要乘以的数字和要插入的桶数以具有正交的素数因子分解.

假设有8个桶要插入.如果您用来乘以的数字是8的某个倍数,那么插入的数据桶将仅由最不重要的条目(根本不相乘的条目)确定.类似的条目将发生冲突.哈希函数不好用.

31是一个足够大的素数,桶的数量不可能被它整除(事实上,现代的Java HashMap实现将桶的数量保持为2的幂).

Answer 3

为了它的价值,Effective Java 2nd Edition可以放弃数学问题,只是说选择31的原因是:

• 因为它是一个奇数素数,并且使用素数是"传统的"
• 它也是一个小于2的幂,它允许按位优化

这是完整的引用,来自第9项:覆盖hashCode时始终覆盖equals:

选择值31是因为它是一个奇数素数.如果它是偶数并且乘法溢出,则信息将丢失,因为乘以2相当于移位.使用素数的优势不太明显,但它是传统的.

31的一个很好的属性是乘法可以用shift(§15.19)和减法代替以获得更好的性能:

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

现代VM自动执行此类优化.

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

也许平台的后续版本将为其类和实用程序方法提供最先进的哈希函数,以允许普通程序员构造这样的哈希函数.与此同时,本项目中描述的技术应该适用于大多数应用程序.

相当简单,可以说使用具有多个除数的乘法器将导致更多的散列冲突.由于有效散列我们希望最小化碰撞次数,因此我们尝试使用具有较少除数的乘数.根据定义,素数具有两个截然不同的正分数.

相关问题

• 来自一个字段的Java hashCode - 配方,以及使用Apache Commons Lang的构建器的示例
• 将对象的哈希码定义为所有类变量哈希码的和,乘,等等是不正确的吗？
• 绝对新手的位移指南？

Answer 4

我听说31被选中以便编译器可以优化乘法到左移5位然后减去该值.