A HashMap handles collisions by allowing multiple key-value pairs to exist within the same bucket. When two different keys produce the same hash value, HashMap stores both entries in that bucket and uses the equals() method to identify the correct key during retrieval. Since Java 8, heavily populated buckets are converted into Red-Black Trees to improve lookup performance.
Key Points: • A collision occurs when multiple keys map to the same bucket. • HashMap uses both hashCode() and equals() to manage collisions. • Before Java 8, collisions were handled using Linked Lists. • From Java 8 onwards, large Linked Lists are converted to Red-Black Trees. • This approach maintains efficient search, insertion, and deletion operations.
What Is a Collision?
A collision happens when two different keys generate the same bucket index.
Example:
Key A → Bucket 5
Key B → Bucket 5
Although the keys are different, they end up in the same bucket.
How HashMap Handles a Collision
Step 1:
Calculate the hash code of the key.
Step 2:
Determine the bucket index.
Step 3:
Check whether the bucket already contains entries.
If the bucket is empty:
• Store the new entry.
If the bucket contains entries:
• Compare keys using equals(). • If the key already exists, update its value. • Otherwise add a new entry to the bucket.
Collision Handling Before Java 8
HashMap stored colliding entries as a Linked List.
Example:
Bucket 5
KeyA -> KeyB -> KeyC
During retrieval:
• HashMap traverses the Linked List. • equals() identifies the matching key.
Drawback:
As collisions increase, search performance degrades.
Time Complexity:
O(n)
Collision Handling in Java 8 and Later
When the number of entries in a bucket exceeds a threshold (8 by default), the Linked List is converted into a Red-Black Tree.
Example:
KeyB
/ \KeyA KeyC
Benefits:
• Faster searching • Better scalability • Improved performance during heavy collisions
Time Complexity:
O(log n)
Example: Suppose two keys generate the same hash code.
Code Example:
import java.util.HashMap;
import java.util.Map;
class Employee {
private int id;
Employee(int id) {
this.id = id;
}
@Override
public int hashCode() {
return 100;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (!(obj instanceof Employee)) {
return false;
}
Employee emp = (Employee) obj;
return this.id == emp.id;
}
}
public class Demo {
public static void main(String[] args) {
Map<Employee, String> map =
new HashMap<>();
map.put(new Employee(101), "John");
map.put(new Employee(102), "David");
System.out.println(map.size());
}
}Output:
2
Even though both objects return the same hash code, HashMap stores them separately because equals() determines they are different keys.
Role of hashCode() and equals()
hashCode():
• Determines the bucket location.
equals():
• Distinguishes keys within the same bucket.
Both methods are required for correct HashMap behavior.
Performance Summary
No Collision:
• put() → O(1) • get() → O(1)
Collision with Linked List:
• get() → O(n)
Collision with Red-Black Tree:
• get() → O(log n)
Why Java 8 Introduced Treeification?
Large Linked Lists could significantly slow down HashMap operations.
Converting them into Red-Black Trees:
• Improves lookup performance • Reduces worst-case complexity • Makes HashMap more efficient for large datasets
Interview Tip: A concise interview answer is:
"When a collision occurs, HashMap stores multiple entries in the same bucket. It uses hashCode() to locate the bucket and equals() to identify the correct key. Before Java 8, collisions were handled using Linked Lists. From Java 8 onwards, buckets containing many entries are converted into Red-Black Trees, improving lookup performance from O(n) to O(log n)."