我想知道为什么在类的hashCode()
方法中使用素数?例如,当使用Eclipse生成我的hashCode()
方法时,总是使用素数31
:
public int hashCode() {
final int prime = 31;
//...
}
参考资料:
这里有一篇我找到的关于哈希码和哈希算法工作原理的好入门文章(C#语言的,但是概念是通用的): Eric Lippert's Guidelines and rules for GetHashCode()
我想知道为什么在类的hashCode()
方法中使用素数?例如,当使用Eclipse生成我的hashCode()
方法时,总是使用素数31
:
public int hashCode() {
final int prime = 31;
//...
}
参考资料:
这里有一篇我找到的关于哈希码和哈希算法工作原理的好入门文章(C#语言的,但是概念是通用的): Eric Lippert's Guidelines and rules for GetHashCode()
素数被选择为最佳分配哈希桶中的数据。如果输入的分布是随机且均匀的,那么哈希码/模数的选择就不重要了。仅在输入存在某种模式时才会产生影响。
当处理内存位置时,通常会出现这种情况。例如,所有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
注意使用质数模数与非质数模数时几乎完美的分布差异。
然而,尽管上面的例子在很大程度上是编造的,但通用原则是,在处理一组输入模式时,使用质数模数会产生最佳分布。
(x*8 + y) % 8 = (x*8) % 8 + y % 8 = 0 + y % 8 = y % 8
- ILMTitan就其价值而言,《Effective Java第二版》在数学问题上进行了手动豁免,并且仅仅说选择31的原因是:
以下是完整的引用,来自于《第9项:在覆盖equals时总是覆盖hashCode》:
简单来说,使用具有众多除数的乘数会导致更多的哈希冲突。由于对于有效的哈希,我们希望尽量减少冲突的数量,因此我们尝试使用具有较少除数的乘数。按照定义,质数恰好有两个不同的正除数。The value 31 was chosen because it's an odd prime. If it were even and multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional.
A nice property of 31 is that the multiplication can be replaced by a shift (§15.19) and subtraction for better performance:
31 * i == (i << 5) - i
Modern VMs do this sort of optimization automatically.
While the recipe in this item yields reasonably good hash functions, it does not yield state-of-the-art hash functions, nor do Java platform libraries provide such hash functions as of release 1.6. Writing such hash functions is a research topic, best left to mathematicians and theoretical computer scientists.
Perhaps a later release of the platform will provide state-of-the-art hash functions for its classes and utility methods to allow average programmers to construct such hash functions. In the meantime, the techniques described in this item should be adequate for most applications.
3、5、17、257、65537
,即 2^n + 1 的形式;另外一些是梅森质数,如3、7、31、127、8191、131071、524287、2147483647
,即2^n - 1 的形式。然而,选定了 31
而不是其他数字,比如 127
。 - Dmitry Bychenkomov reg1,reg2-shl reg1,5-sub reg1,reg2
可以在2个周期内执行。(mov只是一个重命名,并需要0个周期)。 - Johanint
的大小),因此你需要选择与2^32互质的数字(互质意味着没有公共因数)。任何奇数都可以。31也是Java HashMap特有的哈希数据类型int所使用的数字。因此,最大容量为2^32。使用更大的费马或梅森素数没有意义。
通常情况下,它有助于在哈希桶之间实现数据更均匀的分布,特别是对于低熵密钥。