为什么选择31做乘法中的散列code（）的实现？ [英] Why chose 31 to do the multiplication in the hashcode() implementation ?

问题描述

  

可能重复：
  <一href="http://stackoverflow.com/questions/299304/why-does-javas-hash$c$c-in-string-use-31-as-a-multiplier">Why没有Java的哈希值code（）在字符串中使用31作为乘数？
  为什么使用散列code质数？

从有效的Java < STRONG>第9项：始终覆盖散列code，当你重载equals 考虑覆盖散列code（）在Object类中定义的以下相关code段

 公共final类联系号码{
  私人最终总之区code;
  私人最终短preFIX;
  私人最终短行号;
  ...... //故意忽略休息
  .....

私人挥发性INT散列code; //（见项目71）
@覆盖公众诠释哈希code（）{
   INT结果=散列code;
   如果（结果== 0）{
    结果= 17;
    结果= 31 *结果+区域code;
    结果= 31 *结果+ preFIX;
    结果= 31 *结果+行号;
    哈希code =结果;
   }
 返回结果;
 }
}
 

我明白为什么一个非零初始值17被选中。我也明白了乘法的每一步做到让字段顺序发挥计算了重要作用散code（）。但我不明白的选择31作为乘法值的原因。可有一个人给我解释一下为什么？这就是布洛赫不得不说的31，但我真的不明白这一点。我特别不明白下面以斜体字就行了。

  

值31的选择，因为它是一个奇素数。 如果它甚至和乘法溢出时，信息会丢失，如乘2等于移的。使用黄金的优点是不太清楚，但它是传统的。

解决方案

左移只是介绍了正确的零，失去了一下数量的二进制重新presentation左边，所以这是一个明确的信息丢失。重复这个过程中逐渐失去了从早期的计算累积的所有信息。这意味着更多的字段中输入您的哈希值code计算，对最终结果的早期领域具有影响较小。

Possible Duplicate:
Why does Java's hashCode() in String use 31 as a multiplier?
Why use a prime number in hashCode?

From Effective Java Item 9: Always override hashCode when you override equals consider the following relevant code snippet that overrides the hashcode() defined in Object class.

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;
 }
}

I understand why a non zero initial value "17" is chosen . I also understand the that multiplication is done in each step so that the order of fields play an important role in computing hashcode(). But I do not understand the reason for choosing 31 as the value for multiplication . Can some one explain to me why ? This is what Bloch has to say about 31 but I do not really get it . I specifically fail to understand the line in italics below.

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional.

解决方案

Shifting left just introduces a zero on the right and loses a bit on the left of the number's binary representation, so it's a clear information loss. Repeating this process gradually loses all information that was accumulated from earlier computation. That means that the more fields enter your hashcode calculation, the less effect on the final result the early fields have.

这篇关于为什么选择31做乘法中的散列code（）的实现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！