Introduction
A collision happens when two distinct keys are hashed to the same bucket index by the hash function. Since the number of possible keys is usually far greater than the number of buckets, collisions are inevitable (this follows from the pigeonhole principle). Collision handling strategies determine how a hash table stores multiple keys that land in the same bucket without losing data or breaking lookups.
Cricket analogy: When a stadium assigns seat numbers by taking a fan's ticket ID modulo the number of gates, two different fans can land at the same gate number — a collision — and since there are always more fans than gates, this is guaranteed by the pigeonhole principle.
How It Works
There are two main families of collision resolution: chaining and open addressing. In chaining, each bucket holds a small container (usually a linked list, or a balanced tree for very large buckets) of all key-value pairs that hashed to that index. In open addressing, all entries live directly inside the single bucket array itself; when a collision occurs, the algorithm probes (searches) for the next available slot using a defined sequence, such as linear probing, quadratic probing, or double hashing.
Cricket analogy: When two teams are scheduled for the same ground on the same date, one solution is to let both teams share the ground with a shifted time slot (like chaining, stacking both in one bucket), while another is to bump the second team to search sequentially for the next open ground nearby (like open addressing probing).
Explanation
Chaining is simple to implement and tolerates a high load factor gracefully, but it uses extra memory for list/node overhead and can suffer from poor cache locality since chain nodes may be scattered in memory. Open addressing keeps everything in one contiguous array, giving better cache performance, but it requires careful handling of deletions (using 'tombstone' markers, since removing an entry can break the probe sequence) and its performance degrades sharply as the load factor approaches 1, so it must be kept below a stricter threshold (often 0.7). Linear probing (checking index+1, +2, +3, ...) is fast but prone to 'primary clustering', where long runs of filled slots form. Quadratic probing (checking index+1^2, +2^2, +3^2, ...) spreads out probes to reduce primary clustering but can still suffer 'secondary clustering' for keys with the same initial hash. Double hashing uses a second hash function to compute the probe step size, giving the most uniform distribution of probes and the least clustering, at the cost of computing two hash functions per operation.
Cricket analogy: A ground that lets unlimited fans queue at one gate (chaining) handles overcrowding gracefully but creates long, scattered lines; a ground with strictly one fan per turnstile (open addressing) moves faster but must mark "vacated" turnstiles carefully so late arrivals don't misread an empty spot, and gets congested past 70% capacity.
Example
# Illustrating chaining manually with a list of buckets
class ChainingHashTable:
def __init__(self, size=8):
self.size = size
self.buckets = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def put(self, key, value):
idx = self._hash(key)
for i, (k, v) in enumerate(self.buckets[idx]):
if k == key:
self.buckets[idx][i] = (key, value) # update existing
return
self.buckets[idx].append((key, value)) # append on collision
def get(self, key):
idx = self._hash(key)
for k, v in self.buckets[idx]:
if k == key:
return v
raise KeyError(key)
table = ChainingHashTable(size=4)
table.put("a", 1)
table.put("e", 2) # may collide with 'a' in a small table
table.put("i", 3)
print(table.get("e"))
print(table.buckets) # collided keys sit together in the same bucket's list
# Illustrating linear probing (open addressing)
def linear_probe_insert(table, key, value):
size = len(table)
idx = hash(key) % size
for step in range(size):
probe = (idx + step) % size
if table[probe] is None:
table[probe] = (key, value)
return
raise Exception("Hash table is full")
probe_table = [None] * 8
linear_probe_insert(probe_table, "x", 10)
linear_probe_insert(probe_table, "y", 20)
print(probe_table)Complexity
With chaining, average-case insert/lookup/delete is O(1 + load factor), and it degrades gracefully even beyond load factor 1 (buckets simply hold more items), but worst case (all keys in one bucket) is O(n). With open addressing, average-case operations are O(1) when the load factor is kept low (typically under 0.7), but performance degrades quickly as the table fills up, and it becomes O(n) in the worst case or when the table is nearly full, since long probe sequences are needed to find an empty slot.
Cricket analogy: A gate that lets queues grow behind each turnstile handles even a sold-out match reasonably, with wait time scaling gently as crowds grow, though a single turnstile getting all the fans is a nightmare queue; a strictly one-fan-per-turnstile gate is fast when under 70% full but grinds to a crawl near capacity.
Key Takeaways
- Collisions are inevitable when the key space is larger than the number of buckets (pigeonhole principle).
- Chaining stores colliding keys in a list (or tree) per bucket; simple, and tolerates high load factors gracefully.
- Open addressing stores all entries in the array itself, probing for the next free slot on collision.
- Linear probing is simple but causes primary clustering; quadratic probing reduces this but adds secondary clustering; double hashing gives the most uniform spread.
- Open addressing needs tombstones for deletion and requires a lower load factor than chaining for good performance.
Practice what you learned
1. What is a collision in the context of hashing?
2. In separate chaining, how are colliding keys typically stored?
3. What problem is commonly associated with linear probing?
4. Why does open addressing require special handling (like tombstones) for deletions?
5. Which collision resolution technique typically achieves the most uniform distribution of probe sequences?
Was this page helpful?