根据 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
问问题
162562 次
13 回答
443
根据 Joshua Bloch 的Effective Java（这本书推荐得不够多，由于在 stackoverflow 上的不断提及，我买了这本书）：
选择值 31 是因为它是一个奇数素数。如果它是偶数并且乘法溢出，则信息将丢失，因为乘以 2 相当于移位。使用素数的优势不太明显，但它是传统的。31 的一个很好的属性是乘法可以用移位和减法代替以获得更好的性能：
31 * i == (i << 5) - i. 现代虚拟机自动进行这种优化。
（来自第 3 章第 9 项：覆盖等于时始终覆盖哈希码，第 48 页）
于 2008-11-18T18:53:24.447 回答
86
Goodrich 和 Tamassia 从超过 50,000 个英语单词（由两个 Unix 变体中提供的单词列表的并集）计算得出，使用常量 31、33、37、39 和 41 在每种情况下将产生少于 7 个冲突。这可能是许多 Java 实现选择此类常量的原因。
请参阅Java中的数据结构和算法的第 9.2 节哈希表（第 522 页）。
于 2008-11-18T20:56:28.757 回答
59
在（大部分）旧处理器上，乘以 31 可能相对便宜。例如，在 ARM 上，它只有一条指令：
RSB r1, r0, r0, ASL #5 ; r1 := - r0 + (r0<<5)
大多数其他处理器将需要单独的移位和减法指令。但是，如果您的乘数很慢，这仍然是一个胜利。现代处理器往往具有快速乘法器，因此只要 32 在正确的一侧，它就不会产生太大影响。
这不是一个很好的哈希算法，但它已经足够好并且比 1.0 代码更好（并且比 1.0 规范好得多！）。
于 2008-11-18T17:01:45.563 回答
38
通过乘法，位向左移动。这使用了更多可用的哈希码空间，减少了冲突。
通过不使用 2 的幂，低位、最右边的位也被填充，与进入散列的下一条数据混合。
表达式n * 31等价于(n << 5) - n。
于 2009-05-19T18:10:57.263 回答
33
您可以在http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622的“评论”下阅读 Bloch 的原始推理。他研究了不同哈希函数在哈希表中产生的“平均链大小”的性能。P(31)是他在 K&R 的书中找到的那个时期的常见函数之一（但即使是 Kernighan 和 Ritchie 也不记得它是从哪里来的）。最后他基本上只能选择一个，所以他选择了，P(31)因为它似乎表现得足够好。尽管P(33)实际上并没有更糟，并且乘以 33 的计算速度同样快（只是移位 5 和加法），但他选择了 31，因为 33 不是素数：
在剩下的四个中，我可能会选择 P(31)，因为它是在 RISC 机器上计算的最便宜的（因为 31 是 2 的两个幂的差）。P(33) 计算起来同样便宜，但它的性能稍差，而且 33 是复合的，这让我有点紧张。
因此，推理并不像这里的许多答案似乎暗示的那样合理。但我们都善于在直觉决定后提出合理的理由（甚至布洛赫也可能倾向于这样做）。
于 2016-02-10T00:46:26.533 回答
23
实际上，37 会很好用！z := 37 * x 可以计算为y := x + 8 * x; z := x + 4 * y. 这两个步骤都对应一个 LEA x86 指令，因此速度非常快。
事实上，与更大的素数73的乘法可以通过设置 以相同的速度完成y := x + 8 * x; z := x + 8 * y。
使用 73 或 37（而不是 31）可能会更好，因为它会导致代码更密集：两个 LEA 指令只占用 6 个字节，而 move+shift+subtract 的 7 个字节用于乘以 31。一个可能的警告是此处使用的 3 参数 LEA 指令在英特尔的 Sandy 桥架构上变得更慢，延迟增加了 3 个周期。
此外，73是 Sheldon Cooper 最喜欢的数字。
于 2011-07-27T19:37:44.703 回答
19
Neil Coffey解释了为什么在Ironing out the bias中使用 31 。
基本上使用 31 可以为散列函数提供更均匀的设置位概率分布。
于 2011-12-07T15:27:18.477 回答
14
来自JDK-4045622，其中 Joshua Bloch 描述了选择该特定（新）String.hashCode()实现的原因
下表总结了上述各种散列函数对三个数据集的性能：
1) 韦氏词典第 2 版国际未删节词典中包含条目的所有单词和短语（311,141 个字符串，平均长度 10 个字符）。
2) /bin/ 、 /usr/bin/、 /usr/lib/ 、 /usr/ucb/ 和 /usr/openwin/bin/* 中的所有字符串（66,304 个字符串，平均长度 21 个字符）。
3) 昨晚运行了几个小时的网络爬虫收集的 URL 列表（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 是 2 的两个幂的差）。P(33) 计算起来同样便宜，但它的性能稍差，而且 33 是复合的，这让我有点紧张。
乔什
于 2017-06-12T21:17:03.210 回答
5
布洛赫并没有完全深入，但我一直听到/相信的基本原理是这是基本代数。哈希归结为乘法和取模运算，这意味着如果可以提供帮助，您永远不想使用具有公因数的数字。换句话说，相对质数提供了答案的均匀分布。
使用哈希组成的数字通常是：
- 您放入的数据类型的模数（2^32 或 2^64）
- 哈希表中存储桶计数的模数（变化。在 java 中曾经是素数，现在是 2^n）
- 在混合函数中乘以或移位一个幻数
- 输入值
您实际上只能控制其中几个值，因此需要格外小心。
于 2010-04-28T22:39:13.817 回答
5
在最新版本的 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 然后减去自身，因此需要廉价资源。
于 2019-02-18T02:03:42.737 回答
4
Java String hashCode() 和 31
这是因为 31 有一个很好的属性——它的乘法可以用比标准乘法更快的按位移位来代替：
31 * i == (i << 5) - i
于 2019-07-18T18:05:06.043 回答
3
我不确定，但我猜他们测试了一些素数样本，发现 31 在一些可能的字符串样本上给出了最佳分布。
于 2008-11-18T16:58:03.683 回答
1
哈希函数的一个很大期望是，它们的结果的均匀随机性可以在诸如hash(x) % N其中 N 是任意数（在许多情况下是 2 的幂）之类的操作中幸存下来，一个原因是此类操作通常在哈希表中用于确定槽. 在计算哈希时使用素数乘数会降低乘数和 N 共享除数的概率，这会使运算结果的随机性降低。
其他人指出了乘以 31 可以通过乘法和减法来完成的好特性。我只想指出，这种素数有一个数学术语：梅森素数
所有梅森素数都小于 2 的幂，因此我们可以将它们写为：
p = 2^n - 1
将 x 乘以 p：
x * p = x * (2^n - 1) = x * 2^n - x = (x << n) - x
在许多机器上，移位 (SAL/SHL) 和减法 (SUB) 通常比乘法 (MUL) 快。请参阅Agner Fog 的说明表
这就是为什么 GCC 似乎通过用移位和子替换它们来优化梅森素数的乘法，见这里。
然而，在我看来，这么小的素数对于散列函数来说是一个糟糕的选择。使用相对较好的散列函数，您会期望散列的较高位具有随机性。然而，使用 Java 散列函数，具有较短字符串的较高位几乎没有随机性（并且较低位的随机性仍然非常值得怀疑）。这使得构建高效的哈希表变得更加困难。看看这个用 Java 散列函数做不到的好技巧。
一些答案提到他们认为 31 适合一个字节是好的。这实际上是无用的，因为：
(1) 我们执行移位而不是乘法，因此乘数的大小无关紧要。
(2) 据我所知，没有特定的 x86 指令可以将 8 字节值与 1 字节值相乘，因此即使您正在相乘，您也需要将“31”转换为 8 字节值。看到这里，你乘以整个 64 位寄存器。
（而 127 实际上是一个字节中最大的梅森素数。）
较小的值会增加中低位的随机性吗？也许吧，但它似乎也大大增加了可能的冲突:)。
人们可以列出许多不同的问题，但它们通常归结为两个没有很好地实现的核心原则：混淆和扩散
但它快吗？可能，因为它没有多大作用。但是，如果性能真的是这里的重点，那么每个循环一个字符是非常低效的。对于更长的字符串，为什么不每次循环迭代一次 4 个字符（8 个字节），像这样？好吧，这与当前的哈希定义很难做到，您需要将每个字符单独相乘（请告诉我是否有一些技巧可以解决这个问题：D）。
于 2020-06-23T23:54:38.877 回答