Collision resolution in HashMap

Question

When we put key-value pair in HashMap this could happen the hashcode of two keys could be same then how in this condition storing and retrieval of key-value will be handled.

Update

What I understand so far is that if two object key has same hash code then both key objects will be stored in same bucket and when I will say get(key) then out of two objects with matching hashcode which element to fetch is decided by object.equals().

http://stackoverflow.com/questions/4980757/how-do-hashtables-deal-with-collisions — Nikolay Kuznetsov, Dec 07 '12 at 06:41
http://stackoverflow.com/questions/12945894/java-hashmap-confusion-about-collision-handling-and-the-get-method — Nikolay Kuznetsov, Dec 07 '12 at 06:42

score 9 · Accepted Answer · answered Dec 07 '12 at 06:41

9

When you want to retrieve some object from hashmap and there exists several objects with the same hashcode, java will call equals() to determine the right object.

That is why it is so important to override equals() when overriding hashCode().

answered Dec 07 '12 at 06:41

Andrew Logvinov

21,181
6
52
54

thanks for simple and clear answer but I still have confusion so can you please comment on update of my question – Sandeep Kumar Dec 07 '12 at 10:26
Yes, that's right. We will iterate over the list of keys in the bucket and call `equals()` on our key comparing it with each of them until we find a match. – Andrew Logvinov Dec 07 '12 at 10:31

score 3 · Answer 2 · answered Dec 07 '12 at 09:11

Each bucket is represented by a linked list, so there is no limit, other than heap space, on the number of entries in a bucket. There are fewer buckets than possible hashCode results, so multiple hash codes are mapped to the same bucket, not just keys with the same hashCode.

A hashCode() with many collisions, or a HashMap with too few buckets, can make some linked lists long. Good performance depends on short linked lists, because the final stage in a look up is a linear scan of one of the linked lists.

I agree with the previous answer that a match depends on both equals() and hashCode().

+1 for "There are fewer buckets than possible hashCode results, so multiple hash codes are mapped to the same bucket, not just keys with the same hashCode" — Atul, Jun 11 '13 at 16:04

Collision resolution in HashMap

2 Answers2