title: HashMap contains several different keys having the same value?
body: <p>What I did was simple: I would like to creat a <code>HashMap&lt;Pair, ArrayList&lt;Integer&gt;&gt;</code> with <code>Pair</code> as the key and <code>ArrayList&lt;Integer&gt;</code> as the value. The <code>Pair</code> is self-defined class containing elements <code>l</code> (left) and <code>r</code> (right).</p>
  
  <p><strong>At first</strong>, I did this as following:</p>
  
  <pre><code>Map&lt;Pair, ArrayList&lt;Integer&gt;&gt; hashmap = new HashMap&lt;&gt;();
  ArrayList&lt;String&gt; stringList = new ArrayList&lt;&gt;();
  stringList.add("a");
  stringList.add("b");
  stringList.add("c");
  stringList.add("a");
  Pair&lt;String, Integer&gt; aPair = new Pair&lt;&gt;(" ", 1); // HERE will be changed!
  
  for (String aString: stringList) {
    aPair.setLeft(aString);
    if (!hashmap.containsKey(aPair)){
      hashmap.put(aPair, new ArrayList&lt;Integer&gt;());
    }
    hashmap.get(aPair).add(1);
  }
  
  for (Map.Entry&lt;Pair, ArrayList&lt;Integer&gt;&gt; entry: hashmap.entrySet()) {
    out.println(entry.getKey().getLeft() + " " + entry.getKey().getRight() + " " + entry.getValue());
  }
  </code></pre>
  
  <p>But the output is: </p>
  
  <pre><code>a 1 [1]
  a 1 [1]
  a 1 [1, 1]
  </code></pre>
  
  <p><strong>However</strong>, if I changed the above code into the following:</p>
  
  <pre><code>Map&lt;Pair, ArrayList&lt;Integer&gt;&gt; hashmap = new HashMap&lt;&gt;();
  ArrayList&lt;String&gt; stringList = new ArrayList&lt;&gt;();
  stringList.add("a");
  stringList.add("b");
  stringList.add("c");
  stringList.add("a");
  
  for (String aString: stringList) {
    Pair&lt;String, Integer&gt; aPair = new Pair&lt;&gt;(aString, 1); // HERE changed!
    if (!hashmap.containsKey(aPair)){
      hashmap.put(aPair, new ArrayList&lt;Integer&gt;());
    }
    hashmap.get(aPair).add(1);
  }
  
  for (Map.Entry&lt;Pair, ArrayList&lt;Integer&gt;&gt; entry: hashmap.entrySet()) {
    out.println(entry.getKey().getLeft() + " " + entry.getKey().getRight() + " " + entry.getValue());
  }
  </code></pre>
  
  <p>The change made was putting the declaration of <code>Pair&lt;String, Integer&gt; aPair</code> into the for-loop. The results new are what I wanted as following:</p>
  
  <pre><code>c 1 [1]
  b 1 [1]
  a 1 [1, 1]
  </code></pre>
  
  <p>Why it is like this? <a href="https://stackoverflow.com/questions/6687157/same-values-with-different-keys-in-a-hashmap">Here</a> is a similar question. But it is still different. </p>
  
  <p><strong>EDIT</strong>: as mentioned in the comments below by @Eran, the self-defined <code>Pair</code> override the methods <code>hashCode()</code> and <code>equals()</code></p>
  
  <pre><code>@Override
  public int hashCode() { return left.hashCode() ^ right.hashCode(); }
  
  @Override
  public boolean equals(Object o) {
    if (!(o instanceof Pair)) return false;
    Pair&lt;?, ?&gt; pairo = (Pair&lt;?, ?&gt;) o;
    return this.left.equals(pairo.getLeft()) &amp;&amp;
           this.right.equals(pairo.getRight());
  }
  </code></pre>