What you'll learn
Collisions are inevitable in any hash table. This module covers the two strategies for handling them — separate chaining and open addressing — and how resizing keeps a table fast as it fills.
By the end you'll be able to:
- Contrast separate chaining with open addressing
- Trace linear probing (and know about quadratic & double hashing)
- Explain when and why a hash table rehashes
Separate chaining
The approach from Module 14: each bucket holds a linked list (or small array) of all entries that hashed there. Lookups scan the short list in the bucket. Simple and robust — the table can even hold more entries than it has buckets — at the cost of extra pointers and cache misses.
Open addressing
The alternative: store every entry directly in the table, one per slot. On a collision, follow a probe sequence to find another open slot. The simplest is linear probing: just try the next slot, then the next, wrapping around with modulo.
Watch probing
| Probe strategy | Next slot | Trade-off |
|---|---|---|
Linear | (h + 1), (h + 2), … | Simple; but causes primary clustering |
Quadratic | (h + 1²), (h + 2²), … | Reduces clustering; can miss slots |
Double hashing | (h + 1·g), (h + 2·g), … | Best spread; uses a second hash g(key) |
Watch out
Load factor & rehashing
Both strategies slow down as the load factor α rises. The cure is rehashing: when α crosses a threshold (≈0.75 for chaining, lower for open addressing), allocate a bigger array — usually double — and re-insert every existing key (their bucket indices change because the capacity changed). Rehashing is O(n), but like dynamic-array resizing it's rare, so inserts stay amortized O(1).
In code
A minimal open-addressing set with linear probing:
class HashSet:
def __init__(self, capacity=8):
self.slots = [None] * capacity
self.cap = capacity
def _index(self, key):
i = hash(key) % self.cap
while self.slots[i] is not None and self.slots[i] != key:
i = (i + 1) % self.cap # linear probing
return i
def add(self, key):
self.slots[self._index(key)] = key
def contains(self, key):
return self.slots[self._index(key)] == keyRecap & quick check
Key takeaways
- Separate chaining: each bucket holds a list of colliding entries.
- Open addressing: entries live in the table; collisions probe for another slot.
- Linear probing is simple but clusters; quadratic and double hashing spread better.
- Open addressing needs a lower load factor and tombstones for deletion.
- Rehashing into a bigger array keeps the load factor low and operations amortized O(1).
Quick check
1. In separate chaining, each bucket holds:
2. Linear probing resolves a collision by:
3. Why does open addressing need a lower load factor than chaining?
4. What triggers rehashing?
Hash tables give O(1) average lookups but no order. Next we get order and O(log n) with the most important non-linear structure: the tree. Next up: Module 16 — Trees & Traversals.