为什么Java的String中的hashCode()使用31作为乘数？

StackOverflow https://stackoverflow.com/questions/299304

  •  08-07-2019
  •  | 
  •  

题

根据 Java 文档， 哈希码 为一个 String 对象计算如下：

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

使用 int 算术，其中 s[i] 是个 我字符串的第一个字符， n 是 字符串，以及 ^ 表示求幂。

为什么用31作为乘数？

我理解乘数应该是一个比较大的素数。那么为什么不是 29、37、甚至 97呢？

有帮助吗？

解决方案

根据Joshua Bloch的 Effective Java （一本不能出书的书）推荐足够的，我买了，感谢不断提到stackoverflow）：

  

选择值31是因为它是奇数素数。如果它是偶数并且乘法溢出，则信息将丢失，因为乘以2相当于移位。使用素数的优势不太明显，但它是传统的。 31的一个很好的属性是乘法可以用移位和减法代替，以获得更好的性能：31 * i == (i << 5) - i。现代虚拟机会自动执行此类优化。

（来自第3章，第9项：覆盖等于时始终覆盖哈希码，第48页）

其他提示

Goodrich和Tamassia 指出，如果你接受超过50,000个英语单词（形成为联盟）在Unix的两个变体中提供的单词列表中，使用常数31,33,37,39和41将在每种情况下产生少于7个冲突。知道这一点，许多Java实现选择其中一个常量应该不足为奇。

巧合的是，我正在阅读<！>“多项式哈希码<！>”部分。当我看到这个问题时。

编辑：这里是我上面提到的~10mb PDF书的链接。请参阅 Java中的数据结构和算法

在（大多数）旧处理器上，乘以31可能相对便宜。例如，在ARM上，它只有一条指令：

RSB       r1, r0, r0, ASL #5    ; r1 := - r0 + (r0<<5)

大多数其他处理器需要单独的移位和减法指令。但是，如果你的乘数很慢，这仍然是一个胜利。现代处理器往往具有快速乘法器，因此只要32位在正确的一侧，它就没有太大的区别。

这不是一个很好的哈希算法，但它比1.0代码更好，更好（并且比1.0规范要好得多！）。

通过相乘，位向左移位。这使用了更多可用的哈希码空间，减少了冲突。

通过不使用2的幂，也会填充低位，最右边的位，以便与进入散列的下一个数据混合。

表达式n * 31等同于(n << 5) - n。

你可以在<！>注释<！>下阅读Bloch的原始推理。在 http://bugs.java.com/bugdatabase/view_bug.do?bug_id = 4045622 。他研究了不同散列函数在得到的<！>“平均链大小<！>”方面的表现。在哈希表中。 P(31)是他在K <！> amp; R的书中找到的那个时期的常见功能之一（但即使是Kernighan和Ritchie也记不住它来自哪里）。最后他基本上不得不选择一个，所以他拿了P(33)，因为它似乎表现得很好。尽管<=>并不是真的更糟糕，33乘以同样快的计算（只是换了5和加法），他选择了31，因为33不是素数：

  

其余的   四，我可能选择P（31），因为它是在RISC上计算最便宜的   机器（因为31是两个两个幂的差异）。 P（33）是   同样便宜的计算，但它的表现略差，并且   33是复合的，这让我有点紧张。

因此，推理并不像这里的许多答案所暗示的那样理性。但是在我们做出决定之后，我们都很善于提出合理的理由（甚至布洛赫也可能会这样做）。

实际上，37会很好用！ z：= 37 * x可以计算为y := x + 8 * x; z := x + 4 * y。这两个步骤都对应于一个LEA x86指令，因此速度非常快。

事实上，通过设置y := x + 8 * x; z := x + 8 * y，可以以相同的速度乘以更大的素数 73 。

使用73或37（而不是31）可能会更好，因为它会导致更密集的代码：两个LEA指令只占用6个字节而7个字节用于移动+移位+减法一个可能的警告是，这里使用的3参数LEA指令在英特尔Sandy桥架构上变慢，延迟增加3个周期。

此外， 73 是Sheldon Cooper最喜欢的号码。

Neil Coffey 解释为什么31在下使用熨平偏置

基本上使用31可以为哈希函数提供更均匀的设置位概率分布。

来自 JDK-4045622 ，其中Joshua Bloch描述了原因为什么选择特定的（新）String.hashCode()实施

  

下表总结了各种哈希的性能   上述功能，用于三个数据集：

     

1）Merriam-Webster中所有带有条目的单词和短语          第二国际未删节字典（311,141字符串，平均长度为10个字符）。

     

2）/ bin / ，/ usr / bin / ，/ usr / lib / ，/ usr / ucb / 中的所有字符串          和/ usr / openwin / bin / *（66,304个字符串，平均长度为21个字符）。

     

3）网络抓取工具收集的网址列表，其中包含多个网址          昨晚（28,372弦，平均49个字符）。

     

表中显示的效果指标是<！>“平均链尺寸<！>”;   哈希表中的所有元素（即，期望的值）   密钥数比较查找元素。）

                          Webster's   Code Strings    URLs
                          ---------   ------------    ----
Current Java Fn.          1.2509      1.2738          13.2560
P(37)    [Java]           1.2508      1.2481          1.2454
P(65599) [Aho et al]      1.2490      1.2510          1.2450
P(31)    [K+R]            1.2500      1.2488          1.2425
P(33)    [Torek]          1.2500      1.2500          1.2453
Vo's Fn                   1.2487      1.2471          1.2462
WAIS Fn                   1.2497      1.2519          1.2452
Weinberger's Fn(MatPak)   6.5169      7.2142          30.6864
Weinberger's Fn(24)       1.3222      1.2791          1.9732
Weinberger's Fn(28)       1.2530      1.2506          1.2439
     

看看这个表，很明显除了的所有功能   当前的Java函数和Weinberger的两个破碎版本   功能提供优秀，几乎无法区分的性能。一世   强烈推测这种表现基本上是这样的   <！>“理论上的理想<！>”，如果您使用了真正的随机数，那就是你得到的   数字生成器代替哈希函数。

     

我排除了WAIS功能，因为它的规范包含随机数页面，其性能并不比任何一个都好。   更简单的功能。其余六个功能中的任何一个看起来都像   出色的选择，但我们必须选择一个。我想我会排除   Vo的变体和Weinberger的功能因为它们的增加   复杂性，尽管很小。在剩下的四个中，我可能会选择   P（31），因为它是在RISC机器上计算最便宜的（因为31   是两个权力的差异两个）。 P（33）同样便宜   计算，但它的表现略差，而33   复合，这让我有点紧张。

     

约什

我不确定，但我猜他们会测试一些质数样本，并发现31对可能的字符串样本进行了最佳分布。

布洛赫并没有详细讨论这一点，但我一直听到/相信的基本原理是，这是基本代数。哈希归结为乘法和模运算，这意味着如果可以的话，您永远不想使用具有公因数的数字。换句话说，相对质数提供了均匀分布的答案。

使用哈希组成的数字通常是：

  • 将其放入的数据类型的模数 （2^32 或 2^64）
  • 哈希表中存储桶计数的模数（各不相同。在java中曾经是质数，现在是2^n）
  • 在混合函数中乘以或移位一个幻数
  • 输入值

您实际上只能控制其中的几个值，因此需要额外小心。

在最新版本的JDK中，仍然使用31。 https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/String.html#hashCode()

哈希字符串的目的是

  • 唯一（让我们看看运算符 ^ 在hashcode计算文档中，它有助于唯一）
  • 计算成本低廉

31 是可以放入 8 位（= 1 字节）寄存器的最大值。可以放入1字节寄存器的最大素数，是奇数。

乘以 31 << 5 然后减去自身，因此需要廉价的资源。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top