HashMap 中键的突变导致错误的结果 [英] Mutation of the keys in HashMap causes wrong results

问题描述

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

in my project I use HashMap in order to store some data, and I've recently discovered that when I mutate the keys of the HashMap, some unexpected wrong results may happen. For Example:

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) 为真.

我不明白为什么会这样，因为这两个对象是相等的并且具有相同的哈希码.有谁知道这是什么原因，以及是否有任何其他类似的结构允许密钥的突变?谢谢.

I cannot understand why it happens, referring to the fact that the two objects are equal and have the same hash-code. Do anyone know what is the cause of that, and if there is any other similar structure that allows mutation of the keys? Thanks.

推荐答案

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

Mutable keys are always a problem. Keys are to be considered mutable if the mutation could change their hashcode and/or the result of equals(). That being said, lists often generate their hashcodes and check equality based on their elements so they almost never are good candidates for map keys.

您的示例中有什么问题?添加键时，它是一个空列表，因此产生的哈希码与包含元素时不同.因此，即使键的哈希码和 list2 相同 更改键列表后，您也不会找到该元素.为什么?仅仅是因为地图在错误的存储桶中查找.

What is the problem in your example? When the key is added it is an empty list and thus produces a different hashcode than when it contains an element. Hence even though the hashcode of the key and list2 are the same after changing the key list you'll not find the element. Why? Simply because the map looks in the wrong bucket.

示例(简化):

让我们从几个假设开始:

Let's start with a few assumptions:

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

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

If you now add the empty list it gets inserted into bucket 0 due to its hashcode.

当您使用 list1 进行查找时，由于哈希码为 5，它将在存储桶 5 中查找.由于该存储桶为空，因此将找不到任何内容.

When you do the lookup with list1 it will look in bucket 5 due to the hashcode of 5. Since that bucket is empty nothing will be found.

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

The problem is that your key list changes its hashcode and thus should be put into a different bucket but the map doesn't know this should happen (and doing so would probably cause a bunch of other problems).

这篇关于HashMap 中键的突变导致错误的结果的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！