ZERO / HERO
Looking for the next free seat

Hash Map Internals: Probing & Resizing

The analogy

Chaining keeps a little list on each page. Open addressing does something different: if your seat is taken, you walk to the next free seat and sit there. Fast, because everything stays in one tidy block of memory — but deleting someone leaves a hole that can break the trail for whoever came after them.

Visualizer

Probing for a free slot

step 1 / 10
0
1
2
3
4
5
6
7

8 slots. Open addressing stores entries directly in the table — no chains, no pointers, everything in one cache-friendly block.load factor 0.00

# open addressing with linear probing + tombstones
EMPTY, TOMB = object(), object()

def find_slot(table, key):
    i = hash(key) % len(table)
    while table[i] is not EMPTY:
        if table[i] is not TOMB and table[i][0] == key:
            return i                    # found
        i = (i + 1) % len(table)        # probe on
    return None

# deleting must leave a TOMB, never EMPTY,
# or later probes stop early and lose entries

# load factor > ~0.7 -> resize and rehash everything
Check yourself

Why does deletion in open addressing write a tombstone instead of clearing the slot?