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)都是正确的.

Note that both a.keySet().iterator().next().hashCode() == list2.hashCode() and a.keySet().iterator().next().equals(list2) are true.

我无法理解为什么会发生这种情况，指的是两个对象相等并且具有相同的哈希码的事实.有人知道这是什么原因吗?是否还有其他类似的结构允许更改密钥?谢谢.

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屋！