我不确定，但我猜他们测试了一些质数样本，发现31在一些可能的字符串样本中给出了最好的分布。

我不确定，但我猜他们测试了一些质数样本，发现31在一些可能的字符串样本中给出了最好的分布。

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

参见Java中的数据结构和算法的9.2节哈希表(第522页)。

对哈希函数的一个很大的期望是，它们的结果的均匀随机性在哈希(x) % N这样的操作中仍然存在，其中N是一个任意数字(在许多情况下，是2的幂)，一个原因是这样的操作通常用于哈希表中确定槽。在计算散列时使用质数乘数会降低乘数和N个共享除数的概率，这将使操作的结果不那么均匀随机。

还有人指出了一个很好的性质，即乘31可以由一个乘法和一个减法来完成。我只是想指出这样的质数有一个数学术语:梅森质数

所有梅森质数都比2的幂小1所以我们可以写成

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字节)，就像这样?好吧，这将很难与当前定义的哈希，你需要单独乘以每个字符(请告诉我如果有一点hack来解决这个问题:D)。

事实上，37就可以了!Z:= 37 * x可计算为y:= x + 8 * x;z:= x + 4 * y。这两个步骤都对应一个LEA x86指令，所以这是非常快的。

事实上，通过设置y:= x + 8 * x，可以以同样的速度完成与更大的素数73的乘法运算;Z:= x + 8 * y。

使用73或37(而不是31)可能会更好，因为它会导致更密集的代码:两条LEA指令只占用6个字节，而move+shift+subtract(31的乘法)占用7个字节。一个可能的警告是，这里使用的3参数LEA指令在英特尔的Sandy桥架构上变慢了，延迟增加了3个周期。

而且，73是谢尔顿·库珀最喜欢的数字。

在(大多数)老式处理器上，乘以31可能相对便宜。例如，在ARM上，它只有一条指令:

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

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

这不是一个很好的哈希算法，但它已经足够好了，比1.0代码更好(比1.0规范好得多!)。