6

可能重复：
为什么 Java 的 String 中的 hashCode() 使用 31 作为乘数？
为什么在 hashCode 中使用素数？

来自Effective Java Item 9: Always override hashCode when you override equals考虑以下相关代码片段，它覆盖了 Object 类中定义的 hashcode()。

public final class PhoneNumber {
  private final short areaCode;
  private final short prefix;
  private final short lineNumber;
  ......//Rest ignored on purpose
  .....

private volatile int hashCode; // (See Item 71)
@Override public int hashCode() {
   int result = hashCode;
   if (result == 0) {
    result = 17;
    result = 31 * result + areaCode;
    result = 31 * result + prefix;
    result = 31 * result + lineNumber;
    hashCode = result;
   }
 return result;
 }
}

我明白为什么选择非零初始值“17”。我也理解乘法是在每个步骤中完成的，因此字段的顺序在计算中起着重要作用hashcode()。但我不明白选择 31 作为乘法值的原因。有人可以向我解释为什么吗？这就是布洛赫要说的关于 31 的内容，但我真的不明白。我特别无法理解下面斜体字。

选择值 31 是因为它是一个奇数素数。如果它是偶数并且乘法溢出，信息将会丢失，因为乘以 2 相当于移位。使用素数的优势不太明显，但它是传统的。

4

3 回答 3

11

左移只是在右边引入了一个零，在数字的二进制表示的左边丢失了一点，所以这是一个明显的信息丢失。重复这个过程会逐渐丢失从早期计算中积累的所有信息。这意味着输入哈希码计算的字段越多，早期字段对最终结果的影响就越小。

于 2012-07-18T08:20:13.983 回答
3

使用素数的原因是它更有可能产生随机模式。例如，如果您使用 9，则可以以 3 的倍数越过一圈。

AFAIK31用于字符串，因为字母表中的字母少于 31 个，这意味着最多 6 个字母的所有单词都具有唯一的哈希码。例如，如果您使用 61（质数小于 64），最多 5 个字母会产生唯一代码，如果您使用 13（质数小于 16），您可能会与两个字母单词发生冲突。

于 2012-07-18T08:26:41.123 回答
1

我将描述一个不同数字的答案，但我怀疑推理是相似的。对字符 X 的哈希值的贡献是 X*B^k，其中 B 在您的情况下为 31，k 取决于 X 在字符串中的位置及其长度。这种算术通常以字长为模完成。出于这个原因，我们希望 B^k 对于不同的 k 值是不同的。

Now, in "Handbook of Algorithms and Data Structures" by Gonnet and Baeza-Yates section 3.3.1 "Pratical hashing functions" they say "For this function the value B=131 is recommended, as B^i has a maximum cycle mod 2^k for 8 <= k <= 64." I wonder what cycle length 31 has mod 2^32? I believe that 31 will fit into a Sparc immediate operand, but 131 will not.

于 2012-07-18T17:51:17.737 回答