Java HashMap 中的冲突解决

Collision resolution in Java HashMap

提问by user2938723

Java HashMapuses putmethod to insert the K/V pair in HashMap. Lets say I have used putmethod and now HashMap<Integer, Integer>has one entry with keyas 10 and valueas 17.

JavaHashMap使用put方法将 K/V 对插入到HashMap. 假设我使用了put方法，现在HashMap<Integer, Integer>有一个条目，分别key为 10 和value17。

If I insert 10,20 in this HashMapit simply replaces the the previous entry with this entry due to collision because of same key 10.

如果我在其中插入 10,20，HashMap由于相同的键 10，它会因为冲突而简单地用此条目替换前一个条目。

If the key collides HashMapreplaces the old K/V pair with the new K/V pair.

如果密钥冲突，则HashMap用新的 K/V 对替换旧的 K/V 对。

So my question is when does the HashMapuse Chaining collision resolution technique?

所以我的问题是什么时候HashMap使用链接碰撞解决技术？

Why it did not form a linkedlistwith key as 10 and value as 17,20?

为什么它没有形成一个linkedlist键为 10，值为 17,20 的键？

采纳答案by Sanjay T. Sharma

When you insert the pair (10, 17)and then (10, 20), there is technically no collision involved. You are just replacing the old value with the new value for a given key 10(since in both cases, 10 is equal to 10 and also the hash code for 10 is always 10).

当您插入一对(10, 17)然后 时(10, 20)，从技术上讲不涉及碰撞。您只是用给定键的新值替换旧值10（因为在这两种情况下，10 都等于 10，而且 10 的哈希码始终为 10）。

Collision happens when multiple keys hash to the same bucket. In that case, you need to make sure that you can distinguish between those keys. Chaining collision resolution is one of those techniques which is used for this.

当多个键散列到同一个存储桶时会发生冲突。在这种情况下，您需要确保可以区分这些键。链接冲突解决是用于此的技术之一。

As an example, let's suppose that two strings "abra ka dabra"and "wave my wand"yield hash codes 100and 200respectively. Assuming the total array size is 10, both of them end up in the same bucket (100 % 10and 200 % 10). Chaining ensures that whenever you do map.get( "abra ka dabra" );, you end up with the correct value associated with the key. In the case of hash map in Java, this is done by using the equalsmethod.

作为一个例子，让我们假设两个字符串"abra ka dabra"和"wave my wand"产量哈希码100和200分别。假设总数组大小为 10，它们最终都在同一个桶中（100 % 10和200 % 10）。链接确保无论何时执行map.get( "abra ka dabra" );，最终都会得到与键关联的正确值。在 Java 中的哈希映射的情况下，这是通过使用equals方法来完成的。

回答by Macondo2Seattle

There is no collision in your example. You use the same key, so the old value gets replaced with the new one. Now, if you used two keys that map to the same hash code, then you'd have a collision. But even in that case, HashMap would replace your value! If you want the values to be chained in case of a collision, you have to do it yourself, e.g. by using a list as a value.

您的示例中没有碰撞。您使用相同的键，因此旧值会被新值替换。现在，如果您使用映射到相同哈希码的两个键，则会发生冲突。但即使在这种情况下，HashMap 也会替换您的值！如果您希望在发生碰撞时链接值，您必须自己完成，例如使用列表作为值。

回答by yamafontes

It isn't defined to do so. In order to achieve this functionality, you need to create a map that maps keys to lists of values:

它没有被定义为这样做。为了实现此功能，您需要创建一个映射，将键映射到值列表：

Map<Foo, List<Bar>> myMap;

Or, you could use the Multimap from google collections / guava libraries

或者，您可以使用google collections/guava 库中的 Multimap

回答by iluxa

It could have formed a linked list, indeed. It's just that Mapcontract requires it to replace the entry:

它确实可以形成一个链表。只是Map合同要求它替换条目：

V put(K key, V value)

Associates the specified value with the specified key in this map (optional operation). If the map previously contained a mapping for the key, the old value is replaced by the specified value. (A map m is said to contain a mapping for a key k if and only if m.containsKey(k) would return true.)

V put(K key, V value)

将指定值与此映射中的指定键相关联（可选操作）。如果映射先前包含键的映射，则旧值将替换为指定值。（当且仅当 m.containsKey(k) 返回 true 时，才称映射 m 包含键 k 的映射。）

http://docs.oracle.com/javase/6/docs/api/java/util/Map.html

http://docs.oracle.com/javase/6/docs/api/java/util/Map.html

For a map to store lists of values, it'd need to be a Multimap. Here's Google's: http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html

对于存储值列表的映射，它需要是一个Multimap. 这是谷歌的：http: //google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html

A collection similar to a Map, but which may associate multiple values with a single key. If you call put(K, V) twice, with the same key but different values, the multimap contains mappings from the key to both values.

类似于 Map 的集合，但可以将多个值与单个键相关联。如果使用相同的键但不同的值调用 put(K, V) 两次，则多重映射包含从键到两个值的映射。

Edit: Collision resolution

编辑：碰撞解决方案

That's a bit different. A collision happens when two different keys happen to have the same hash code, or two keys with different hash codes happen to map into the same bucket in the underlying array.

那有点不同。当两个不同的键碰巧具有相同的哈希码，或者两个具有不同哈希码的键碰巧映射到底层数组中的同一个桶时，就会发生冲突。

Consider HashMap's source (bits and pieces removed):

考虑HashMap的来源（删除了点点滴滴）：

public V put(K key, V value) {
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    // i is the index where we want to insert the new element
    addEntry(hash, key, value, i);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    // take the entry that's already in that bucket
    Entry<K,V> e = table[bucketIndex];
    // and create a new one that points to the old one = linked list
    table[bucketIndex] = new Entry<>(hash, key, value, e);
}

For those who are curious how the Entryclass in HashMapcomes to behave like a list, it turns out that HashMapdefines its own static Entryclass which implements Map.Entry. You can see for yourself by viewing the source code:

对于那些好奇这个Entry类如何HashMap表现得像一个列表的人来说，事实证明它HashMap定义了自己的静态Entry类，它实现了Map.Entry. 你可以通过查看源代码自己看看：

GrepCode for HashMap

HashMap 的 GrepCode

回答by Guillaume Poussel

In a HashMapthe key is an object, that contains hashCode()and equals(Object)methods.

在一个HashMap键是一个对象，它包含hashCode()和equals(Object)方法。

When you insert a new entry into the Map, it checks whether the hashCodeis already known. Then, it will iterate through all objects with this hashcode, and test their equality with .equals(). If an equalobject is found, the new value replaces the old one. If not, it will create a new entry in the map.

当您在 Map 中插入新条目时，它会检查该条目是否hashCode已知。然后，它将遍历具有此哈希码的所有对象，并使用 测试它们的相等性.equals()。如果找到相等的对象，则新值将替换旧值。如果没有，它将在地图中创建一个新条目。

Usually, talking about maps, you use collisionwhen two objects have the same hashCodebut they are different. They are internally stored in a list.

通常，谈到贴图，当两个对象具有相同但不同时，您会使用碰撞hashCode。它们在内部存储在一个列表中。

回答by Rajarshee Mitra

First of all, you have got the concept of hashing a little wrong and it had been rectified by Mr. Sanjay.

首先，你对散列的概念有点错误，桑杰先生已经纠正了。

And yes, Java indeed implement a collision resolution technique. When two keys get hashed to a same value (as the internal array used is finite in size and at some point the hashcode() method will return same hash value for two different keys) at this time, a linked list is formed at the bucket location where all the informations are entered as an Map.Entry object that contains a key-value pair. Accessing an object via a key will at worst require O(n) if the entry in present in such a lists. Comparison between the key you passed with each key in such list will be done by the equals() method.

是的，Java 确实实现了冲突解决技术。当两个键被散列到相同的值时（因为使用的内部数组的大小是有限的，并且在某些时候 hashcode() 方法将为两个不同的键返回相同的散列值），此时，在存储桶处形成一个链表所有信息作为包含键值对的 Map.Entry 对象输入的位置。如果条目存在于这样的列表中，那么通过键访问对象最坏的情况是需要 O(n)。您传递的键与此类列表中的每个键之间的比较将由 equals() 方法完成。

Although, from Java 8 , the linked lists are replaced with trees (O(log n))

尽管从 Java 8 开始，链表被替换为树（O(log n)）

回答by Hutashan Chandrakar

There is difference between collision and duplication. Collision means hashcode and bucket is same, but in duplicate, it will be same hashcode,same bucket, but here equals method come in picture.

碰撞和重复之间有区别。碰撞意味着哈希码和桶是相同的，但在重复时，它将是相同的哈希码，相同的桶，但这里的 equals 方法出现在图片中。

Collision detected and you can add element on existing key. but in case of duplication it will replace new value.

检测到冲突，您可以在现有键上添加元素。但在重复的情况下，它将替换新值。

回答by developer

Your case is not talking about collision resolution, it is simply replacement of older value with a new value for the same key because Java's HashMapcan't contain duplicates (i.e., multiple values) for the same key.

你的情况是不是在谈论冲突解决，那简直是与相同的密钥的新值替换旧的价值，因为Java的HashMap不能包含重复（即多个值，对于相同的）关键。

In your example, the value 17 will be simply replaced with 20 for the same key 10 inside the HashMap.

在您的示例中，对于 HashMap 中的相同键 10，值 17 将简单地替换为 20。

If you are trying to put a different/new value for the same key, it is not the concept of collision resolution, rather it is simply replacing the old value with a new value for the same key. It is how HashMaphas been designed and you can have a look at the below API (emphasis is mine) taken from here.

如果您尝试为同一键放置不同的/新值，这不是冲突解决的概念，而是简单地用同一键的新值替换旧值。它是如何HashMap设计的，您可以从此处查看以下 API（重点是我的）。

public V put(K key, V value)

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.

public V put(K key, V value)

将指定值与此映射中的指定键相关联。如果映射先前包含键的映射，则旧值将被替换。

---

---

On the other hand, collision resolution techniques comes into play only when multiple keys end up with the same hashcode(i.e., they fall in the same bucket location) where an entry is already stored. HashMaphandles the collision resolution by using the concept of chaining i.e., it stores the values in a linked list (or a balanced tree since Java8, depends on the number of entries).

另一方面，冲突解决技术仅在多个键以相同的哈希码（即，它们位于相同的存储桶位置）结束时才发挥作用，其中条目已经存储。HashMap通过使用链接的概念来处理冲突解决，即，它将值存储在一个链表中（或自 Java8 以来的平衡树，取决于条目的数量）。

回答by RAKESH AKUTHOTA

When multiple keys end up in same hash code which is present in same bucket. When the same key has different values then the old value will be replaced with new value.

当多个键以相同的哈希码结束时，该哈希码出现在同一个桶中。当同一个键有不同的值时，旧值将被新值替换。

Liked list converted to balanced Binary tree from java 8 version on wards in worst case scenario.

在最坏的情况下，喜欢的列表在病房上从 java 8 版本转换为平衡二叉树。

Collision happen when 2 distinct keys generate the same hashcode() value. When there are more collisions then there it will leads to worst performance of hashmap.

当 2 个不同的键生成相同的 hashcode() 值时，就会发生冲突。当有更多冲突时，它将导致哈希图的性能最差。

Objects which are are equal according to the equals method must return the same hashCode value. When both objects return the same has code then they will be moved into the same bucket.

根据 equals 方法相等的对象必须返回相同的 hashCode 值。当两个对象返回相同的代码时，它们将被移动到同一个存储桶中。