How does a Java HashMap behave when two keys collide?
Explain hashCode, equals, and what the bucket does when several keys land together.
Points worth saying
- hashCode picks the bucket. equals decides whether the key is the same.
- Equal keys must share a hash code, or the map will lose entries.
- A bucket that grows too far becomes a tree so lookup stays logarithmic.
A full answer
HashMap uses hashCode to choose a bucket, then walks that bucket with equals to find the key. If two different keys share a hash code, they live in the same bucket as separate entries. If two keys are equal, the second put replaces the value.
The contract that matters in an interview is the pair of methods. If equals returns true, hashCode must return the same number. If you break that, the map looks in the wrong bucket and get returns null for a key you just put.
A long collision chain used to be a linked list, which made lookup linear in the worst case. Modern HashMap turns a long bucket into a balanced tree, so a hostile or unlucky hash degrades to logarithmic time instead of linear time.
For a custom key, implement both methods from the same fields, and do not mutate those fields while the key is in the map. A key whose hash changes after insertion is stranded in the old bucket. If the map is shared across threads, use a concurrent map. HashMap itself does not make that promise.
Mark your progress
Create a practice profile to mark this question.