title: Efficient hash code for multiset in Java
body: <p>I have defined a subinterface of <code>java.util.Collection</code> that effectively is a multiset (aka bag). It may not contain <code>null</code> elements, although that's not crucial to my question. The equals contract defined by the interface is as you would expect:</p>
  
  <ul>
  <li><code>obj instanceof MyInterface</code></li>
  <li><code>obj</code> contains the same elements as <code>this</code> (by <code>equals</code>)</li>
  <li><code>obj</code> contains the same number of duplicates for each element</li>
  <li>order of elements is disregarded</li>
  </ul>
  
  <p>Now I want to write my <code>hashCode</code> method. My initial idea was:</p>
  
  <pre><code>int hashCode = 1;
  for( Object o : this ) {
      hashCode += o.hashCode();
  }
  </code></pre>
  
  <p>However, I noticed that <code>com.google.common.collect.Multiset</code> (from Guava) defines the hash code as follows:</p>
  
  <pre><code>int hashCode = 0;
  for( Object o : elementSet() ) {
      hashCode += ((o == null) ? 0 : o.hashCode()) ^ count(o);
  }
  </code></pre>
  
  <p>It strikes me as odd that an empty Multiset would have hash code 0, but more importantly I don't understand the benefit of <code>^ count(o)</code> over simply adding up the hash codes of every duplicate. Maybe it's about not calculating the same hash code more than once, but then why not <code>* count(o)</code>?</p>
  
  <p>My question: what would be an efficient hash code calculation? In my case the count for an element is not guaranteed to be cheap to obtain.</p>