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

Question

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

578

根据Java文档，计算字符串对象的哈希码的方法如下：

哈希码是针对String对象计算的。

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

使用int算术，在此情况下，其中s [i]是字符串的第i个字符，n是字符串的长度，^表示指数。

为什么使用31作为乘数？

我知道乘数应该是一个相对较大的质数。那么为什么不选用29、37或甚至是97呢？

- jko

1

还可以参考https://dev59.com/SHI-5IYBdhLWcg3weoPR - 如果你要编写自己的hashCode函数，我认为31是一个不好的选择。 - Hans-Peter Störr

16

如果是29、37，甚至是97的话，你会问：“为什么不是31呢？” - user207421

3

重要的是了解选择某个数字的原因，除非该数字是黑魔法技巧的结果。 - Dushyant Sabharwal

这里有一篇关于此的博客文章，作者是@peter-lawrey：https://vanilla-java.github.io/2018/08/12/Why-do-I-think-Stringhash-Code-is-poor.html 和 https://vanilla-java.github.io/2018/08/15/Looking-at-randomness-and-performance-for-hash-codes.html。 - Christophe Roussy

1

我的观点是，它本可以是29、37、97、41或许多其他值，而这并没有产生太大的实际差异。我们在1976年使用了37。 - user207421

13个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Raphaël Colantonio · Answer 1

在最新版本的JDK中，仍然使用31。https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/lang/String.html#hashCode() 哈希字符串的目的是：

唯一性（看看哈希码计算文档中的运算符^，它有助于唯一性）
计算成本低廉

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

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

- Dave L. · Answer 2

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

- Altan · Answer 3

哈希函数的一个很大期望就是它们的结果在进行操作（如hash(x) % N，其中N是任意数字，而且在许多情况下是2的幂）后仍然保持均匀随机性。原因之一是这种操作通常用于哈希表中以确定插槽。当计算哈希时使用质数乘数可以降低乘数和N共有除数的概率，这会使操作的结果不太均匀随机。

其他人指出了乘以31的好处在于可以通过乘法和减法来完成。我只想指出这样的质数有一个数学术语：Mersenne Prime。

所有梅森质数都比某个2的幂少1，所以我们可以将它们写成：

p = 2^n - 1

将x乘以p：

x * p = x * (2^n - 1) = x * 2^n - x = (x << n) - x

Shifts (SAL/SHL)和减法（SUB）通常比乘法（MUL）快得多。在许多机器上，参见Agner Fog的指令表。

这就是为什么GCC似乎通过用移位和减法替换mersenne质数来优化乘法请看这里。

然而，在我看来，这样一个小的质数对于哈希函数来说是一个不好的选择。使用相对较好的哈希函数，您会期望在哈希的高位具有随机性。然而，使用Java哈希函数时，短字符串的高位几乎没有随机性（低位的随机性也非常值得怀疑）。这使得构建高效的哈希表更加困难。请参见这个很棒的技巧，你无法在Java哈希函数中实现。

一些答案提到他们认为31适合放入一个字节中是好的。这实际上是无用的，因为：

(1) 我们使用移位而不是乘法，因此乘数的大小并不重要。 (2) 据我所知，在x86指令中没有特定的指令可以将8字节值与1字节值相乘，因此即使您进行乘法运算，也需要将“31”转换为8字节值。请参见这里，您可以乘以整个64位寄存器。（127实际上是适合一个字节的最大mersenne质数。）较小的值是否会增加中低位的随机性？也许，但它似乎也极大地增加了可能的冲突：）。我们可以列出许多不同的问题，但它们通常归结为两个核心原则未被很好地满足：混淆和扩散。

但是它快吗？可能是的，因为它并没有做很多事情。然而，如果性能真的是重点，每个循环迭代只处理一个字符效率相当低下。对于较长的字符串，为什么不每次迭代处理4个字符（8字节）像这样呢？嗯，由于需要逐个乘以每个字符，这在当前哈希定义下可能会比较困难（如果有位运算技巧可以解决，请告诉我:D）。