为什么在哈希码中使用素数？

hashcode java primes

2022-08-31 06:20:27

我只是想知道为什么在类的方法中使用素数？例如，当使用 Eclipse 生成我的方法时，总是使用质数：hashCode()hashCode()31

public int hashCode() {
     final int prime = 31;
     //...
}

引用：

这里有一个很好的哈希代码入门和关于哈希工作原理的文章，我发现（C#，但概念是可转移的）：Eric Lippert的GetHashCode（）的指南和规则

答案 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

请注意，当使用素模量与非素模量时，几乎完美的分布。

然而，尽管上面的例子很大程度上是人为的，但一般原则是，在处理输入模式时，使用素数模量将产生最佳分布。

答案 2

因为您希望要乘以的数字和要插入的存储桶数具有正交质因数分解。

假设有 8 个存储桶要插入其中。如果您用于乘以的数字是 8 的某个倍数，则插入到中的存储桶将仅由最低有效条目（根本不相乘的条目）确定。类似的条目将发生冲突。不适合哈希函数。

31 是一个足够大的素数，以至于存储桶的数量不太可能被它整除（事实上，现代 Java HashMap 实现将桶的数量保持在 2 的幂）。