[java] Collision resolution in Java HashMap

Java HashMap uses put method to insert the K/V pair in HashMap. Lets say I have used put method and now HashMap<Integer, Integer> has one entry with key as 10 and value as 17.

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

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

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

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

This question is related to java hashmap

The answer is


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.


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.

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


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

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

Usually, talking about maps, you use collision when two objects have the same hashCode but they are different. They are internally stored in a list.


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 HashMap can't contain duplicates (i.e., multiple values) for the same key.

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

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 HashMap has been designed and you can have a look at the below API (emphasis is mine) taken from here.

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.


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. HashMap handles 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).


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


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.

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.

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.


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.

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


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

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.)

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

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.

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):

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 Entry class in HashMap comes to behave like a list, it turns out that HashMap defines its own static Entry class which implements Map.Entry. You can see for yourself by viewing the source code:

GrepCode for HashMap