Hash Collision HashMap Java
Fast recall
Quick revision
Core answer
HashMap keeps both entries and uses the stored hash plus equals() to find the requested key. Colliding entries begin as a linked list. In typical Java 8+ implementations, a sufficiently large bin in a table of at least 64 buckets can become a red-black tree. Good hash distribution keeps average operations O(1); tree bins improve many heavy-collision lookups, but do not make every possible worst case O(log n).Whether you understand separate chaining, the role of equals, and Java 8 treeification
Confusing 'same hashCode' with 'same bucket', or thinking a collision overwrites data
Distinguish hash collision (same bucket) from a key match (equals true) - only the latter overwrites
Interview-ready guide
Interview answer
A collision means two different keys select the same HashMap bucket.
They may have the same hash code, or different hashes may reduce to the same bucket index. The entries do not overwrite each other unless equals says they are the same logical key.
For example, two custom keys can deliberately return hash 42 while equals compares different names; both remain stored, and a lookup checks the hash and then equality inside that bucket. Collisions begin as a linked list.
In typical Java 8 and later implementations, a bin can become a red-black tree when it reaches the treeification threshold and the table is at least 64 buckets wide; below that capacity, HashMap normally resizes first. With good hash distribution, operations are O(1) on average.
Tree bins improve many heavy-collision lookups toward O(log m), where m is that bucket's size, but I would not promise O(log n) for every pathological key set because keys with identical hashes and no comparison order may require broader searching. The practical rule is to implement consistent equals and hashCode and make the hash distribute keys well.
Hash Collision HashMap Java
Direct Answer
A collision happens when different keys map to the same bucket. HashMap keeps both entries and uses the stored hash plus equals() to find the requested key. Colliding entries begin as a linked list. In typical Java 8+ implementations, a sufficiently large bin in a table of at least 64 buckets can become a red-black tree. Good hash distribution keeps average operations O(1); tree bins improve many heavy-collision lookups, but do not make every possible worst case O(log n).
Code Example
// Two DIFFERENT keys deliberately sharing a hashCode -> collision
class BadKey {
final String name;
BadKey(String n) { name = n; }
public int hashCode() { return 42; } // everyone collides!
public boolean equals(Object o) {
return o instanceof BadKey b && b.name.equals(name);
}
}
Map<BadKey, Integer> m = new HashMap<>();
m.put(new BadKey("a"), 1); // bucket 42
m.put(new BadKey("b"), 2); // SAME bucket -> chained, both kept
System.out.println(m.get(new BadKey("a"))); // 1 - equals finds it in the chain
// All keys in one bucket => lookups degrade toward O(n)/O(log n).
Common Mistakes & Pitfalls
- Collision means data loss: both unequal keys remain in the bucket.
- Same hash means same key:
equals()decides logical equality. - Ignoring table capacity: a long bin in a small table is normally handled by resizing, not immediate treeification.
- Promising O(log n) for every collision case: tree bins help, but the safe public complexity statement is O(1) average.
- Constant hash code: it puts every key into one bucket and destroys normal performance.
Check your understanding
Answer these without looking back at the article.
- What happens if you only override hashCode but not equals?
- What is the default load factor of HashMap?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.