title: Why does HashSet allow equal items if hashcodes are different?
body: <p>The <a href="http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html" rel="noreferrer">HashSet</a> class has an <a href="http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html#add%28E%29" rel="noreferrer">add(Object o)</a> method, which is not inherited from another class. The Javadoc for that method says the following:</p>
  
  <blockquote>
    <p>Adds the specified element to this set if it is not already present. More formally, adds the specified element <code>e</code> to this set if this set contains no element <code>e2</code> such that <code>(e==null ? e2==null : e.equals(e2))</code>. If this set already contains the element, the call leaves the set unchanged and returns <code>false</code>.</p>
  </blockquote>
  
  <p>In other words, if two objects are equal, then the second object will not be added and the HashSet will remain the same. However, I've discovered that this is not true if objects <code>e</code> and <code>e2</code> have different hashcodes, despite the fact that <code>e.equals(e2)</code>. Here is a simple example:</p>
  
  <pre><code>import java.util.HashSet;
  import java.util.Iterator;
  import java.util.Random;
  
  public class BadHashCodeClass {
  
      /**
       * A hashcode that will randomly return an integer, so it is unlikely to be the same
       */
      @Override
      public int hashCode(){
          return new Random().nextInt();
      }
  
      /**
       * An equal method that will always return true
       */
      @Override
      public boolean equals(Object o){
          return true;
      }
  
      public static void main(String... args){
          HashSet&lt;BadHashCodeClass&gt; hashSet = new HashSet&lt;&gt;();
          BadHashCodeClass instance = new BadHashCodeClass();
          System.out.println("Instance was added: " + hashSet.add(instance));
          System.out.println("Instance was added: " + hashSet.add(instance));
          System.out.println("Elements in hashSet: " + hashSet.size());
  
          Iterator&lt;BadHashCodeClass&gt; iterator = hashSet.iterator();
          BadHashCodeClass e = iterator.next();
          BadHashCodeClass e2 = iterator.next();
          System.out.println("Element contains e and e2 such that (e==null ? e2==null : e.equals(e2)): " + (e==null ? e2==null : e.equals(e2)));
      }
  </code></pre>
  
  <p>The results from the main method are:</p>
  
  <pre><code>Instance was added: true
  Instance was added: true
  Elements in hashSet: 2
  Element contains e and e2 such that (e==null ? e2==null : e.equals(e2)): true
  </code></pre>
  
  <p>As the example above clearly shows, HashSet was able to add two elements where <code>e.equals(e2)</code>.</p>
  
  <p>I'm going to assume that this is <em>not</em> a bug in Java and that there is in fact some perfectly rational explanation for why this is. But I can't figure out what exactly. What am I missing?</p>