Collisions, Chaining and Probing
26 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Two different keys can want the same slot. The table must keep both and still find each one. There are two standard answers: let a slot hold a list, or move to another free slot. Both keep lookups fast while the table stays lightly filled.
Collisions are normal
A collision happens when two different keys map to the same slot. Every hash table must store both keys and still find each one.
A table of 8 slots cannot give 9 keys their own slot. Even with fewer keys, two often share one. Keys 3, 11 and 19 all give slot 3 when the size is 8. A table must handle this.
for key in [3, 11, 19, 6]: print(key, "-> slot", key % 8)Example 1 · Table size changes how keys spread
keys = [0, 8, 16, 24, 32]for size in (8, 7): used = {key % size for key in keys} print("size", size, "-> slots used:", len(used))size 8 -> slots used: 1 size 7 -> slots used: 5
What this code does
- Every key is a multiple of 8, so with 8 slots all five land in slot 0.
- With 7 slots they spread over five different slots. This is why many tables use a prime size, or mix the bits of the hash first.
Three different keys want slot 3. Throwing a key away is not allowed, so the table needs a plan for the second and third key. There are two main plans: chaining and probing.
Chaining: keep a list in each slot
Chaining is a collision strategy where each slot holds a list of all the keys that map to it. Lookup walks only that list.
Chaining lets a slot hold several keys. Each bucket is a list, and the keys that collide simply sit in the same list. A lookup finds the bucket, then compares keys one by one.
buckets = [[] for _ in range(8)]for key in [3, 11, 19, 6]: buckets[key % 8].append(key)print([len(b) for b in buckets])Example 2 · Chain lengths
keys = [3, 11, 19, 6, 14, 22, 30, 1]buckets = [[] for _ in range(8)]for key in keys: buckets[key % 8].append(key)print([len(b) for b in buckets])print("longest chain:", max(len(b) for b in buckets))print(buckets[6])[0, 1, 0, 3, 0, 0, 4, 0] longest chain: 4 [6, 14, 22, 30]
What this code does
- Eight keys in eight buckets is an average of one per bucket, but the spread is uneven.
- Slot 6 holds four keys, so a lookup there may compare four times. The average stays small while the worst bucket does not.
The cost of a lookup is one step to find the bucket plus the length of the chain. Short chains mean fast lookups. If every key lands in one bucket, the table becomes one long list and costs linear time.
Linear probing: use the next free slot
Linear probing is an open addressing method that, after a collision, checks the next slot, then the next, wrapping around, until a free slot or the key is found.
Open addressing stores keys in the table itself, with no lists. If a slot is taken, step to the next slot, and the next, until a free one appears. Wrap around at the end with %.
def put(slots, key): i = key % len(slots) while slots[i] is not None: if slots[i] == key: return i = (i + 1) % len(slots) slots[i] = key
slots = [None] * 8for key in [3, 11, 19, 6]: put(slots, key)print(slots)Example 3 · Linear probing insert
def put(slots, key): i = key % len(slots) while slots[i] is not None: if slots[i] == key: return i = (i + 1) % len(slots) slots[i] = key
slots = [None] * 8for key in [3, 11, 19, 6, 14]: put(slots, key)print(slots)[None, None, None, 3, 11, 19, 6, 14]
What this code does
- 3 takes slot 3, 11 slot 4 and 19 slot 5. Key 6 has its own slot 6.
- Key 14 also wants slot 6, so it moves on to slot 7. Equal keys stop early, so a key is never stored twice.
Example 4 · Counting probes in a lookup
def put(slots, key): i = key % len(slots) while slots[i] is not None: if slots[i] == key: return i = (i + 1) % len(slots) slots[i] = key
def find(slots, key): i = key % len(slots) probes = 1 while slots[i] is not None: if slots[i] == key: return True, probes i = (i + 1) % len(slots) probes += 1 return False, probes
slots = [None] * 8for key in [3, 11, 19, 6, 14]: put(slots, key)for key in [3, 19, 14, 27, 1]: print(key, find(slots, key))3 (True, 1) 19 (True, 3) 14 (True, 2) 27 (False, 6) 1 (False, 1)
What this code does
- Key 19 needs three probes: slots 3, 4 and 5. A key that is missing is found out when an empty slot appears.
- Key 27 starts at slot 3 and walks the run 3 to 7 before slot 0 is empty. Long runs make misses slow, so tables should never get too full.
Key 3 takes slot 3. Key 11 finds slot 3 taken and moves to slot 4. Key 19 goes to slot 5. To look up a key, start at its home slot and follow the same steps until you find it or reach an empty slot.
Deleting from a probed table
A tombstone is a special marker left in a slot after a delete in open addressing, so that lookups keep probing past it instead of stopping early.
Deleting is tricky with probing. If you set a slot back to empty, a lookup that needs to pass through it stops too early and misses keys stored further along. Leave a marker instead.
DELETED = object()def remove(slots, key): i = key % len(slots) while slots[i] is not None: if slots[i] == key: slots[i] = DELETED return True i = (i + 1) % len(slots) return FalseExample 5 · Why a plain empty marker breaks lookups
def put(slots, key): i = key % len(slots) while slots[i] is not None: if slots[i] == key: return i = (i + 1) % len(slots) slots[i] = key
def find(slots, key): i = key % len(slots) probes = 1 while slots[i] is not None: if slots[i] == key: return True, probes i = (i + 1) % len(slots) probes += 1 return False, probes
slots = [None] * 8for key in [3, 11, 19]: put(slots, key)slots[4] = None # wrong: forget key 11 without a markerprint("after wrong delete:", find(slots, 19)[0])slots[4] = "DELETED" # right: a tombstone keeps the run unbrokenprint("with tombstone:", find(slots, 19)[0])after wrong delete: False with tombstone: True
What this code does
- Key 19 sits in slot 5 because it passed slots 3 and 4. Emptying slot 4 cuts the path, and the search stops there.
- A tombstone is not None, so the search continues to slot 5 and finds 19.
Lookups treat the marker as occupied and keep going. Inserts may reuse it. CPython uses a similar idea and a smarter step than +1, which avoids long runs of full slots called clusters.
Next step
Check your understanding
11 quick questions