在Java中， String 对象的hash code计算为
String
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
使用 int 算术，其中 s[i] 是字符串的 i 字符， n 是字符串的长度， ^ 表示取幂 .
int
s[i]
i
n
^
为什么31用作乘数？
我知道乘数应该是一个相对较大的素数 . 那么为什么不是29岁，37岁，甚至97岁？
根据Joshua Bloch的Effective Java（一本不能推荐的书，我买了这本书得益于不断提到的stackoverflow）：
选择值31是因为它是一个奇数素数 . 如果它是偶数并且乘法溢出，则信息将丢失，因为乘以2相当于移位 . 使用素数的优势不太明显，但它是传统的 . 31的一个很好的属性是乘法可以用移位和减法代替以获得更好的性能：31 * i ==（i << 5） - i . 现代VM自动执行此类优化 .
（来自第3章，第9项：覆盖等于时始终覆盖哈希码，第48页）
正如Goodrich and Tamassia指出的那样，如果你接受超过50,000个英语单词（形成为Unix的两个变体中提供的单词列表的联合），使用常数31,33,37,39和41将产生少于7个冲突案件 . 知道这一点，许多Java实现选择其中一个常量应该不足为奇 .
巧合的是，当我看到这个问题时，我正在阅读“多项式哈希码”部分 .
编辑：这里是我上面提到的~10mb PDF书的链接 . 请参见Data Structures and Algorithms in Java的10.2哈希表（第413页）一节
在（大多数）旧处理器上，乘以31可能相对便宜 . 例如，在ARM上，它只有一条指令：
RSB r1, r0, r0, ASL #5 ; r1 := - r0 + (r0<<5)
大多数其他处理器需要单独的移位和减法指令 . 但是，如果你的乘数很慢，这仍然是一个胜利 . 现代处理器往往具有快速乘法器，因此它没有太大的区别，只要32在正确的一侧 .
它不是一个很好的哈希算法，但它足够好，比1.0代码更好（并且比1.0规范好得多！） .
通过相乘，位向左移位 . 这使用了更多可用的哈希码空间，减少了冲突 .
通过不使用2的幂，也填充低阶最右边的位，以与进入散列的下一个数据混合 .
表达式 n * 31 等同于 (n << 5) - n .
n * 31
(n << 5) - n
您可以在http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622中的"Comments"下阅读Bloch的原始推理 . 他研究了哈希表中生成的"average chain size"的不同哈希函数的性能 . P(31) 是他在K＆R发现的那个时期的常见功能之一，记得它来自哪里 . 最后他基本上不得不选择一个，所以他拿了 P(31) 因为它看起来表现得还不错 . 虽然 P(33) 并不是真的更糟，乘以33同样快速计算（只是换了5和加法），他选择了31因为33不是素数：
P(31)
P(33)
在剩下的四个中，我可能会选择P（31），因为它是在RISC机器上计算最便宜的（因为31是2的两个幂的差异） . P（33）计算起来同样便宜，但它的表现稍微差一点，而且33是复合的，这让我有点紧张 .
因此，推理并不像这里的许多答案所暗示的那样理性 . 但是在我们做出决定之后，我们都很善于提出合理的理由（甚至布洛赫也可能会这样做） .
实际上，37会很好用！ z：= 37 * x可以计算为 y := x + 8 * x; z := x + 4 * y . 这两个步骤都对应于一个LEA x86指令，因此速度非常快 .
y := x + 8 * x; z := x + 4 * y
事实上，通过设置 y := x + 8 * x; z := x + 8 * y 可以以相同的速度乘以更大的素数 73 .
y := x + 8 * x; z := x + 8 * y
使用73或37（而不是31）可能会更好，因为它会导致更密集的代码：两个LEA指令只需要6个字节，而7个字节用于移位减法乘以31 . 一个可能的警告是3这里使用的参数LEA指令在英特尔的Sandy网桥架构上变得更慢，延迟增加了3个周期 .
此外，73是Sheldon Cooper最喜欢的号码 .
Neil Coffey explains为什么31用于熨平偏见 .
基本上使用31为哈希函数提供了更均匀的设置位概率分布 .
我不确定，但我猜他们测试了一些质数样本，并发现31在一些可能的字符串样本中给出了最好的分布 .
布洛赫并没有完全理解这一点，但我一直听到/相信的理由是这是基本的代数 . 哈希归结为乘法和模数运算，这意味着你永远不想使用数字有共同因素，如果你能帮助它 . 换句话说，相对素数提供了均匀的答案分布 .
使用哈希构成的数字通常是：
你输入的数据类型的
模数（2 ^ 32或2 ^ 64）哈希表中桶数的
模数（各不相同 . 在java以前是素数，现在是2 ^ n）
在混音函数中乘以幻数或乘以幻数
输入值
你真的只能控制这些 Value ，所以需要额外注意 .
从JDK-4045622开始，Joshua Bloch描述了选择特定（新） String.hashCode() 实施的原因
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的代码字符串URL
当前的Java Fn . 1.2509 1.2738 13.2560P（37）[Java] 1.2508 1.2481 1.2454P（65599）[Aho等] 1.2490 1.2510 1.2450P（31）[K R] 1.2500 1.2488 1.2425P（33）[Torek] 1.2500 1.2500 1.2453Vo的Fn 1.2487 1.2471 1.2462WAIS Fn 1.2497 1.2519 1.2452Weinberger的Fn（MatPak）6.5169 7.2142 30.6864Weinberger的Fn（24）1.3222 1.2791 1.9732Weinberger的Fn（28）1.2530 1.2506 1.2439看看这个表，很明显除了当前的Java函数和Weinberger函数的两个破坏版本之外的所有函数都提供了极好的，几乎无法区分的性能 . 我强烈推测这种性能本质上是“理论上的理想”，如果你用一个真正的随机数发生器来代替散列函数，那就是你所得到的 . 我排除了WAIS函数，因为它的规范包含随机数页面，并且它的性能并不比任何更简单的函数更好 . 其余六个功能中的任何一个看起来都是很好的选择，但我们必须选择一个 . 我想我会排除Vo的变体和Weinberger的功能，因为它们增加了复杂性，尽管很小 . 在剩下的四个中，我可能选择P（31），因为它是在RISC机器上计算最便宜的（因为31是2的两个幂的差异） . P（33）计算起来同样便宜，但它的表现稍微差一点，而且33是复合的，这让我有点紧张 . 玩笑
10 回答
根据Joshua Bloch的Effective Java（一本不能推荐的书，我买了这本书得益于不断提到的stackoverflow）：
（来自第3章，第9项：覆盖等于时始终覆盖哈希码，第48页）
正如Goodrich and Tamassia指出的那样，如果你接受超过50,000个英语单词（形成为Unix的两个变体中提供的单词列表的联合），使用常数31,33,37,39和41将产生少于7个冲突案件 . 知道这一点，许多Java实现选择其中一个常量应该不足为奇 .
巧合的是，当我看到这个问题时，我正在阅读“多项式哈希码”部分 .
编辑：这里是我上面提到的~10mb PDF书的链接 . 请参见Data Structures and Algorithms in Java的10.2哈希表（第413页）一节
在（大多数）旧处理器上，乘以31可能相对便宜 . 例如，在ARM上，它只有一条指令：
大多数其他处理器需要单独的移位和减法指令 . 但是，如果你的乘数很慢，这仍然是一个胜利 . 现代处理器往往具有快速乘法器，因此它没有太大的区别，只要32在正确的一侧 .
它不是一个很好的哈希算法，但它足够好，比1.0代码更好（并且比1.0规范好得多！） .
通过相乘，位向左移位 . 这使用了更多可用的哈希码空间，减少了冲突 .
通过不使用2的幂，也填充低阶最右边的位，以与进入散列的下一个数据混合 .
表达式
n * 31等同于(n << 5) - n.您可以在http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622中的"Comments"下阅读Bloch的原始推理 . 他研究了哈希表中生成的"average chain size"的不同哈希函数的性能 .
P(31)是他在K＆R发现的那个时期的常见功能之一，记得它来自哪里 . 最后他基本上不得不选择一个，所以他拿了P(31)因为它看起来表现得还不错 . 虽然P(33)并不是真的更糟，乘以33同样快速计算（只是换了5和加法），他选择了31因为33不是素数：因此，推理并不像这里的许多答案所暗示的那样理性 . 但是在我们做出决定之后，我们都很善于提出合理的理由（甚至布洛赫也可能会这样做） .
实际上，37会很好用！ z：= 37 * x可以计算为
y := x + 8 * x; z := x + 4 * y. 这两个步骤都对应于一个LEA x86指令，因此速度非常快 .事实上，通过设置
y := x + 8 * x; z := x + 8 * y可以以相同的速度乘以更大的素数 73 .使用73或37（而不是31）可能会更好，因为它会导致更密集的代码：两个LEA指令只需要6个字节，而7个字节用于移位减法乘以31 . 一个可能的警告是3这里使用的参数LEA指令在英特尔的Sandy网桥架构上变得更慢，延迟增加了3个周期 .
此外，73是Sheldon Cooper最喜欢的号码 .
Neil Coffey explains为什么31用于熨平偏见 .
基本上使用31为哈希函数提供了更均匀的设置位概率分布 .
我不确定，但我猜他们测试了一些质数样本，并发现31在一些可能的字符串样本中给出了最好的分布 .
布洛赫并没有完全理解这一点，但我一直听到/相信的理由是这是基本的代数 . 哈希归结为乘法和模数运算，这意味着你永远不想使用数字有共同因素，如果你能帮助它 . 换句话说，相对素数提供了均匀的答案分布 .
使用哈希构成的数字通常是：
你输入的数据类型的
模数（2 ^ 32或2 ^ 64）
哈希表中桶数的
模数（各不相同 . 在java以前是素数，现在是2 ^ n）
在混音函数中乘以幻数或乘以幻数
输入值
你真的只能控制这些 Value ，所以需要额外注意 .
从JDK-4045622开始，Joshua Bloch描述了选择特定（新）
String.hashCode()实施的原因当前的Java Fn . 1.2509 1.2738 13.2560
P（37）[Java] 1.2508 1.2481 1.2454
P（65599）[Aho等] 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的Fn 1.2487 1.2471 1.2462
WAIS Fn 1.2497 1.2519 1.2452
Weinberger的Fn（MatPak）6.5169 7.2142 30.6864
Weinberger的Fn（24）1.3222 1.2791 1.9732
Weinberger的Fn（28）1.2530 1.2506 1.2439
看看这个表，很明显除了当前的Java函数和Weinberger函数的两个破坏版本之外的所有函数都提供了极好的，几乎无法区分的性能 . 我强烈推测这种性能本质上是“理论上的理想”，如果你用一个真正的随机数发生器来代替散列函数，那就是你所得到的 . 我排除了WAIS函数，因为它的规范包含随机数页面，并且它的性能并不比任何更简单的函数更好 . 其余六个功能中的任何一个看起来都是很好的选择，但我们必须选择一个 . 我想我会排除Vo的变体和Weinberger的功能，因为它们增加了复杂性，尽管很小 . 在剩下的四个中，我可能选择P（31），因为它是在RISC机器上计算最便宜的（因为31是2的两个幂的差异） . P（33）计算起来同样便宜，但它的表现稍微差一点，而且33是复合的，这让我有点紧张 . 玩笑