为什么ArrayList不作为HashMap的关键工作？

Question

我试图ArrayList在a中使用a 作为键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()中用于检查那个密钥是否已存在于那里.查找也是如此.

现在ArrayList做得很深equals(),hashCode()所以如果你在使用它作为键后更改列表,你将最终在一个不同的桶或具有不同的结果,equals()并且地图很可能找不到它.

编辑

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 .但是如果在将其用作关键字后更改该列表,则可能会在不同的情况下结束:

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