HashMap contains several different keys having the same value?

Question

What I did was simple: I would like to creat a HashMap<Pair, ArrayList<Integer>> with Pair as the key and ArrayList<Integer> as the value. The Pair is self-defined class containing elements l (left) and r (right).

At first, I did this as following:

Map<Pair, ArrayList<Integer>> hashmap = new HashMap<>();
ArrayList<String> stringList = new ArrayList<>();
stringList.add("a");
stringList.add("b");
stringList.add("c");
stringList.add("a");
Pair<String, Integer> aPair = new Pair<>(" ", 1); // HERE will be changed!

for (String aString: stringList) {
  aPair.setLeft(aString);
  if (!hashmap.containsKey(aPair)){
    hashmap.put(aPair, new ArrayList<Integer>());
  }
  hashmap.get(aPair).add(1);
}

for (Map.Entry<Pair, ArrayList<Integer>> entry: hashmap.entrySet()) {
  out.println(entry.getKey().getLeft() + " " + entry.getKey().getRight() + " " + entry.getValue());
}

But the output is:

a 1 [1]
a 1 [1]
a 1 [1, 1]

However, if I changed the above code into the following:

Map<Pair, ArrayList<Integer>> hashmap = new HashMap<>();
ArrayList<String> stringList = new ArrayList<>();
stringList.add("a");
stringList.add("b");
stringList.add("c");
stringList.add("a");

for (String aString: stringList) {
  Pair<String, Integer> aPair = new Pair<>(aString, 1); // HERE changed!
  if (!hashmap.containsKey(aPair)){
    hashmap.put(aPair, new ArrayList<Integer>());
  }
  hashmap.get(aPair).add(1);
}

for (Map.Entry<Pair, ArrayList<Integer>> entry: hashmap.entrySet()) {
  out.println(entry.getKey().getLeft() + " " + entry.getKey().getRight() + " " + entry.getValue());
}

The change made was putting the declaration of Pair<String, Integer> aPair into the for-loop. The results new are what I wanted as following:

c 1 [1]
b 1 [1]
a 1 [1, 1]

Why it is like this? Here is a similar question. But it is still different.

EDIT: as mentioned in the comments below by @Eran, the self-defined Pair override the methods hashCode() and equals()

@Override
public int hashCode() { return left.hashCode() ^ right.hashCode(); }

@Override
public boolean equals(Object o) {
  if (!(o instanceof Pair)) return false;
  Pair<?, ?> pairo = (Pair<?, ?>) o;
  return this.left.equals(pairo.getLeft()) &&
         this.right.equals(pairo.getRight());
}

Answer 1

If an object’s hashCode() value can change based on its state, then we must be careful when using such objects as keys in hash-based collections to ensure that we don’t allow their state to change when they are being used as hash keys. All hash-based collections assume that an object’s hash value does not change while it is in use as a key in the collection. If a key’s hash code were to change while it was in a collection, some unpredictable and confusing consequences could follow. This is usually not a problem in practice — it is not common practice to use a mutable object like a List as a key in a HashMap.

From this answer