为什么ArrayList不是HashMap中的关键字？ [英] why doesn't ArrayList as key in HashMap work?

问题描述

我试图在 HashMap 中使用 ArrayList 作为键，但是如果我将值添加到将列表设置为关键字后，列表将不再识别该列表。我已经为我的问题找到了一个解决方案，但这是一个丑陋的做法，下面是该问题的一些示例代码：

 的HashMap<对象，字符串> hm = new HashMap< Object，String>（）; 
 
列表< String> l = new ArrayList< String>（）; 
 hm.put（l，stuff）; 
 l.add（test）; //在将列表添加到散列映射后添加项目
 
 System.out.println（hm.get（l））; 
  

这将返回文本null，而

 的HashMap<对象，字符串> hm = new HashMap< Object，String>（）; 
 
列表< String> l = new ArrayList< String>（）; 
 l.add（test）; //在将列表添加到散列表之前添加项目
 hm.put（l，stuff）; 
 
 System.out.println（hm.get（l））; 
  

可以正常工作并返回stuff

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

解决方案

Short：因为键必须是不可变的，长：当你向地图添加一个键时，它的 hashCode（）方法用于确定条目被放入的存储区。在那个桶里 equals（）用于检查那个键是否已经存在。

现在 ArrayList 执行深度 equals（）和 hashCode（），所以如果你在之后使用它作为键修改列表，那么你最终会得到一个不同的桶或者对于 equals（）有不同的结果，而映射很可能不会找到它。

Edit

hashCode（） <> AbstractList ArrayList extends）：

  public int hashCode ）{
 int hashCode = 1; （E e：this）
 hashCode = 31 * hashCode +（e == null？0：e.hashCode（））; 
返回hashCode; 
 
 
 
 
 
 $ b 
正如你所看到的：如果列表为空，那么哈希码将为1否则哈希码将是别的东西（在你的情况下 31 *test.hashCode（））。因此，您很可能最终会看到另一个桶，这将失败。
 
 
 
 编辑2   
 
 
澄清 equals（）的不同结果：当然 equals（）应该返回如果列表用作关键字，并且仅用于查找 的列表包含相同顺序的相同元素，则为true。但是，如果在将它用作关键字后更改该列表，您可能会在不同情况下结束： 
 
 
 
 
虽然hashCode返回不同​​的值，但它可能会被映射到同一个存储桶（最糟糕的情况是，想象地图中只有一个存储桶）。在这种情况下，您最终会在列表中找到两个相同的键，尽管它们之前不相同。 
 
您可能不知道对列表所做的更改，因此可能不会使用即使您认为自己是查找的平等列表。
 
 
 
I am trying to use an ArrayList as a key in a HashMap, but if I add values to the list after setting the list as a key, the map won't recognize the list anymore. I have already found a solution for my problem, but it is an ugly way of doing it, here is some example code for the problem:
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));
this will return the text "null" while
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));
works fine and returns "stuff"

Does anyone know why this happens?
解决方案
Short: because keys must be immutable for hashmaps to work (at least their identity must be immutable) and lists aren't.

Long: when you add a key to a map its hashCode() method is used to determine the bucket the entry is put into. Inside that bucket equals() is used to check whether that key already exists in there. The same is true for lookups.

Now ArrayList does a deep equals() and hashCode() so if you alter the list after using it as key you'll end up in a different bucket or with a different outcome for equals() and the map most likely won't find it.

Edit

hashCode() implementation for AbstractList (which ArrayList extends):
public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;
}
As you can see: if the list is empty the hash code will be 1 otherwise the hash code will be something else (in your case 31 * "test".hashCode()). Thus you're likely to end up looking in a different bucket which will fail.

Edit 2 

Clarification on "different outcome for equals()": of course equals() should return true if the list used as a key and the list used for the lookup only contain equal elements in the same order. But if you change that list after using it as a key you might end up in different situations:


Although hashCode returns a different value it might get mapped to the same bucket (in the worst case think of only one bucket in the map). In that case you'd end up with two equal keys in the list although they weren't equal before.
You might not be aware of changes to the list and thus might not use an equal list for the lookup even if you think you are.


                        
这篇关于为什么ArrayList不是HashMap中的关键字？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！