AlgoScope

Hash Table

structureintermediateTime O(1)Space O(n)

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.

01234551662778910

A table of 11 slots. Remove 16.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 2, with their answers.

  1. Slot 5 holds 5. What does the search do?

    • Found it
    • Keep walking
    • Not here

    Answer: Keep walking. A different key means a collision happened, so the probe walks on.

  2. Slot 6 holds 16. What does the search do?

    • Found it
    • Keep walking
    • Not here

    Answer: Found it. The slot holds exactly the key being looked for.

How it runs, step by step

  1. A table of 11 slots. Remove 16.

    A hash table with 11 slots. Deleting key 16.

  2. Delete 16. Its hash is 16 mod 11, which is slot 5.

    Delete key 16. The hash of 16 is 5, so slot 5 is where the search starts.

  3. Slot 5 holds 5, not 16. Walk on to slot 6.

    Probing slot 5, which holds 5. It does not match, so the probe moves on.

  4. Slot 6 holds 16. Found it after 2 probes.

    Probing slot 6, which holds 16. It matches key 16.

  5. 16 is gone, but slot 6 is not emptied. It is marked as a removed key, because a real hole here would cut short every search that walks through this slot.

    Key 16 is removed from slot 6. The slot is marked as previously used rather than emptied, so probe chains through it stay intact.

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

Next up