Java - 关于碰撞处理和 get() 方法的 HashMap 混淆
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12945894/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java - HashMap confusion about collision handling and the get() method
提问by Slims
I'm using a HashMapand I haven't been able to get a straight answer on how the get()method works in the case of collisions.
我正在使用 aHashMap并且我无法直接回答该get()方法在发生碰撞的情况下如何工作。
Let's say n > 1objects get placed in the same key. Are they stored in a LinkedList? Are they overwritten so that only the last object placed in that key exists there anymore? Are they using some other collision method?
假设n > 1对象被放置在同一个key 中。它们存储在LinkedList? 它们是否被覆盖，以便只有放置在该键中的最后一个对象不再存在？他们是否使用其他碰撞方法？
If they are placed in a LinkedList, is there a way to retrieve that entire list? If not, is there some other built in map for Javain which I can do this?
如果它们放在 a 中LinkedList，有没有办法检索整个列表？如果没有，是否还有其他一些内置的Java地图可以在其中执行此操作？
For my purposes, separate chaining would be ideal, as if there are collisions, I need to be able to look through the list and get information about all the objects in it. What would be the best way to do this in Java?
就我的目的而言，单独的链接将是理想的，就好像存在冲突一样，我需要能够查看列表并获取有关其中所有对象的信息。在Java 中执行此操作的最佳方法是什么？
Thanks for all your help!
感谢你的帮助！
回答by GreyBeardedGeek
The documentation for Hashmap.put()clearly states, "Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced"
Hashmap.put()的文档明确指出，“将指定值与此映射中的指定键相关联。如果映射先前包含该键的映射，则旧值将被替换”
If you would like to have a list of objects associated with a key, then store a list as the value.
如果您想拥有与键关联的对象列表，则将列表存储为值。
Note that 'collision' generally refers to the internal working of the HashMap, where two keys have the same hash value, not the use of the same key for two different values.
请注意，“碰撞”通常是指 HashMap 的内部工作，其中两个键具有相同的哈希值，而不是对两个不同的值使用相同的键。
回答by Louis Wasserman
Are they overwritten so that only the last object placed in that key exists there anymore?
它们是否被覆盖，以便只有放置在该键中的最后一个对象不再存在？
Yes, assuming you're putting multiple values with the same key (according to Object.equals, not Object.hashCode.) That's specified in the Map.putjavadoc:
是的，假设您使用相同的键放置多个值（根据Object.equals，而不是Object.hashCode。）这是在Map.putjavadoc 中指定的：
If the map previously contained a mapping for the key, the old value is replaced by the specified value.
如果映射先前包含键的映射，则旧值将替换为指定值。
If you want to map a key to multiple values, you're probably better off using something like Guava's ListMultimap, ArrayListMultimapin specific, which maps keys to lists of values. (Disclosure: I contribute to Guava.) If you can't tolerate a third-party library, then really you have to have a Map<Key, List<Value>>, though that can get a bit unwieldy.
如果你想将一个键映射到多个值，你可能最好使用像 Guava's 之类的东西ListMultimap，ArrayListMultimap具体来说，它将键映射到值列表。（披露：我为 Guava 做出了贡献。）如果你不能容忍第三方库，那么你真的必须拥有一个Map<Key, List<Value>>，尽管这可能会变得有点笨拙。
回答by Jigar Joshi
Let's say n > 1 objects get placed in the same key. Are they stored in a linked list? Are they overwritten so that only the last object placed in that key exists there anymore? Are they using some other collision method?
假设 n > 1 个对象被放置在同一个键中。它们存储在链表中吗？它们是否被覆盖，以便只有放置在该键中的最后一个对象不再存在？他们是否使用其他碰撞方法？
There could be single instance for the same key so the last one overrides the prior one
同一个键可能只有一个实例，所以最后一个会覆盖前一个
Map<String, Integer> map = new HashMap<String, Integer>();
map.put("a", 1);
map.put("a", 2);// it overrides 1 and puts 2 there
chaining comes where there turns the same hash for different keys
链接来自不同键的相同哈希值
See
看
回答by sgroh
Cite: "Let's say n > 1 objects get placed in the same key. Are they stored in a linked list? Are they overwritten so that only the last object placed in that key exists there anymore? Are they using some other collision method?"
引用：“假设 n > 1 个对象被放置在同一个键中。它们是否存储在链表中？它们是否被覆盖，以便只有放置在该键中的最后一个对象不再存在？它们是否使用了其他碰撞方法？”
Yes, if the hashmap contained something under this key, it will override it.
是的，如果哈希映射在此键下包含某些内容，它将覆盖它。
You can implement your own class to handle that or more simple use a HashMap> in where K is your Key Object and V the object value. Have in mind that with last solution when you do a map.get(K) will retrieve a List or the implementation that you choose (i.e: ArrayList) so all the methods of this implementation are available for you and perhaps fulfils your requirements. For example if you used Arraylist you have the size, trimToSize, removeRange, etc.
您可以实现自己的类来处理该问题，或者更简单地使用 HashMap>，其中 K 是您的关键对象，V 是对象值。请记住，当您执行 map.get(K) 时，最后一个解决方案将检索一个列表或您选择的实现（即：ArrayList），因此该实现的所有方法都可供您使用，并且可能满足您的要求。例如，如果您使用 Arraylist，则您有大小、trimToSize、removeRange 等。
回答by Larsen
collision resolution for hashing in java is not based on chaining. To my understanding, JDK uses double hashing which is one of the best way of open addressing. So there's no list going to be associated with a hash slot.
java中散列的冲突解决不是基于链接。据我了解，JDK 使用双散列，这是最好的开放寻址方式之一。所以没有列表将与哈希槽相关联。
You might put the objects for which the hash function resolves to the same key can be put in list and this list can be updated in the table/map.
您可以将散列函数解析为相同键的对象放在列表中，并且可以在表/映射中更新此列表。
package hashing;
import java.util.HashMap;
import java.util.Map;
public class MainAnimal {
/**
* @param args
*/
public static void main(String[] args) {
Animal a1 = new Animal(1);
Animal a2 = new Animal(2);
Map<Animal, String> animalsMap = new HashMap<Animal, String>();
animalsMap.put(a1,"1");
animalsMap.put(a2,"2");
System.out.println(animalsMap.get(a1));
Map<String, Integer> map = new HashMap<String, Integer>();
map.put("a", 1);
map.put("a", 2);// it overrides 1 and puts 2 there
System.out.println(map.get("a"));
}
}
class Animal {
private int index = 0;
Animal(int index){
this.index = index;
}
public boolean equals(Object obj){
if(obj instanceof Animal) {
Animal animal = (Animal) obj;
if(animal.getIndex()==this.getIndex())
return true;
else
return false;
}
return false;
}
public int hashCode() {
return 0;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
}
In the above code, am showing two different things.
在上面的代码中，我展示了两个不同的东西。
case 1 - two different instances resolving to same hashkey case 2 - two same instances acting as keys for two different entries.
case 1 - 两个不同的实例解析为相同的 hashkey case 2 - 两个相同的实例充当两个不同条目的键。
Animal instances, a1 & a2 resolves to same key. But they are not overriden. Hashing mechanism probes through the hash slots and places the entries on different slots.
动物实例，a1 和 a2 解析为相同的键。但它们不会被覆盖。散列机制探测散列槽并将条目放在不同的槽上。
with the second case, keys resolve to same hash key and also the equals method satisfies. Hence overriding happens.
对于第二种情况，键解析为相同的散列键，并且满足 equals 方法。因此发生覆盖。
Now if in the animal class I override the equals method this way -
现在，如果在动物类中我以这种方式覆盖了 equals 方法 -
public boolean equals(Object obj){
// if(obj instanceof Animal) {
// Animal animal = (Animal) obj;
// if(animal.getIndex()==this.getIndex())
// return true;
// else
// return false;
// }
// return false;
return true;
}
Overriding happens. The behavior is like using same instance. Since a1 and a2 are in the same bucket and equals return true as well.
发生覆盖。行为就像使用相同的实例。由于 a1 和 a2 在同一个桶中并且 equals 也返回 true。
