HashMap 包含几个具有相同值的不同键？

Question

我所做的很简单：我想创建一个 HashMap<Pair, ArrayList<Integer>>，其中 Pair 作为键，ArrayList<Integer> 作为值。 Pair 是自定义的 class，包含元素 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 的声明放入 for 循环中。新的结果是我想要的如下：

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

为什么会这样？ Here 是一个类似的问题。但它仍然不同。

编辑：正如@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

在第一个代码片段中，您实际上为地图的每个条目使用了相同的键对象。你只是修改它的左值，但它仍然指向相同的内存地址。 Map 需要有唯一的键（每个键必须指向不同的内存地址）这就是为什么你需要为每个 map 条目放置新的 pair 实例。

Answer 2

您正在涉足危险的水域，因为您的密钥是可变的，请阅读为什么这不是一个好主意 - Are mutable hashmap keys a dangerous practice?。

好吧，你的例子本身就说明了为什么这不是一个好主意。您在映射中添加 1 个键实例，然后修改它，有效地修改哈希映射中的所有键值对。

Answer 3

您的第一个代码段不起作用，因为您正在改变已作为 HashMap 中的键的相同 Pair 实例。这允许相同的 Pair 实例作为键出现在 HashMap 的多个条目中（因为在您修改 Pair 实例后计算的新 hashCode 被映射到一个新的不包含任何条目的 HashMap 的桶）并有效地破坏 HashMap。

您不应该改变用作 HashMap 键的实例（除非您在更新它之前将其从 HashMap 中删除并将更新后的版本放入 Map稍后）。

Answer 4

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.

由此answer

HashMap 包含几个具有相同值的不同键？

HashMap contains several different keys having the same value?

java

arraylist

hashmap

mutable

immutability