title: Why chose 31 to do the multiplication in the hashcode() implementation ?
body: <blockquote>
    <p><strong>Possible Duplicate:</strong><br>
    <a href="https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier">Why does Java&#39;s hashCode() in String use 31 as a multiplier?</a><br>
    <a href="https://stackoverflow.com/questions/3613102/why-use-a-prime-number-in-hashcode">Why use a prime number in hashCode?</a>  </p>
  </blockquote>
  
  
  
  <p>From <a href="http://books.google.co.in/books/about/Effective_Java.html?id=Ft8t0S4VjmwC&amp;redir_esc=y" rel="nofollow noreferrer">Effective Java</a> <strong>Item 9: Always override hashCode when you override equals</strong> consider the following relevant code snippet that overrides the hashcode() defined in Object class.</p>
  
  <pre><code>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;
   }
  }
  </code></pre>
  
  <p>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 <code>hashcode()</code>. 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.</p>
  
  <blockquote>
    <p>The value 31 was chosen because it is an odd prime. <em>If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting</em>. The advantage of using a prime is less clear, but it is traditional.</p>
  </blockquote>