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

Question

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

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

using int arithmetic, where s[i] is the i th character of the string, n is the length of the string, and ^ indicates求幂。

为什么31用作乘数？

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

原文由 jacobko 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

根据 Joshua Bloch 的 Effective Java （一本推荐不够的书，由于在 stackoverflow 上不断提到，我买了这本书）：

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

（来自第 3 章第 9 项：当您覆盖 equals 时始终覆盖 hashcode，第 48 页）

原文由 matt b 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

Goodrich 和 Tamassia 从超过 50,000 个英语单词（形成为 Unix 的两个变体中提供的单词列表的并集）计算得出，使用常量 31、33、37、39 和 41 将在每种情况下产生少于 7 次冲突。这可能是许多 Java 实现选择此类常量的原因。

请参阅 Java 中的数据结构和算法的 第 9.2 节哈希表（第 522 页）。

原文由 JohnZaj 发布，翻译遵循 CC BY-SA 4.0 许可协议