logo标签列表

为什么在hashCode中使用素数？

javahashcodeprimes
204

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

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

参考资料：

这里有一篇我找到的关于哈希码和哈希算法工作原理的好入门文章（C#语言的，但是概念是通用的）： Eric Lippert's Guidelines and rules for GetHashCode()

3
好的，我会尽力为您进行翻译。以下是需要翻译的内容：related: Why does Java's hashCode() in String use 31 as a multiplier? - matt b
这更或多或少是问题https://dev59.com/7nM_5IYBdhLWcg3w-4Zg的副本。 - Hans-Peter Störr
1
请在 https://dev59.com/7nM_5IYBdhLWcg3w-4Zg#20206663 上检查我的答案。它与域上多项式的性质有关（不是环！），因此需要使用质数。 - TT_ stands with Russia
9个回答
156

素数被选择为最佳分配哈希桶中的数据。如果输入的分布是随机且均匀的，那么哈希码/模数的选择就不重要了。仅在输入存在某种模式时才会产生影响。

当处理内存位置时，通常会出现这种情况。例如，所有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

注意使用质数模数与非质数模数时几乎完美的分布差异。

然而，尽管上面的例子在很大程度上是编造的，但通用原则是，在处理一组输入模式时，使用质数模数会产生最佳分布。

26
我们现在讨论的是用于生成哈希码的乘数，而不是用于将这些哈希码分类到桶中的模数，对吧？ - ILMTitan
5
同样的原理。在输入/输出方面，哈希函数将输入传递到哈希表的模操作中。我认为要表达的观点是，如果你使用质数进行乘法运算，你会得到更加随机分布的输入值，以至于模操作不再重要。因为哈希函数能更好地分散输入，使它们不那么规则化，所以它们不太可能发生冲突，无论用哪种模数将它们放入桶中。 - Triynko
11
这样的答案非常有用，就像教人如何捕鱼而不是替别人捉鱼。它可以帮助人们“看到”并理解使用质数进行哈希的基本原理... 即通过不规则地分配输入，在模运算后均匀地将其分配到桶中 :)。 - Triynko
这应该是答案。上面评论中的后续问题也非常好（关于质数是乘数还是模数本质上并没有太大区别的原因）。 - Srikanth
112
因为你希望乘法因子和桶的数量具有正交的质因数分解。
假设有8个桶要插入。如果你用来乘的数字是8的倍数，那么插入的桶只会由最低位（根本没有乘）确定。类似的条目会发生冲突。对于哈希函数来说不好。
31是足够大的质数，桶的数量不太可能被它整除（事实上，现代Java HashMap实现将桶的数量保持为2的幂）。
9
如果使用乘以31的哈希函数会表现得不够优秀。然而，考虑到31作为乘数非常常见，我认为这样的哈希表实现是设计得不好的。 - ILMTitan
11
31被选中是基于这样一个假设：哈希表的实现者知道31在哈希码中被广泛使用。 - Steve Kuo
3
31被选中的理念是大多数实现具有相对较小质数的分解，通常是2、3和5。它可能从10开始，并在满载时增长3倍。大小很少是完全随机的。即使如此，30/31的概率也不错，可以拥有良好同步的哈希算法。正如其他人所说，这也可能很容易计算。 - ILMTitan
9
换句话说，为了编写一个函数，用于去除输入值集合中的规则性使得这些值不会在相同的哈希桶中碰撞，我们需要了解输入值集合及其规律。通过乘/除/取模的方式使用质数可以实现这个目的，因为如果你在一个有X个项的循环中跳Y个空间，则直到X成为Y的因数之前，你永远不会回到同一位置。由于X通常是偶数或2的幂，因此需要选择质数作为Y，以便X+X+X...不成为Y的因数，因此31 yay! :/ - Triynko
3
这是模运算的本质。(x*8 + y) % 8 = (x*8) % 8 + y % 8 = 0 + y % 8 = y % 8 - ILMTitan
显示剩余4条评论
35

就其价值而言，《Effective Java第二版》在数学问题上进行了手动豁免，并且仅仅说选择31的原因是：

  • 因为它是一个奇素数，而使用素数是“传统的”
  • 它还比一个2的幂次少1，这允许进行位优化

以下是完整的引用，来自于《第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.

简单来说，使用具有众多除数的乘数会导致更多的哈希冲突。由于对于有效的哈希，我们希望尽量减少冲突的数量，因此我们尝试使用具有较少除数的乘数。按照定义，质数恰好有两个不同的正除数。

相关问题

4
嗯，有许多适合的质数可以选择，其中一些是费马质数，如 3、5、17、257、65537，即 2^n + 1 的形式；另外一些是梅森质数，如3、7、31、127、8191、131071、524287、2147483647，即2^n - 1 的形式。然而，选定了 31 而不是其他数字，比如 127。 - Dmitry Bychenko
4
“因为它是一个奇素数”，所以只有一个偶素数 :P。 - Martin Schneider
1
我不喜欢《Effective Java》中“is less clear, but it is traditional”这个措辞。如果他不想深入数学细节，他应该写一些类似“有[相似的]数学原因”的东西。他写作的方式听起来好像只是历史背景而已 :( - Qw3ry
6
我听说选择31是为了让编译器将乘法优化为左移5位，然后再减去该值。
编译器怎么可能优化成那种方式呢？毕竟并非所有的x都满足x31==x32-1。你想表达的是左移5位（相当于乘以32），然后再减去原来的值（例如我的例子中的x）。虽然这样可能比乘法更快（顺便说一下，对于现代CPU处理器而言，可能并不是这样），但在选择哈希码的乘法时还有更重要的因素需要考虑（例如输入值的均匀分布到桶中）。 - Grizzly
做一些搜索，这是一个相当普遍的观点。 - Steve Kuo
5
普遍观点无关紧要。 - fractor
3
@Grizzly，它确实比乘法更快。IMul在任何现代CPU上的最小延迟为3个周期。(请参见Agner Fog的手册) mov reg1，reg2-shl reg1，5-sub reg1，reg2 可以在2个周期内执行。(mov只是一个重命名，并需要0个周期)。 - Johan
3

这里有一篇更接近原始来源的引用。

它可以归结为：

  • 31是质数，这减少了碰撞
  • 31产生良好的分布，并且
  • 在速度上有合理的权衡
3
首先，你需要计算哈希值模2^32（即int的大小），因此你需要选择与2^32互质的数字（互质意味着没有公共因数）。任何奇数都可以。
然后，对于给定的哈希表，索引通常是从哈希值模哈希表大小计算得出的，因此你需要选择一个相对于哈希表大小互质的数字。通常哈希表的大小被选为质数。在Java中，Sun的实现确保大小始终是2的幂，因此这里也可以使用奇数。还有一些额外的哈希键调整以进一步减少冲突。
如果哈希表和乘数有一个公共因数n，则可能会产生不良影响，在某些情况下仅使用哈希表中的1/n个条目。
2
使用质数的原因是在数据表现出某些特定模式时，可以最小化碰撞。
首先，如果数据是随机的，则不需要质数，可以对任何数字执行模运算，对于模数的每个可能值，都会有相同数量的碰撞。
但是，当数据不是随机的时候，奇怪的事情就会发生。例如，考虑始终为10的倍数的数字数据。
如果我们使用模4，我们会发现：
10 mod 4 = 2
20 mod 4 = 0
30 mod 4 = 2
40 mod 4 = 0
50 mod 4 = 2
因此，在模数的3个可能值（0、1、2、3）中，只有0和2会发生碰撞，这是不好的。
如果我们使用像7这样的质数：
10 mod 7 = 3
20 mod 7 = 6
30 mod 7 = 2
40 mod 7 = 4
50 mod 7 = 1
等等
我们还注意到5不是一个好选择，但5是质数的原因是所有的键都是5的倍数。这意味着我们必须选择一个不能被我们的键整除的质数，选择一个大的质数通常就足够了。
因此，用重复的方式来说，使用质数的原因是为了使哈希函数的碰撞分布中的密钥模式的影响达到中和的效果。
1

31也是Java HashMap特有的哈希数据类型int所使用的数字。因此，最大容量为2^32。使用更大的费马或梅森素数没有意义。

0

通常情况下，它有助于在哈希桶之间实现数据更均匀的分布，特别是对于低熵密钥。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接