What is a Hash Collision?
Learn what causes hash collisions, how chaining and open addressing resolve them, and their impact on lookup speed.
Expected Interview Answer
A hash collision occurs when two different keys are mapped by a hash function to the same bucket or index in a hash table, which is mathematically inevitable once the number of possible keys exceeds the table size (the pigeonhole principle).
Because a hash function maps a large or infinite key space down to a fixed number of buckets, collisions cannot be eliminated entirely, only handled well. Two main strategies exist: separate chaining, where each bucket holds a small list (or tree) of all keys hashing there, and open addressing, where a colliding key probes for the next free slot using a scheme like linear, quadratic, or double hashing. A good hash function distributes keys uniformly to keep the average chain length short, which is what keeps average-case lookup at O(1) even though the worst case (many keys colliding) is O(n).
- Understanding collisions explains hash table O(1) average vs O(n) worst case
- Chaining and open addressing are the two standard resolution strategies
- Load factor management keeps collisions rare and lookups fast
- Directly relevant to designing caches, dictionaries, and databases
AI Mentor Explanation
Imagine assigning every player a locker number by taking the last digit of their jersey number — players wearing 7 and 17 both land on locker 7, a collision. The equipment manager handles it by hanging a second hook inside locker 7 for the extra player’s gear, so both are still findable, just with one extra step to check the hook. This is exactly how separate chaining resolves a hash collision: extra items share the bucket in a small list instead of overwriting each other.
Step-by-Step Explanation
Step 1
Hash the key
Compute hash(key) and reduce it modulo the table size to get a bucket index.
Step 2
Detect the collision
If that bucket already holds a different key, a collision has occurred.
Step 3
Resolve via chaining
Append the new key to a list/tree at that bucket so both keys remain retrievable.
Step 4
Or resolve via open addressing
Probe subsequent slots (linear, quadratic, or double hashing) until a free slot is found.
What Interviewer Expects
- Clear statement that collisions are inevitable, not a bug, due to the pigeonhole principle
- Both resolution strategies explained: chaining and open addressing
- Discussion of load factor and resizing to keep collisions rare
- Correct average-case vs worst-case complexity distinction
Common Mistakes
- Believing a "perfect" hash function can avoid all collisions for an unbounded key space
- Confusing chaining with open addressing when describing resolution
- Ignoring load factor, leading to degraded O(n) performance under a poor hash function
- Not mentioning resizing/rehashing as a mitigation strategy
Best Answer (HR Friendly)
“A hash collision happens when two different pieces of data end up assigned to the same storage slot by a hash function. It is unavoidable in general, so hash tables are designed to handle it gracefully, either by storing a small list of colliding items together or by moving the newer item to another nearby slot.”
Code Example
class HashTable:
def __init__(self, size=8):
self.size = size
self.buckets = [[] for _ in range(size)]
def _index(self, key):
return hash(key) % self.size
def put(self, key, value):
bucket = self.buckets[self._index(key)]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value)) # collision handled via chaining
def get(self, key):
bucket = self.buckets[self._index(key)]
for k, v in bucket:
if k == key:
return v
raise KeyError(key)Follow-up Questions
- What is the difference between separate chaining and open addressing?
- What is load factor and why does it matter for hash table performance?
- How does double hashing reduce clustering compared to linear probing?
- Why can a hash table degrade to O(n) lookups in the worst case?
MCQ Practice
1. Why are hash collisions mathematically unavoidable in general?
When the key space exceeds the number of buckets, at least two keys must map to the same bucket.
2. In separate chaining, how is a collision resolved?
Separate chaining keeps a small collection (list or tree) of all keys that hash to the same bucket.
3. What is the worst-case time complexity for a hash table lookup when many keys collide into one bucket?
If all keys collide into a single bucket, lookup degrades to a linear scan of that bucket, O(n).
Flash Cards
What is a hash collision? — When two different keys hash to the same bucket/index in a hash table.
Name the two main collision resolution strategies. — Separate chaining (list/tree per bucket) and open addressing (probing for the next free slot).
Why are collisions unavoidable in general? — The pigeonhole principle: when the key space exceeds the table size, some keys must share a bucket.
What keeps average-case hash table lookup at O(1) despite collisions? — A well-distributed hash function combined with a managed load factor and resizing.