为什么Java的String hashCode()使用31作为乘数？

为什么 Java 中 String 的 hashCode() 使用 31 作为乘数

在 Java 中，String 对象的哈希码是使用公式：

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

其中 s[i] 是字符串的第 i 个字符， n 是字符串的长度，^ 表示求幂。

素数乘数的重要性

此公式的一个关键方面是素数乘数的使用，在本例中为 31。使用素数的优点是减少哈希冲突的可能性。如果使用非素数乘数，两个具有相同哈希值的字符串可以共享一个公因子，从而更容易发生哈希冲突。

为什么不使用另一个素数？

虽然 31 是奇素数，但也可以选择其他素数，例如 29、37 或 97。 31 基于多种因素的组合：

• 避免溢出： 31 是一个相对较小的质数，这降低了乘法过程中整数溢出的风险。如果使用偶素数，乘以 2 时可能会发生溢出，从而可能丢失信息。
• 性能优化： 正如 Joshua Bloch 在《Effective Java》中所指出的，乘以 31 可以被更有效的移位和减法运算取代：31 * i == (i
• 传统：对哈希函数使用质数乘数是一种长期的做法，31 是特别受欢迎的选择。虽然没有明确选择 31 的原因，但它已成为许多编程语言和应用程序的标准选择。

以上是为什么Java的String hashCode()使用31作为乘数？的详细内容。更多信息请关注PHP中文网其他相关文章！