HashMap содержит несколько разных ключей, имеющих одинаковое значение?

Question

То, что я сделал, было просто: я хотел бы создать HashMap<Pair, ArrayList<Integer>> с Pair в качестве ключа и ArrayList<Integer> в качестве значения. Pair это самоопределяемый класс, содержащий элементы l (слева) и r (право).

Сначала я сделал это следующим образом:

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());
}

Но вывод:

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

Однако, если я изменил приведенный выше код в следующем:

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());
}

Сделанное изменение ставит декларацию Pair<String, Integer> aPair в цикл. Новые результаты - это то, что я хотел получить следующим образом:

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

Почему это так? Вот похожий вопрос. Но это все-таки другое.

РЕДАКТИРОВАТЬ: как упомянуто в комментариях ниже @Eran, самоопределение Pair переопределить методы hashCode() а также 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

Если значение hashCode() объекта может изменяться в зависимости от его состояния, то мы должны быть осторожны при использовании таких объектов в качестве ключей в коллекциях на основе хеша, чтобы не допустить изменения их состояния при использовании в качестве ключей хеша, Все основанные на хэше коллекции предполагают, что хеш-значение объекта не изменяется, пока оно используется в качестве ключа в коллекции. Если бы хэш-код ключа изменился, пока он находился в коллекции, это может привести к непредсказуемым и запутанным последствиям. На практике это обычно не является проблемой - не является обычной практикой использование изменяемого объекта, такого как List, в качестве ключа в HashMap.

Из этого ответа

Answer 2

Вы идете по опасной воде, так как ваши ключи изменчивы, прочитайте это, почему это не очень хорошая идея. Являются ли изменяемые ключи hashmap опасной практикой?,

Ну, один ваш пример показывает, почему это не очень хорошая идея. Вы добавляете 1 экземпляр ключа на свою карту, а затем модифицируете его, эффективно изменяя все пары ключ-значение в вашей хэш-карте.

Answer 3

Ваш первый фрагмент не работает, потому что вы мутируете так же Pair экземпляр, который уже служит ключом в HashMap, Это позволяет то же самое Pair экземпляр, чтобы появиться в качестве ключа в нескольких записях HashMap (так как новый hashCode вычисляется после изменения Pair Экземпляр сопоставлен с новым ведром HashMap который не содержит никакой записи) и эффективно сломать HashMap,

Вы не должны мутировать экземпляр, который служит ключом HashMap (если вы не удалите его из HashMap перед обновлением и поместите обновленную версию в Map потом).

Answer 4

В первом фрагменте кода вы фактически используете один и тот же ключевой объект для каждой записи карты. Вы просто изменяете его левое значение, но оно все еще указывает на тот же адрес памяти. Карта должна иметь уникальные ключи (каждый ключ должен указывать на другой адрес памяти), поэтому вам нужно поставить новый экземпляр пары для каждой записи карты.