Collision Handling in Hash Indexes
You'll learn how hash indexes deal with the inevitable situation where two different keys produce the same hash value.
The Collision Problem
Even with a good hash function (like the ones you learned about in "Hash Function Selection for Indexes"), collisions are unavoidable. When two different keys hash to the same bucket location, the index must have a strategy to store both values without losing data.
Think of it like apartment mailboxes: if two tenants are mistakenly assigned the same box number, the building needs a system to ensure both still get their mail.
Common Collision Handling Techniques
Chaining is the most common approach in hash indexes. Each bucket contains not just one entry, but a linked list (or chain) of all key-value pairs that hash to that location. When searching, the index:
- Hashes the key to find the bucket
- Scans through the chain in that bucket to find the exact match
If a bucket's chain grows too long, performance degrades from O(1) toward O(n) for that bucket.
Open Addressing takes a different approach: when a collision occurs, the index probes for the next available bucket using a predetermined sequence. Common probing methods include:
- Linear probing: check the next bucket, then the next, etc.
- Quadratic probing: check buckets at increasing quadratic intervals
- Double hashing: use a second hash function to determine the probe sequence
Open addressing keeps everything in the main bucket array without external chains, but can suffer from clustering where collisions create "clumps" of filled buckets.
Real-World Impact
The collision handling method affects both read and write performance. Chaining is simpler and handles high load factors better, while open addressing uses cache more efficiently but requires careful management of deletions.
Key Takeaway: Hash indexes use chaining (linked lists per bucket) or open addressing (probing for alternative buckets) to handle collisions, each with distinct performance characteristics under different load conditions.