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

Question

为什么Java的字符串中的hashCode()使用31作为乘数？根据Java文档，散列码为了String对象计算为：s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]使用int算术，哪里s[i]是i字符串的第四个字符，n字符串的长度，以及^指示指数。为什么31被用作乘数？我知道乘数应该是一个相对较大的素数。那么为什么不是29，37，甚至97呢？

Answer 1

根据约书亚·布洛赫的有效Java(这是一本不能推荐的书，我之所以买这本书，是因为我不断地提到堆叠溢出)：

之所以选择31值，是因为它是一个奇数素数。如果是偶数，乘法溢出，信息就会丢失，因为乘2等于移动。使用质数的优点不太清楚，但它是传统的。31的一个优点是可以用移位和减法来代替乘法，以获得更好的性能：31 * i == (i << 5) - i..现代VM自动进行这种优化。

(从第3章第9项：当您重写等于时始终重写hashcode，第48页)

Answer 2

如Goodrich和Tamassia指出，如果您取超过50，000个英文单词(由Unix的两个变体中提供的单词列表组成)，使用常数31、33、37、39和41在每种情况下产生的碰撞将少于7次。知道了这一点，许多Java实现选择这些常量之一就不足为奇了。

巧合的是，当我看到这个问题时，我正在阅读“多项式哈希码”一节。

编辑：这是链接到~10 mb PDF的书，我指的是上面。见第10.2节散列表(第413页)Java中的数据结构和算法

Answer 3

在(大部分)旧处理器上，乘以31可能比较便宜。例如，在手臂上，它只是一条指令：

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

大多数其他处理器都需要一个单独的移位和减法指令。然而，如果你的乘数比较慢，这仍然是一场胜利。现代处理器往往有快速乘法器，所以它不会有太大的区别，只要32正确的一面。

它不是一个很好的哈希算法，但它足够好，也比1.0代码好(而且比1.0规范好得多！)