为什么在hashCode中使用质数?

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

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

引用:

这是一个很好的Hashcode入门和关于哈希如何工作的文章，我发现(c#，但概念是可迁移的): Eric Lippert的GetHashCode()指南和规则 < / p >
76883 次浏览
小开

我听说选择31是为了编译器可以优化乘法到左移5位，然后减去这个值。

小开

它通常有助于在哈希桶中实现更均匀的数据分布，特别是对于低熵键。

小开

下面是一个更接近源代码的引用。

这可以归结为:

  • 31是质数，减少碰撞
  • 31 .产生良好的分布，配合
  • 在速度上的合理权衡
小开
最佳答案

因为你想让你要乘的数和你要插入的桶数有正交质因数分解。

假设有8个桶要插入。如果要乘的数字是8的倍数，那么插入的bucket将只由最小有效项(根本没有相乘的项)决定。类似的条目会发生冲突。这对哈希函数来说不太好。

31是一个足够大的质数，因此存储桶的数量不可能被它整除(事实上，现代java HashMap实现将存储桶的数量保持为2的幂)。

小开

质数的选择是为了在哈希桶中最好地分配数据。如果输入的分布是随机且均匀分布的，那么哈希码/模量的选择并不重要。只有当输入有特定的模式时，它才会产生影响。

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

注意使用质数模量和非质数模量时几乎完美的分布。

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

小开

不管怎样，Effective Java第二版放弃了数学问题，只说选择31的原因是:

  • 因为它是一个奇数质数，而且它是“传统的”;使用质数
  • 它也比2的幂小1，这允许按位优化

下面是来自第9项:当你重写__ABC1时，总是重写hashCode的完整引用:

选择31是因为它是一个奇质数。如果它是偶数并且乘法溢出，信息就会丢失，因为乘法乘以2相当于移位。使用质数的优势不太明显，但它是传统的。

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

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

现代虚拟机自动进行这类优化。

虽然本文中的配方产生了相当好的哈希函数，但它并没有产生最先进的哈希函数，Java平台库在1.6版中也没有提供这样的哈希函数。编写这样的哈希函数是一个研究课题，最好留给数学家和理论计算机科学家。

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

相当简单地说，可以这样说，使用带有多个除数的乘数将导致更多哈希碰撞。因为为了有效的哈希，我们想要最小化碰撞的数量，所以我们尝试使用具有较少除数的乘数。根据定义，质数有两个完全不同的正数除数。

相关问题

小开

首先计算哈希值模2^32 (int的大小)，所以你想要一个相对于2^32的素数(相对素数意味着没有公约数)。任何奇数都可以。

对于一个给定的哈希表，索引通常是从哈希值对哈希表的大小取模计算出来的，所以你需要一个相对于哈希表大小的素数。出于这个原因，哈希表的大小通常被选为质数。在Java的情况下，Sun实现确保大小总是2的幂，所以奇数在这里也足够了。还有一些附加的哈希键按摩，以进一步限制冲突。

如果哈希表和乘数有一个公共因子n，那么在某些情况下哈希表中只会使用1/n个条目。

小开

31也是特定于Java HashMap的，它使用int作为散列数据类型。因此最大容量为2^32。使用更大的费马质数或梅森质数是没有意义的。

小开

使用素数的原因是为了在数据显示某些特定模式时尽量减少冲突。

首先:如果数据是随机的，那么就不需要质数，你可以对任何数字做mod运算，对于每个可能的模量值，你将有相同的碰撞次数。

但当数据不是随机的时，奇怪的事情就会发生。例如，考虑总是10的倍数的数字数据。

如果我们用mod 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的倍数。这意味着我们必须选择一个不会除键的质数，选择一个大的质数通常就足够了。

所以在重复的方面，使用素数的原因是为了中和键的模式在哈希函数碰撞分布中的影响。


提交答案