为什么String中的hashCode（）使用31作为乘数？
在Java中， String对象的哈希码计算为
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
使用int算术，其中s[i]是string的第 i 个字符， n是string的长度， ^表示取幂。
为什么31被用作乘数？
我知道乘数应该是一个相对较大的素数。 那么为什么不是29，或37，甚至97？
根据Joshua Bloch的Effective Java （一本不能被推荐的书，而且我经常在stackoverflow中提到，这是我买的书）：
值31被select，因为它是一个奇数的素数。 如果它是偶数，并且倍增溢出，则信息将会丢失，因为乘以2相当于移位。 使用素数的好处不太清楚，但是是传统的。 31的一个很好的特性是乘法可以被一个移位和一个减法取代以获得更好的性能：
31 * i == (i << 5) - i。 现代虚拟机自动进行这种优化。
（从第3章，第9项：覆盖等于时总是覆盖哈希码，第48页）
正如Goodrich和Tamassia所指出的那样，如果你接收了超过50,000个英文单词（形成Unix的两种变体提供的单词列表的联合），使用常量31,33,37,39和41将产生less于7次的冲突在每种情况下。 知道这一点，许多Java实现select这些常量之一就不足为奇了。
巧合的是，当我看到这个问题的时候，我正在阅读“多项式哈希码”部分。
编辑：这里是链接到〜10mb PDF书我指的是上面。 请参见Java中的“ 数据结构和algorithm”的 10.2哈希表（第417页）
在（大部分）旧的处理器上，乘以31可能会相对便宜。 例如在ARM上，它只是一个指令：
RSB r1, r0, r0, ASL #5 ; r1 := - r0 + (r0<<5)
大多数其他处理器将需要单独的移位和减法指令。 但是，如果你的乘数很慢，这仍然是一个胜利。 现代的处理器往往有快速的乘法器，所以它没有太大的区别，只要32是正确的一面。
这不是一个很好的哈希algorithm，但它比1.0代码更好，更好（并且比1.0版本好得多）。
通过相乘，位向左移动。 这使用了更多的散列码可用空间，减less了冲突。
通过不使用2的幂，低位，最右边的位也被填充，以与下一个进入散列的数据混合。
expression式n * 31相当于(n << 5) - n 。
尼尔·科菲（Neil Coffey） 解释了为什么在熨烫时使用31。
基本上使用31给你一个更平均的哈希函数的设置位概率分布。
事实上，37会工作得很好！ z：= 37 * x可以计算为y := x + 8 * x; z := x + 4 * y y := x + 8 * x; z := x + 4 * y 。 这两个步骤对应一个LEA x86指令，所以这是非常快的。
事实上，通过设置y := x + 8 * x; z := x + 8 * y可以以相同的速度乘以更大的素数73 y := x + 8 * x; z := x + 8 * y y := x + 8 * x; z := x + 8 * y 。
使用73或37（而不是31）可能会更好，因为它会导致代码更密集 ：两个LEA指令只需要6个字节，而移动+ shift + shift +减去31个乘以31.这样一个可能的警告是在英特尔的Sandy bridge体系结构中，此处使用的三参数LEA指令变慢，延迟时间增加了3个周期。
而且，Sheldon Cooper最喜欢的数字是73 。
您可以在http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622的; “评论”下阅读Bloch的原始推理。 他调查了散列表中所产生的“平均链大小”的不同散列函数的性能。 在那段时间里， P(31)是他在K＆R书中发现的常见function之一（但是即使Kernighan和Ritchie也不记得它来自哪里）。 最后，他基本上不得不select一个，所以他拿P(31)因为它似乎performance不错。 即使P(33)并不是真的更糟糕，33的乘法也是同样快的计算（只是一个5和一个加法），他select了31，因为33不是素数：
在剩下的四个中，我可能会selectP（31），因为它是在RISC机器上计算最便宜的（因为31是两个二的幂的差）。 P（33）计算起来同样便宜，但是性能稍微差一些，33是复合的，这让我有些紧张。
所以这个推理不像这里的许多答案似乎暗示的那样理性。 但是，在我们做出决定之后，我们都有理由提出合理的理由（甚至布洛赫也可能会这样做）。
我不确定，但我猜测他们testing了一些素数的样本，发现31个样本的string可能是最好的。
布洛赫并没有完全理解这一点，但我一直听到/相信的基本原理就是这是一个基本的代数。 哈希归结为乘法和模数运算，这意味着如果可以帮助的话，你永远都不想使用具有公因子的数字。 换句话说，相对的素数提供了均匀分布的答案。
使用散列组成的数字通常是：
- 数据types的模数（2 ^ 32或2 ^ 64）
- 在你的hashtable中bucket数量的模数（在java中曾经是素数，现在是2 ^ n）
- 在您的混音function中乘以或移动一个幻数
- input值
你真的只能控制这些值，所以要多加小心。
从JDK-4045622中 ，Joshua Bloch描述了为什么select这个特定的（新的） String.hashCode()实现的原因
下面的表格总结了上述各种散列函数对于三个数据集的性能：
1）所有在Merriam-Webster's第二国际未删节词典（311,141个string，平均长度为10个字符）中input的单词和短语。
2）/ bin / ，/ usr / bin / ，/ usr / lib / ，/ usr / ucb /和/ usr / openwin / bin / *中的所有string（66,304个string，平均长度为21个字符）。
3）一个由networking爬虫收集的URL列表，昨天晚上运行了几个小时（28372个string，平均长度为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函数的两个破解版本之外，所有的函数都提供了非常好的几乎不可区分的性能。 我强烈猜测这个performance本质上是“理论上的理想”，如果你使用一个真正的随机数发生器来代替散列函数，那么你会得到这个理论上的理想。
我会排除WAIS函数，因为它的规范包含了随机数字的页面，其性能没有任何更简单的函数更好。 剩下的六个function中的任何一个都是非常好的select，但我们必须select一个。 我想我会排除Vo的变体和Weinberger的function，因为它们增加了复杂性，尽pipe很小。 在剩下的四个中，我可能会selectP（31），因为它是在RISC机器上计算最便宜的（因为31是两个二的幂的差）。 P（33）计算起来同样便宜，但是性能稍微差一些，33是复合的，这让我有些紧张。
玩笑
