Collision Handling
When two different keys produce the same hash index, a collision occurs. Good hash functions minimize collisions, but they can't be eliminated. We need strategies to handle them.
1. Separate Chaining
Each bucket (index) holds a linked list (or other structure) of key-value pairs. This is used by Java's HashMap (with trees for large buckets). Insert: O(1) average, worst-case O(n).
2. Open Addressing
Find another empty slot within the array when collision occurs. Variants:
- Linear probing – check next slot (i+1, i+2, ...). May cause clustering.
- Quadratic probing – check i+1², i+2², ...
- Double hashing – use a second hash function to compute step size.
Java's HashMap uses separate chaining with optimization: when a bucket becomes too large, it converts the linked list to a balanced tree for O(log n) operations.
Simple illustration of separate chaining:
// Each bucket is a LinkedList
LinkedList[] table = new LinkedList[capacity];
// Insert: compute index, if bucket null create list, then add entry
// Search: traverse bucket's list to find key
Two Minute Drill
- Collision handling methods: separate chaining and open addressing.
- Separate chaining: each bucket holds a list of entries. Used by Java HashMap.
- Open addressing: linear probing, quadratic probing, double hashing.
- Java's HashMap uses trees for large buckets to maintain performance.
- Choosing good hash function and load factor reduces collisions.
Need more clarification?
Drop us an email at career@quipoinfotech.com