Skip to content
Tutorials Center
My learning

Topics

Lesson 53 of 225 ยท Hashing

Collision Handling

Learn how hash tables handle collisions in Python: separate chaining, linear and quadratic probing, double hashing, tombstones and resizing, with full implementations.

A hash table turns a key into a bucket number and stores the value there. The catch is simple arithmetic: there are far more possible keys than buckets, so two different keys will sometimes land in the same bucket. That event is a collision, and every real hash table needs a plan for it. The plan you choose decides how fast lookups stay, how much memory you waste, and how deletion works.

In this lesson you will meet the two big families of collision handling: chaining (each bucket holds a small collection) and open addressing (every key lives directly in the array, and a collision sends you to another slot). You will build both from scratch, see why deleting from an open-addressing table is tricky, and learn when and how a table resizes itself.

Why collisions are unavoidable

Imagine 10 pigeons and 7 pigeonholes: at least one hole must hold two pigeons. This is the pigeonhole principle. A table with 7 buckets can only hold distinct bucket numbers 0 to 6, so inserting an eighth key forces a collision no matter how clever the hash function is. Even with plenty of room, collisions appear sooner than most people expect (the birthday paradox): with 23 people in a room, two share a birthday more often than not.

Python Keys that share a bucket

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Keys 10, 24 and 17 all reduce to 3, and 5 and 12 both reduce to 5, so those buckets hold several keys while only one bucket holds a single key. Collisions are normal, not a bug. What matters is keeping them cheap.

Strategy 1: separate chaining

With separate chaining, each bucket stores a little list (the "chain") of all entries that hash there.

TEXT
index   bucket
  0     -> (14,'a')
  1     ->
  2     -> (9,'b') -> (16,'c') -> (2,'d')
  3     ->
  4     -> (11,'e')
  • Insert: hash the key, walk the chain; update if the key exists, otherwise append.
  • Lookup: hash the key, walk the chain comparing keys.
  • Delete: find the entry in the chain and remove it. Nothing else is affected.

If the table has m buckets and holds n entries, the average chain length is n / m. That ratio is the load factor, written ฮฑ. As long as ฮฑ stays below a small constant (we resize to keep it there), a chain has O(1) entries on average and every operation is O(1) on average.

Python A hash map with separate chaining

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the table doubled its bucket count whenever the load factor passed 1.0, and every entry was re-hashed because key % new_capacity gives different answers than key % old_capacity. Resizing costs O(n) but happens rarely, so inserts stay O(1) amortized (see amortized analysis).

Chaining is simple and forgiving. Its downsides are the extra memory for list objects and poor cache behavior, because chain entries are scattered in memory.

Strategy 2: open addressing

With open addressing there are no chains. Every entry lives directly in the array. If the slot you want is taken, you follow a deterministic probe sequence to the next candidate slot, and keep going until you find a free one. A lookup follows the same sequence and stops when it finds the key or reaches an empty slot (which proves the key is absent).

The table must never be full, so the load factor ฮฑ is always below 1, typically kept under 0.5 to 0.75.

Linear probing

Try h, then h + 1, h + 2, and so on, wrapping around the end:

TEXT
slot(i) = (h + i) mod m          i = 0, 1, 2, ...

insert 10 (h=3):  [ . . . 10 . . . ]
insert 17 (h=3):  [ . . . 10 17 . . ]     3 taken -> 4
insert 24 (h=3):  [ . . . 10 17 24 . ]    3, 4 taken -> 5
insert 4  (h=4):  [ . . . 10 17 24 4 ]    4, 5 taken -> 6

Linear probing is cache friendly (neighbors are adjacent in memory) but suffers from primary clustering: runs of occupied slots grow, and a new key that hashes anywhere into a run must walk to its end, which makes the run grow even faster.

Quadratic probing

Jump by growing steps: h, h + 1, h + 4, h + 9, ...

TEXT
slot(i) = (h + iยฒ) mod m

This breaks up primary clusters, but keys with the same starting slot still follow the same path (secondary clustering). Also, with an arbitrary m the sequence may visit only some slots and miss free ones. A prime m with ฮฑ under 0.5 guarantees a free slot is found; a power-of-two table works with the triangular offsets i(i+1)/2.

Double hashing

Use a second hash function to choose the step size, so different keys with the same start follow different paths:

TEXT
slot(i) = (h1(key) + i * h2(key)) mod m

h2 must never return 0, and it must be coprime with m so the sequence can reach every slot. A common recipe: m prime and h2 = 1 + key % (m - 1).

Python Three probe sequences for the same key

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Keys 25 and 36 both start at slot 3. Linear and quadratic probing then give both keys identical paths; double hashing sends them in different directions because their steps differ. That is exactly why double hashing has the least clustering.

Deleting from an open-addressing table

Here is the trap. Suppose keys A and B both hash to slot 3, so A sits at 3 and B at 4. If you delete A by simply emptying slot 3, a lookup for B starts at 3, sees an empty slot, concludes "B is absent" and stops. B is now unreachable.

The fix is a tombstone: instead of emptying the slot, mark it as "deleted". Lookups treat a tombstone as occupied-and-not-a-match and keep probing. Inserts may reuse the first tombstone they pass (after confirming the key is not further along).

Watch out: tombstones never go away on their own. A table full of tombstones makes every lookup walk long paths, even though few live entries exist. Count tombstones as part of the load, and rebuild the table (re-insert only live entries) when too many accumulate.

Python Open addressing with tombstones

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The x marks the tombstone. Key 19 is still found because the lookup walks past it, and the later insert of 27 reuses that slot. If delete wrote EMPTY instead, get(19) would return None.

Chaining versus open addressing

Separate chaining Open addressing
Memory Extra node/list per entry Entries stored in the array itself
Load factor Can exceed 1 Must stay below 1 (about 0.5 to 0.75)
Cache behavior Pointer chasing Good, especially linear probing
Deletion Easy Needs tombstones
Worst case One long chain, O(n) One long probe run, O(n)
Bad hash function Degrades gracefully Clusters badly

Python's own dict uses open addressing with a perturbed probe sequence (it mixes in the upper bits of the hash so patterns break up), plus a compact entries array that preserves insertion order. You can read about its API in dictionaries and sets in practice.

How load factor affects cost

For a successful lookup, the expected number of examined entries grows slowly while ฮฑ is small, then explodes as ฮฑ approaches 1 in open addressing. The experiment below inserts keys with a deterministic pseudo-random generator and counts probes for linear probing at several loads.

Python Probe counts as the table fills

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The counts creep up slowly (about 1.5 slots at half full, about 2.3 at three quarters) and then climb quickly (about 5.4 at 90% and about 11 at 97%). That curve is the reason open-addressing tables resize long before they are full. For chaining you would see the average chain length equal to ฮฑ.

Resizing: when and how

Whichever strategy you use, a table that keeps growing needs to grow its array:

  1. When ฮฑ passes a threshold (for example 0.7 for open addressing, 1.0 for chaining), allocate a new array about twice as large.
  2. Re-insert every live entry. You cannot copy slots over, because the bucket number depends on m.
  3. Throw the old array away. Tombstones vanish during this rebuild.

Doubling keeps the total cost of all resizes at O(n) for n inserts, so each insert is O(1) amortized. Some tables also shrink when they become sparse, which saves memory but must be done carefully to avoid repeatedly growing and shrinking around one threshold.

Common mistakes

  • Using key % m with a bad m. If m is a power of two and keys are multiples of 8, only every eighth bucket is used. Primes (or a good scrambling hash first) spread keys better. See hash functions.
  • Forgetting tombstones. Emptying a slot on delete silently breaks later lookups.
  • Not re-hashing on resize. Copying old slots into the bigger array puts entries where lookups will not find them.
  • Letting an open-addressing table fill up. Probing an almost-full table degrades to a linear scan, and a completely full one never finds an empty slot to stop at.
  • Comparing hash values instead of keys. Equal hashes do not imply equal keys; always confirm with == after the hash matches.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does a hash table always have to handle collisions?

    By the pigeonhole principle, a large key space mapped into a small set of buckets forces some keys to collide, even in a nearly empty table.
  2. 2. What is the load factor of a chained table with 12 entries and 8 buckets?

    Load factor = entries / buckets = 12 / 8 = 1.5. Chaining allows values above 1; open addressing does not.
  3. 3. In an open-addressing table, why can't you just set a deleted slot back to empty?

    Lookups stop at the first empty slot. If a deleted entry's slot becomes empty, keys stored later in the same probe path become unreachable. A tombstone keeps the path intact.
  4. 4. Which problem does double hashing reduce compared with linear probing?

    Linear (and quadratic) probing give keys with the same start the same path. Double hashing makes the step depend on the key, so paths differ and clusters are smaller.
  5. 5. After a hash table doubles its array, what must be done with the existing entries?

    The slot number depends on the table size (for example key % m), so each entry's position changes and every entry must be re-inserted.

Summary

  • Collisions are unavoidable (pigeonhole principle); good tables make them cheap, not impossible.
  • Chaining keeps a small list per bucket; load factor can exceed 1 and deletion is simple.
  • Open addressing stores entries in the array and follows a probe sequence: linear (cache friendly, primary clustering), quadratic (less clustering), double hashing (least clustering).
  • Deleting in open addressing needs tombstones; rebuild the table when they pile up.
  • Keep the load factor bounded by resizing: double the array and re-hash every entry, giving O(1) amortized inserts and O(1) average lookups.

Next: Hash Functions