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)正确的。

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

Answer 1

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

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

示例（简化）：

让我们从一些假设开始：

• 空列表返回哈希码 0
• 如果列表包含元素 5，则返回哈希码 5
• 我们的地图有 16 个桶（默认）
• 桶索引由 hashcode % 16 （我们桶的数量）决定

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

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

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