为什么在hashCode中使用素数？
我只是想知道为什么在类的hashCode()方法中使用素数？ 例如，当使用Eclipse生成我的hashCode()方法时，总是使用素数31 ：
public int hashCode() { final int prime = 31; //... }
参考文献：
这里是一个关于哈希码和哈希如何工作，我发现（C＃，但概念是可转移的）的文章的一个很好的入门： Eric Lippert的准则和GetHashCode（）
因为你想要你乘的数量和你插入的桶的数量有正交的素数分解。
假设有8个桶插入。 如果您用来乘以的数字是8的倍数，则插入的桶将只由最不重要的入口（根本不相乘的入口）确定。 类似的条目会相互冲突。 不适合散列函数。
31是一个足够大的素数，桶的数量不可能被它整除（实际上，现代Java HashMap实现将桶的数量保持为2的幂）。
素数被select为在散列桶之间最好地分配数据。 如果input的分布是随机且均匀分布的，那么散列码/模数的select就不重要了。 只有当input有一定的模式时才会产生影响。
处理内存位置时通常是这种情况。 例如，所有的32位整数都alignment到可被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
注意使用质数模量与非质数模数的近乎完美的分布。
但是，尽pipe上面的例子在很大程度上是人为devise的，但总体原则是，在处理input模式时 ，使用素数模数将产生最佳的分布。
对于什么是值得的， 有效的Java第二版放手围绕math问题，只是说，select31的原因是：
- 因为这是一个奇怪的素数，使用素数是“传统的”
- 这也是一个不到2的幂，这允许按位优化
以下是第9条中的完整引用：当您覆盖equals时总是覆盖hashCode ：
值31被select，因为它是一个奇数的素数。 如果它是偶数并且倍增溢出，则信息将会丢失，因为乘以2相当于移位。 使用素数的好处不太清楚，但是是传统的。
31的一个很好的特性是乘法可以被replace为一个移位（ §15.19 ）和减法以获得更好的性能：
31 * i == (i << 5) - i现代虚拟机自动进行这种优化。
虽然这个项目中的配方可以产生相当好的散列函数，但它不会产生最先进的散列函数，Java平台库也不会提供像1.6版本那样的散列函数。 编写这样的哈希函数是一个研究课题，最好留给math家和理论计算机科学家来完成。
也许稍后的平台版本将为其类和实用方法提供最先进的散列函数，以允许普通程序员构build这样的散列函数。 同时，本文所述的技术应该适用于大多数应用。
简而言之，可以说使用一个有许多除数的乘法器会导致更多的散列冲突 。 由于有效的哈希，我们希望尽量减less碰撞的次数，我们尝试使用一个更less的除数乘法器。 根据定义，素数恰好有两个明显的正数因子。
相关问题
- 来自一个字段的Java hashCode – 配方，以及使用Apache Commons Lang的构build器的示例
- 定义一个对象的哈希码作为所有类variables哈希码的和，乘，无论是不正确的？
- 绝对新手指南移位？
我听说select了31，以便编译器可以将乘法优化为左移5位然后减去该值。
这里有一个更接近源的引文 。
归结为：
- 31是素数，减less了碰撞
- 31产生良好的分配，与
- 速度合理的折衷
首先计算2 ^ 32（ int的大小）的散列值，所以你想要一个相对于2 ^ 32的素数（相对的素数意味着没有公因数）。 任何奇数都可以做到这一点。
那么对于一个给定的散列表，索引通常是根据散列值以散列表的大小为模来计算的，所以你需要一些与散列表大小相当的东西。 出于这个原因，散列表的大小通常被选为素数。 在Java的情况下，Sun的实现可以确保大小总是2的幂，所以奇数就足够了。 还有一些额外的散列键按摩来进一步限制冲突。
如果散列表和乘数具有共同的因子n可能是在某些情况下，散列表中只有1 / n个条目将被使用。
它通常有助于在散列桶之间实现更均匀的数据传播，特别是对于低熵密钥。
31也特定于使用int作为散列数据types的Java HashMap。 因此最大容量为2 ^ 32。 使用更大的费马或梅森素数没有意义。
