java - 为什么 ArrayList 作为 HashMap 中的键不起作用？

Question

我尝试使用ArrayList作为HashMap中的键，但是如果我在将列表设置为键后向列表中添加值，则映射会获胜不再认识该列表了。我已经找到了解决我的问题的方法，但这是一种丑陋的方法，这里是该问题的一些示例代码:

HashMap<Object,String> hm = new HashMap<Object,String>();

List<String> l = new ArrayList<String>();
hm.put(l, "stuff");
l.add("test");//add item after adding the list to the hashmap

System.out.println(hm.get(l));

这将返回文本“null”，而

HashMap<Object,String> hm = new HashMap<Object,String>();

List<String> l = new ArrayList<String>();
l.add("test"); //add item before adding the list to the hashmap
hm.put(l, "stuff");

System.out.println(hm.get(l));

工作正常并返回“东西”

有人知道为什么会发生这种情况吗？

Answer 1

简短:因为键必须是不可变的，散列图才能工作(至少它们的身份必须是不可变的)，而列表则不然。

Long:当您向映射添加键时，其 hashCode() 方法用于确定将条目放入的存储桶。在该存储桶内，equals() 用于检查该 key 是否已存在于其中。查找也是如此。

现在 ArrayList 执行深度 equals() 和 hashCode()，因此如果您在之后更改列表使用它作为键，您最终会进入不同的存储桶，或者 equals() 得到不同的结果，并且 map 很可能找不到它。

编辑

hashCode() AbstractList 实现(ArrayList 扩展):

public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;
}

如您所见:如果列表为空，则哈希代码将为 1，否则哈希代码将为其他内容(在您的情况下 31 * "test".hashCode())。因此，您可能最终会寻找不同的存储桶，但最终会失败。

编辑2

澄清“equals() 的不同结果”:当然，如果列表用作键且列表用于查找，equals() 应该返回 true 仅包含相同顺序的相等元素。但是，如果您在使用该列表作为 key 后更改该列表，您可能会遇到不同的情况:

• 虽然 hashCode 返回不同的值，但它可能会映射到同一个存储桶(在最坏的情况下，考虑映射中只有一个存储桶)。在这种情况下，您最终会在列表中得到两个相等的键，尽管它们之前并不相等。
• 您可能不知道列表的更改，因此即使您认为自己知道，也可能不会使用相等的列表进行查找。