Java字符串hashCode()和31

这是因为31有一个很好的属性——它的乘法运算可以被逐位移位取代，这比标准乘法运算快得多:

31 * i == (i << 5) - i

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

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

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

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

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

Java字符串hashCode()和31

这是因为31有一个很好的属性——它的乘法运算可以被逐位移位取代，这比标准乘法运算快得多:

31 * i == (i << 5) - i

You can read Bloch's original reasoning under "Comments" in http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622. He investigated the performance of different hash functions in regards to the resulting "average chain size" in a hash table. P(31) was one of the common functions during that time which he found in K&R's book (but even Kernighan and Ritchie couldn't remember where it came from). In the end he basically had to choose one and so he took P(31) since it seemed to perform well enough. Even though P(33) was not really worse and multiplication by 33 is equally fast to calculate (just a shift by 5 and an addition), he opted for 31 since 33 is not a prime:

剩下的 第四，我可能会选择P(31)，因为它是RISC上最便宜的计算方法 机器(因为31是2的2次幂之差)P (33) 同样，计算起来很便宜，但它的性能稍微差一些，并且 33是合数，这让我有点紧张。

因此，推理并不像这里的许多答案所暗示的那样理性。但我们都善于在做出直觉决定后提出理性的理由(甚至布洛赫也可能倾向于这样)。

对哈希函数的一个很大的期望是，它们的结果的均匀随机性在哈希(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)。