Hash Table
Turn the key into a slot number and go straight there. When two keys want the same slot, one of them walks forward until it finds space.
An empty table of 11 slots. Each key goes to slot key mod 11, and when that slot is taken it walks to the next free one.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 15, with their answers.
Slot 1 holds empty. What happens to 12?
Answer: Free, land here. Nothing is in the way, so the walk ends here.
Slot 1 holds 12. What happens to 23?
Answer: Taken, keep walking. 12 is already there, so 23 tries the next slot along.
Slot 2 holds empty. What happens to 23?
Answer: Free, land here. Nothing is in the way, so the walk ends here.
Slot 1 holds 12. What happens to 1?
Answer: Taken, keep walking. 12 is already there, so 1 tries the next slot along.
Slot 2 holds 23. What happens to 1?
Answer: Taken, keep walking. 23 is already there, so 1 tries the next slot along.
Slot 3 holds empty. What happens to 1?
Answer: Free, land here. Nothing is in the way, so the walk ends here.
Slot 1 holds 12. What happens to 34?
Answer: Taken, keep walking. 12 is already there, so 34 tries the next slot along.
Slot 2 holds 23. What happens to 34?
Answer: Taken, keep walking. 23 is already there, so 34 tries the next slot along.
Slot 3 holds 1. What happens to 34?
Answer: Taken, keep walking. 1 is already there, so 34 tries the next slot along.
Slot 4 holds empty. What happens to 34?
Answer: Free, land here. Nothing is in the way, so the walk ends here.
Slot 1 holds 12. What happens to 45?
Answer: Taken, keep walking. 12 is already there, so 45 tries the next slot along.
Slot 2 holds 23. What happens to 45?
Answer: Taken, keep walking. 23 is already there, so 45 tries the next slot along.
Slot 3 holds 1. What happens to 45?
Answer: Taken, keep walking. 1 is already there, so 45 tries the next slot along.
Slot 4 holds 34. What happens to 45?
Answer: Taken, keep walking. 34 is already there, so 45 tries the next slot along.
Slot 5 holds empty. What happens to 45?
Answer: Free, land here. Nothing is in the way, so the walk ends here.
How it runs, step by step
An empty table of 11 slots. Each key goes to slot key mod 11, and when that slot is taken it walks to the next free one.
An empty hash table with 11 slots. Keys will be inserted using key modulo 11, walking forward on a collision.
Next key: 12.
Moving on to key 12.
Insert 12. Its hash is 12 mod 11, which is slot 1.
Insert key 12. The hash of 12 is 1, so slot 1 is where the search starts.
Slot 1 is empty, so 12 goes here.
Probing slot 1, which holds empty. It is free.
12 is stored in slot 1.
Key 12 is now stored in slot 1.
Next key: 23.
Moving on to key 23.
Insert 23. Its hash is 23 mod 11, which is slot 1.
Insert key 23. The hash of 23 is 1, so slot 1 is where the search starts.
Slot 1 holds 12, not 23. Walk on to slot 2.
Probing slot 1, which holds 12. It does not match, so the probe moves on.
Slot 2 is empty, so 23 goes here.
Probing slot 2, which holds empty. It is free.
23 is stored in slot 2.
Key 23 is now stored in slot 2.
Next key: 1.
Moving on to key 1.
Insert 1. Its hash is 1 mod 11, which is slot 1.
Insert key 1. The hash of 1 is 1, so slot 1 is where the search starts.
Slot 1 holds 12, not 1. Walk on to slot 2.
Probing slot 1, which holds 12. It does not match, so the probe moves on.
Slot 2 holds 23, not 1. Walk on to slot 3.
Probing slot 2, which holds 23. It does not match, so the probe moves on.
Slot 3 is empty, so 1 goes here.
Probing slot 3, which holds empty. It is free.
1 is stored in slot 3.
Key 1 is now stored in slot 3.
Next key: 34.
Moving on to key 34.
Insert 34. Its hash is 34 mod 11, which is slot 1.
Insert key 34. The hash of 34 is 1, so slot 1 is where the search starts.
Slot 1 holds 12, not 34. Walk on to slot 2.
Probing slot 1, which holds 12. It does not match, so the probe moves on.
Slot 2 holds 23, not 34. Walk on to slot 3.
Probing slot 2, which holds 23. It does not match, so the probe moves on.
Slot 3 holds 1, not 34. Walk on to slot 4.
Probing slot 3, which holds 1. It does not match, so the probe moves on.
Slot 4 is empty, so 34 goes here.
Probing slot 4, which holds empty. It is free.
34 is stored in slot 4.
Key 34 is now stored in slot 4.
Next key: 45.
Moving on to key 45.
Insert 45. Its hash is 45 mod 11, which is slot 1.
Insert key 45. The hash of 45 is 1, so slot 1 is where the search starts.
Slot 1 holds 12, not 45. Walk on to slot 2.
Probing slot 1, which holds 12. It does not match, so the probe moves on.
Slot 2 holds 23, not 45. Walk on to slot 3.
Probing slot 2, which holds 23. It does not match, so the probe moves on.
Slot 3 holds 1, not 45. Walk on to slot 4.
Probing slot 3, which holds 1. It does not match, so the probe moves on.
Slot 4 holds 34, not 45. Walk on to slot 5.
Probing slot 4, which holds 34. It does not match, so the probe moves on.
Slot 5 is empty, so 45 goes here.
Probing slot 5, which holds empty. It is free.
45 is stored in slot 5.
Key 45 is now stored in slot 5.
5 keys in 11 slots, after 10 collisions. The fuller a table gets, the more it collides.
The table holds 5 keys in 11 slots after 10 collisions.
Remember
- O(1) is the expected cost, not a guarantee. A bad hash degrades it to a scan.
- The fuller the table, the longer the probe walks, so real tables grow before they fill up.
- Deleting must leave a marker, not a hole, or searches stop short of keys that are still there.
Topics covered
Related
Where this is used
LanguagesThe Python dict
Every dict in CPython, and with it every object's attributes and every module's globals, is an open-addressed table probed with i = (i * 5 + perturb + 1) & mask, where perturb starts as the whole hash and is shifted down five bits per step. That shifting is the interesting part: the first probe uses the low bits, but each further step folds in bits the mask had discarded, so two keys that collide at the start are pulled apart instead of walking the same path. A deleted key leaves DKIX_DUMMY behind in the index, which is this lesson's tombstone under another name.
Systems programmingSwiss tables in Go and Abseil
Go 1.24 replaced its map with the Swiss table layout Google had written for C++'s absl::flat_hash_map. The table is cut into groups of 8 slots, each group carrying a 64-bit control word whose 8 bytes hold the low 7 bits of their slot's hash, so one word comparison performs 8 probe steps at once and only the matching bytes cost a real key comparison. This only works because the entries are probed inside a flat array: the candidates sit next to each other, which separately allocated chain nodes never could.
DatabasesGROUP BY in ClickHouse
ClickHouse builds the hash tables behind aggregation and joins with open addressing and linear probing. The probe is the inner loop of the query, one lookup per row across billions of rows, so the number that decides the runtime is cache misses per lookup, and a colliding key one slot along is usually already inside the cache line just fetched. A chain pointer instead would be a second dependent load that the CPU cannot even begin until the first one comes back.
Java standard libraryjava.util.IdentityHashMap
The JDK class whose own javadoc calls it a simple linear-probe hash table compares keys by reference rather than by equals, so a probe step is one pointer comparison and the flat array pays off immediately. It is also the rare implementation that refuses tombstones: removing an entry shifts the later entries of its run back into the gap, so no marker is left to slow future probes. That shift is only possible because the probe path is linear - under quadratic or double hashing the entries of a run share no common path to slide along, which is what leaves those tables stuck with markers.
Why it works this way
A probe loop that stops only at an empty slot
Both loops above walk until they reach a slot they can stop at, and a table whose slots are all live keys offers none: lookup spins forever on a key that is absent, and insert spins forever on a key it cannot place. Nothing inside either loop can detect that, so the guarantee has to come from outside it - an open-addressed table is grown while at least one slot is still free, which makes the load factor a correctness rule and not only a speed one. Lookup runs out of stopping points sooner than insert, because it stops only at a genuinely empty slot and reads a marker as occupied, so a table churned by deletes can lose its last null while holding few live keys. The cheap guard is to bound each loop by the table size and treat exhaustion as a failure rather than a hang.
Why linear probing's clusters grow faster than you would guess
A run of L filled slots in a row absorbs any key whose home is one of those L slots, so the empty slot at the end of the run is L + 1 times more likely to be taken next than a lone empty slot is. Long runs therefore get longer, and two runs that touch merge into one much longer run. That is primary clustering, and it is the whole reason the other probe schemes exist: quadratic probing jumps 1, 4, 9 slots out to leave the cluster, and double hashing gives each key a stride of its own so two keys never share a path. Linear probing still wins often in practice, because its next slot is the next address in memory and several probe steps come free inside one cache line.
The stride must never be zero, and must not share a factor with the size
The 1 + key % (size - 1) in the double hashing line is not decoration. A stride of 0 probes the same slot forever, and a stride that shares a factor f with the table size only ever reaches size / f of the slots, so an insert can fail while most of the table is empty. A prime size makes every stride below it coprime automatically, which is why double hashing implementations nearly always use primes. Plain quadratic probing has the same coverage problem, and the usual fix is the triangular form home + step * (step + 1) / 2 on a power-of-two table, which is guaranteed to visit every slot exactly once.
A tombstone repairs lookup and quietly breaks insert
Once deletes leave markers, insert must not stop at the first marker and write there. The key may already be sitting further along the same probe path, and writing early leaves two copies of it, of which lookup will only ever find the first. The correct shape is to remember the first marker, keep probing until a genuinely empty slot proves the key is absent, and only then go back and use the remembered slot. The insert above takes the short cut for readability. Note what the correct version costs: even an insert that could have stopped at the first marker still walks the whole path to an empty slot, so it is the absence check that sets the price, not the write.
Read more
- Open addressingWikipedia
- Linear probingWikipedia
- Double hashingWikipedia
- Faster Go maps with Swiss TablesThe Go Blog · go.dev
- dictobject.c, the CPython dict implementationCPython · github.com
Next up
- Hash MapA hash table storing key-value pairs; the key picks the bucket and the value travels with it.
- Separate ChainingEach bucket holds a chain of colliding entries; a lookup hashes once and compares keys along that chain.
- Bloom FilterA probabilistic set: k hash functions set k bits; false positives possible, false negatives impossible.