为什么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岁呢?

当前回答

事实上，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是谢尔顿·库珀最喜欢的数字。

其他回答

在最新版本的JDK中，仍然使用31。https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/lang/String.html hashCode ()

哈希字符串的目的是

唯一(让我们看看hashcode计算文档中的运算符^，它有助于唯一) 计算成本低

31是可以放入8位(= 1字节)寄存器的最大值，是可以放入1字节寄存器的最大素数，是奇数。

31乘以<<5然后减去自己，因此需要廉价的资源。

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

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

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

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

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

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

通过相乘，位向左移位。这使用了更多哈希码的可用空间，减少了冲突。

通过不使用2的幂，低阶，最右边的位也被填充，与进入散列的下一段数据混合。

表达式n * 31等价于(n << 5) - n。

推荐文章