java - HashMap 中键的突变会导致错误的结果

Question

在我的项目中，我使用HashMap来存储一些数据，最近我发现当我改变HashMap的键时，可能会发生一些意想不到的错误结果。例如:

HashMap<ArrayList,Integer> a = new HashMap<>();
ArrayList list1 = new ArrayList<>();
a.put(list1, 1);
System.out.println(a.containsKey(new ArrayList<>())); // true
list1.add(5);
ArrayList list2 = new ArrayList<>();
list2.add(5);
System.out.println(a.containsKey(list2)); // false

请注意，a.keySet().iterator().next().hashCode() == list2.hashCode() 和 a.keySet().iterator() .next().equals(list2) 为 true。

我无法理解为什么会发生这种情况，因为这两个对象相等并且具有相同的哈希码。有谁知道这是什么原因，以及是否有任何其他类似的结构允许 key 突变？谢谢。

Answer 1

可变键始终是一个问题。如果突变可以改变键的哈希码和/或equals()的结果，则键被认为是可变的。话虽这么说，列表通常会生成哈希码并根据其元素检查相等性，因此它们几乎永远不会成为映射键的良好候选者。

你的例子有什么问题？添加键时，它是一个空列表，因此会生成与包含元素时不同的哈希码。因此，即使在更改键列表后，键和 list2 的哈希码相同，您也找不到该元素。为什么？仅仅是因为 map 看起来在错误的存储桶中。

示例(简化):

让我们从一些假设开始:

• 空列表返回哈希码 0
• 如果列表包含元素 5，则返回哈希码 5
• 我们的 map 有 16 个桶(默认)
• 存储桶索引由哈希码 % 16(我们的存储桶数量)决定

如果您现在添加空列表，由于其哈希码，它会被插入到存储桶 0 中。

当您使用 list1 进行查找时，由于哈希码为 5，它将在存储桶 5 中查找。由于该存储桶为空，因此什么也找不到。

问题是您的 key 列表更改了其哈希码，因此应该放入不同的存储桶中，但 map 不知道应该发生这种情况(这样做可能会导致一堆其他问题)。