为什么String中的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岁？

1> matt b..：

---

根据Joshua Bloch的Effective Java(一本不能推荐的书,以及我在stackoverflow上不断提及而购买的书):

选择值31是因为它是奇数素数.如果它是偶数并且乘法溢出,则信息将丢失,因为乘以2相当于移位.使用素数的优势不太明显,但它是传统的.31的一个很好的特性是乘法可以用移位和减法代替,以获得更好的性能:31 * i == (i << 5) - i.现代VM自动执行此类优化.

(来自第3章,第9项:覆盖等于时始终覆盖哈希码,第48页)

---

所有素数都是奇数,除了2.只是说.

---

我认为31的选择是相当不幸的.当然,它可能会在旧机器上节省一些CPU周期,但是你已经在短的ascii字符串上发生了哈希冲突,例如"@和#!,或者Ca和DB.如果您选择,例如,1327144003,或者在至少524287也允许bitshift:524287*i == i << 19 - i.

---

31被选中因为它是一个奇数素数??? 这没有任何意义 - 我说31被选中是因为它给出了最好的分布 - 检查http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

---

我不认为布洛赫说它被选中是因为它是一个奇数素数,但是因为它是奇数并且因为它是素数(因为它可以很容易地被优化为移位/减法).

---

@Jason请参阅我的答案http://stackoverflow.com/questions/1835976/what-is-a-sensible-prime-for-hashcode-calculation/2816747#2816747.我的观点是:如果你使用更大的素数,你会得到更少的碰撞,而这些日子里什么都不会丢失.如果您使用非英语语言与常见的非ascii字符,问题会更严重.在编写自己的hashCode函数时,31作为许多程序员的坏例子.

---

@FrankQ。问题并没有泛滥成灾：正如您所说，这是不可避免的。问题是，乘以偶数可确保更少的位包含“变化的”信息-低位变为零。始终为零。您已经失去了一点“可变性”。结果是可能的哈希值分布较差。

---

@hstoerr:我想看看你的数学.即使你是对的(你最有可能是2位数的例子),我想如果你看一下Java中如何使用哈希,那么在非常短的字符串中发生冲突并不会真的伤害到很多东西.它们并不常用于钥匙.

2> JohnZaj..：

---

正如古德里奇和塔玛西亚指出的那样,如果你接受超过50,000个英语单词(形成为两个Unix变体中提供的单词列表的联合),使用常数31,33,37,39和41将产生少于7个冲突在每种情况下.知道这一点,许多Java实现选择其中一个常量应该不足为奇.

巧合的是,当我看到这个问题时,我正在阅读"多项式哈希码"部分.

编辑:这里是我上面提到的~10mb PDF书的链接.请参见Java中的数据结构和算法的第10.2节哈希表(第413页)

---

但是请注意,如果您使用ASCII范围之外的常用字符的任何类型的国际字符集,您可能会遇到更多冲突.至少,我检查了31和德语.所以我认为31的选择被打破了.

3> Tom Hawtin -..：

---

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

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

大多数其他处理器需要单独的移位和减法指令.但是,如果你的乘数很慢,这仍然是一个胜利.现代处理器往往具有快速乘法器,因此它没有太大的区别,只要32在正确的一侧.

它不是一个很好的哈希算法,但它足够好并且比1.0代码更好(并且比1.0规范好得多!).

---

有趣的是,31的乘法在我的台式机上实际上比乘法比92821慢一点.我想编译器试图将它"优化"为移位并添加.:-)

---

@supercat有趣的是，`Map.Entry`的哈希码已通过规范固定为`key.hashCode（）^ value.hashCode（）`，尽管它甚至不是无序的对，例如`key`和`value `具有完全不同的含义。是的，这意味着Map.of（42，42）.hashCode（）或Map.of（“ foo”，“ foo”，“ bar”，“ bar”）。hashCode（）等预期为零。因此，请勿将地图用作其他地图的键…

4> erickson..：

---

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

通过不使用2的幂,也填充低阶最右边的位,以与进入散列的下一个数据混合.

表达式n * 31相当于(n << 5) - n.

5> David Ongaro..：

---

您可以在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的两个幂的差异).P(33)计算起来同样便宜,但它的表现稍微差一些,而且33是复合的,这让我有点紧张.

因此,推理并不像这里的许多答案所暗示的那样理性.但是在我们做出决定之后,我们都很善于提出合理的理由(甚至布洛赫也可能会这样做).

---

彻底的研究和公正的答案!

6> hrr..：

---

实际上,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个字节,而7个字节用于移动+移位+减法乘以31个.一个可能的警告是这里使用的3参数LEA指令在英特尔的Sandy网桥架构上变得更慢,延迟增加了3个周期.

此外,73是Sheldon Cooper最喜欢的号码.

---

@Mainguy它实际上是ALGOL语法,在伪代码中经常使用.

---

你是一个pascal程序员还是什么？什么是:=东西？

---

@Mainguy [在伪代码中做什么:=是什么意思？](http://programmers.stackexchange.com/questions/101716/in-pseudo-code-what-does-mean)

---

但是在ARM程序集中,31乘法可以在一条指令中完成

7> TheJuice..：

---

尼尔·科菲(Neil Coffey)解释了为什么31在熨平偏见时使用.

基本上使用31为哈希函数提供了更均匀的设置位概率分布.

8> Flow..：

---

来自JDK-4045622,Joshua Bloch描述了String.hashCode()选择特定(新)实施的原因

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

1)所有在Merriam-Webster的第二个国际完整字典中有条目的单词和短语(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的两个幂的差异).P(33)计算起来同样便宜,但它的表现稍微差一些,而且33是复合的,这让我有点紧张.

玩笑