为什么Java's hashCode()在字符串使用31作为乘数?

根据Java文档，String对象的散列码计算如下:

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

使用int算术，其中s[i]是 n是字符串的长度

. ^表示取幂

为什么用31作为乘数?

我知道乘数应该是一个相对较大的质数。那么为什么不是29岁，37岁，甚至97岁呢?

171781 次浏览
小开

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

小开

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

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

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

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

小开
最佳答案

根据约书亚·布洛赫的有效的Java(这本书怎么推荐都不为过，多亏了stackoverflow上不断的提及，我才买了这本书):

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

(摘自第3章第9项:重写equals时总是重写hashcode，第48页)

小开

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

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

小开

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

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

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

小开

Bloch并没有深入研究这个问题，但我总是听到/相信这是基本的代数。哈希可以归结为乘法和模运算，这意味着如果可以的话，永远不要使用带公因式的数字。换句话说，相对素数提供了答案的均匀分布。

使用哈希的数字通常是:

  • 你放入的数据类型的模量 (2^32或2^64)
  • 哈希表中桶数的模数(变化。在java中，以前是质数，现在是2^n)
  • 在混合函数中乘以或平移一个神奇的数字
  • 输入值

实际上，您只能控制其中的几个值，因此需要多加注意。

小开

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

事实上，与更大的质数73相乘可以通过设置y := x + 8 * x; z := x + 8 * y以相同的速度完成。

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

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

小开

尼尔·科菲解释了为什么在消除偏见下面使用31。

基本上，使用31可以为哈希函数提供更均匀的集位概率分布。

小开

你可以在http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622的“评论”下阅读Bloch的原始推理。他研究了不同哈希函数在哈希表中产生的“平均链大小”方面的性能。P(31)是他在K&R的书中发现的一个常见函数(但即使是Kernighan和Ritchie也不记得它是从哪里来的)。最后，他不得不选择一个，所以他选择了P(31)，因为它似乎表现得足够好。尽管P(33)并不是真的更糟糕，乘以33的计算速度也同样快(只需要平移5和一个加法)，但他选择了31，因为33不是质数:

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

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

小开

在jdk - 4045622中，Joshua Bloch描述了为什么选择特定的(新的)String.hashCode()实现的原因

下表总结了各种哈希的性能 上述函数，用于三个数据集:

1)韦氏词典收录的所有单词和短语 第2个国际未删节字典(311,141个字符串，平均长度10个字符).

2) /bin/, /usr/bin/， /usr/lib/， /usr/ucb/中的所有字符串 /usr/openwin/bin/*(66,304个字符串，平均长度21个字符).

3)一个由网络爬虫收集的url列表 (28,372个字符串，平均长度49个字符).

表中显示的性能指标是“平均链大小” 对哈希表中的所有元素(即

.

.

. 
                          Webster's   Code Strings    URLs
---------   ------------    ----
Current Java Fn.          1.2509      1.2738          13.2560
P(37)    [Java]           1.2508      1.2481          1.2454
P(65599) [Aho et al]      1.2490      1.2510          1.2450
P(31)    [K+R]            1.2500      1.2488          1.2425
P(33)    [Torek]          1.2500      1.2500          1.2453
Vo's Fn                   1.2487      1.2471          1.2462
WAIS Fn                   1.2497      1.2519          1.2452
Weinberger's Fn(MatPak)   6.5169      7.2142          30.6864
Weinberger's Fn(24)       1.3222      1.2791          1.9732
Weinberger's Fn(28)       1.2530      1.2506          1.2439
看这张表，很明显所有的函数除了 当前的Java函数和Weinberger的两个坏版本 功能提供优秀的，几乎没有区别的性能。我 强烈的推测，这种表现本质上是对的 “理论理想”，这是你使用真实随机时得到的结果

.数字生成器代替哈希函数 我排除了WAIS函数，因为它的规范包含数页的随机数，而且它的性能并不比任何一个 更简单的函数。剩下的六个函数看起来都是 不错的选择，但我们必须选一个。我想我可以排除 Vo的变体和Weinberger的函数因为它们的添加 复杂性，尽管很小。剩下的四个，我可能会选择 P(31)，因为它是在RISC机器上最便宜的计算(因为31 是2的2次幂之差)。P(33)同样便宜 计算，但它的性能略差，33是 复合，这让我有点紧张。

杰克

小开

在最新版本的JDK中，仍然使用31。# EYZ0

哈希字符串的目的是

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

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

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

小开

Java字符串hashCode()和31

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

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

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

这就是为什么GCC似乎通过将梅森质数的乘法替换为移位和置换来优化它们的原因，在这里看到的。

然而，在我看来，如此小的质数对于哈希函数来说是一个糟糕的选择。对于一个相对较好的哈希函数，你会期望在哈希的较高位具有随机性。然而，使用Java哈希函数，对于较短的字符串，在较高的位上几乎没有随机性(在较低的位上仍然具有高度可疑的随机性)。这使得构建高效哈希表变得更加困难。看到# EYZ0。

一些回答提到，他们认为31适合一个字节是好的。这实际上是无用的，因为:

(1)我们执行移位而不是乘法，因此乘数的大小无关紧要。

(2)据我所知，没有特定的x86指令来将8字节的值与1字节的值相乘，所以你需要转换“31”;到8字节的值，即使是乘法运算。参见在这里，您将整个64位寄存器相乘。

(127实际上是一个字节所能容纳的最大梅森素数。)

较小的值是否会增加中下位的随机性?也许吧，但这似乎也大大增加了可能的碰撞:)。

人们可以列出许多不同的问题，但它们通常可以归结为两个核心原则没有很好地实现:混乱与扩散

但是速度快吗?可能吧，因为它没什么用。然而，如果性能真的是这里的重点，那么每个循环一个字符是相当低效的。为什么不每次循环迭代4个字符(8字节)更长的字符串，像这样?好吧，这将很难与当前定义的哈希，你需要单独乘以每个字符(请告诉我如果有一点hack来解决这个问题:D)。


提交答案