Open Addressing Hash Table: The Strategy That Skips the Linked List

You have a hash table. Two keys hash to the same slot. Now what?

Most textbooks show a linked list dangling off each bucket. Clean diagram. Makes sense on the first read. But open the source for Python's dict, Go's map, or Ruby's Hash and you will not find a linked list anywhere near them. They store every key directly inside the array itself, no external nodes, no pointer chasing.

That's open addressing. And since you use Python dictionaries roughly six hundred times a day, you've been running this algorithm your whole career without knowing it.

Chaining Puts the Overflow Elsewhere. Open Addressing Doesn't.

In separate chaining, each array slot holds a pointer to a linked list. Colliding keys pile into that list. The array is just a directory. The actual data lives scattered across the heap in a constellation of tiny allocations.

Open addressing stores every key directly inside the table array. No linked lists. No pointers to external nodes. When a collision happens, the table probes for another open slot within the same array and puts the key there.

One constraint falls out of this immediately: the table can never hold more entries than slots. You cannot exceed 100% capacity because there is nowhere else to go. That sounds limiting, but it forces the entire data structure into a single contiguous block of memory. CPUs love that more than almost anything.

Linear Probing: When in Doubt, Try the Next Slot

The most intuitive probing strategy has a name that describes it completely. When slot h(k) is occupied, try h(k) + 1. Occupied? Try h(k) + 2. Wrap around at the end.

Concrete example. Table of size 7, inserting keys with hash values 0, 4, 1, and 4 again.

Insert "alice" (hash=0) → slot 0
Insert "bob"   (hash=4) → slot 4
Insert "carol" (hash=1) → slot 1
Insert "dave"  (hash=4) → slot 4 occupied, probe slot 5 → insert at slot 5

Slot: [ 0 ]   [ 1 ]   [ 2 ]   [ 3 ]   [ 4 ]   [ 5 ]   [ 6 ]
      alice  carol    ---     ---     bob    dave    ---

To look up "dave": hash to 4, find "bob", probe 5, find "dave". Two probes.

The probe sequence is (h(k) + i) mod m for i = 0, 1, 2, .... The simplicity is the point. Sequential memory access is exactly what CPU caches are built to accelerate. Your hardware prefetcher loads the next cache line before you even ask for it. Once you pay for the first cache miss, the next several probes are basically free.

The Load Factor Is the Whole Story

The load factor is the ratio of entries to slots:

α = n / m

This single number determines how often you collide and how long probe sequences get. Under uniform hashing assumptions (Knuth, CLRS Chapter 11), expected probe counts for open addressing are:

Successful search: (1/2) * (1 + 1/(1 - α))
Unsuccessful search: (1/2) * (1 + 1/(1 - α)²)

Here is what those formulas actually produce:

α	Successful	Unsuccessful
0.50	1.5	2.5
0.75	2.5	8.5
0.90	5.5	50.5
0.99	50.5	~5,000

That last row is not a typo. At 99% full, an unsuccessful search averages five thousand probes. You are not doing a hash table lookup at that point. You are doing a linear scan of the entire table while telling yourself it's still O(1).

This is why open-addressed tables resize before they fill up. Python's dict triggers a resize when α exceeds 2/3. The table grows, every key rehashes, and operations snap back to being fast. The rehash costs O(n), but between two consecutive resizes you also do O(n) insertions. Amortized cost per insertion stays O(1). Same argument as dynamic array doubling, same sleight of hand, same result.

Load factor vs expected probe count for open addressing

Primary Clustering: When One Bad Neighborhood Grows

Linear probing has a well-documented failure mode. When multiple keys land near the same region, they form a contiguous run of occupied slots. Every future key that hashes anywhere inside that run gets tacked onto its end, which extends the run further, which catches more future keys, and so on.

This is primary clustering. It compounds like interest on a bad loan.

Before:  [ A ][ B ][ - ][ - ][ C ][ D ][ - ]
After inserting two more keys that hash to 1 or 4:
         [ A ][ B ][ E ][ - ][ C ][ D ][ F ]
(Slots 2 and 6 filled because probing extended existing runs)

Actual probe counts grow faster than the formulas predict because the real probe distribution over a clustered table is not uniform. You get a small number of extremely long sequences and a lot of short ones. The long ones are what users notice when they file a bug report about "random latency spikes."

Two Strategies That Break Up Clustering

Quadratic probing uses a quadratic step: (h(k) + i + i²) mod m. Instead of stepping 1, 2, 3 forward you step 1, 2, 4, 9, 16. The scattered jumps break up linear pileups. Remaining problem: two keys that initially hash to the same slot follow the exact same quadratic sequence forever. Secondary clustering. Weaker than primary, but present, and slightly annoying.

Double hashing uses a second hash function for the step size:

probe(k, i) = (h1(k) + i * h2(k)) % m

Two colliding keys get different h2(k) values and take completely different paths. Clustering vanishes. The tradeoff: probes jump unpredictably across the table, the hardware prefetcher gives up immediately, and you have traded cluster-driven slowness for cache-miss-driven slowness. Different problem, similar pain.

In practice, linear probing at moderate load factors often beats double hashing in wall-clock time. Cache-friendly sequential access survives more abuse than the probe-count analysis suggests, because the analysis assumes uniform hashing but says nothing about nanoseconds per memory access.

Robin Hood hashing improves on plain linear probing by measuring how far each key has drifted from its ideal slot and swapping incoming keys with incumbents that are closer to home. This redistributes probe lengths more evenly and cuts variance. Several high-performance implementations use it. Standard libraries, mostly not.

Deletion Leaves Ghosts

Here is a problem that does not exist with chaining: you cannot just null out a slot.

Suppose "dave" landed at slot 5 because slot 4 was occupied. Later, "bob" at slot 4 gets deleted and you set it to null. A search for "dave" now hashes to 4, sees null, and stops. It concludes "dave" does not exist. It is wrong. You broke the probe chain by creating a gap in the middle of it.

The fix is a tombstone: a sentinel that means "deleted here, keep probing" rather than "nothing here, stop."

EMPTY     = None
TOMBSTONE = object()  # sentinel

def delete(table, key):
    i = hash(key) % len(table)
    while table[i] is not EMPTY:
        if table[i] is not TOMBSTONE and table[i].key == key:
            table[i] = TOMBSTONE  # mark, don't erase
            return
        i = (i + 1) % len(table)

During search, tombstones count as occupied (probing continues). During insertion, tombstones are valid landing spots (reuse the slot).

The catch is that tombstones accumulate. A table with frequent deletes gradually fills with dead slots that slow searches without reducing the logical entry count. They inflate the effective load factor without being actual entries. The remedy is periodic rehashing to purge tombstones and recompute positions. Workloads with heavy deletes sometimes reach for chaining specifically because node removal leaves no residue.

What Real Hash Tables Actually Do

Python's dict uses open addressing with a perturbation-based probe that folds in high hash bits to reduce clustering. Load threshold: 2/3. On resize it grows to 4x the current used count and rehashes everything. The 4x gives you a lot of headroom before the next resize.

Go's map used open addressing with 8-key buckets per slot until Go 1.24, when it migrated to Swiss Tables. Swiss Tables check 16 slots simultaneously using per-slot metadata bytes and SIMD comparisons, keeping expected probe counts near 1 even at high load. Your Go code quietly got faster when you upgraded.

Ruby's Hash switched from chaining to open addressing in Ruby 2.4, explicitly for cache locality.

Java's HashMap stayed on chaining, which is why it tolerates a 0.75 load factor without the drama you would see in an open-addressed table at the same density. When a bucket's chain exceeds 8 entries, Java converts it to a red-black tree (added in JDK 8, the last time Java made a decision quickly).

When you call d["key"] in Python, you are running a probing sequence through a flat array. That's why Python dicts are faster than the collision analysis alone suggests. An insertion that tips α past 2/3 can briefly spike latency as everything rehashes. Now you know why.

How to Talk About This in an Interview

Open addressing rarely appears as a direct coding problem. It shows up in follow-up questions constantly.

When you implement a hash map from scratch, interviewers ask: "How would you handle collisions?" Knowing the chaining vs. open addressing split, the three probe strategies, and the tradeoffs earns you a real answer instead of "uh, linked list I guess."

When complexity comes up, load factor is what matters. "Hash map lookup is O(1)" is correct on average. Explaining that worst-case degradation occurs as α approaches 1, and that real implementations resize to prevent it, is the answer that earns a strong algorithms signal.

The amortized resizing argument is worth having ready. Each resize copies n entries in O(n). But between two consecutive resizes, you also do O(n) insertions. Amortized cost per insertion is O(1). That's the same argument as dynamic array resizing, and connecting the two without prompting is exactly the kind of thing interviewers write down in your feedback.

Practicing these explanations out loud is different from recognizing them on a page. SpaceComplexity runs voice-based mock interviews with rubric feedback so you can rehearse the reasoning, not just read it.

For more on why hash map complexity works the way it does, see hash map time complexity and how hash functions work. The cache locality side of the chaining vs. open addressing comparison is in array vs linked list performance, with concrete benchmark numbers. When to reach for a hash map versus a BST is in BST vs hash map.