CODEWITHSUNDEEP
javahashmaphash-collision
Mandar Kale
Mandar Kale

Reputation: 337

Hash code collision handling in collison chain

Let us consider HashMap, which employs separate chaining to resolve hashcode collisions.

If I have multiple entries, where hascode comes out to be same, the collision mechanism forms a linked-list chain of all those entries.

Now, lets consider a case, where such linked list is present as:

(K1,V1,->) (K2,V2, ->) (K7,V7,->) (K9,V9,)

Now a new entry is coming in, for which the hashcode is coming as same, and the key has same value as K7. Will it overwrite the existing value of K7?

Upvotes: 1

Views: 198

Answers (2)

Saurav Sahu
Saurav Sahu

Reputation: 13924

Definition of hashmap function public V put(K key, V value) explains about the resolve for hash-collision.

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.

Snippet of putVal() which is called by put()

633             if (p.hash == hash &&
634                 ((k = p.key) == key || (key != null && key.equals(k))))
635                 e = p;
...
652             if (e != null) { // existing mapping for key
653                 V oldValue = e.value;
654                 if (!onlyIfAbsent || oldValue == null)
655                     e.value = value;
656                 afterNodeAccess(e);
657                 return oldValue;
658             }

Upvotes: 0

Marko Topolnik
Marko Topolnik

Reputation: 200138

Yes, it will overwrite the value reference within the existing node that represents K7.

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/HashMap.java#655

Upvotes: 5

Related Questions