Collision Resolution: Open Addressing

Hash tables are among the most powerful data structures in computer science, offering average-case O(1) performance for insertions, deletions, and lookups. But their efficiency depends entirely on how collisions are handled. A collision occurs when two distinct keys produce the same index after the hash function is applied. One major family of collision resolution strategies is called open addressing, which keeps all data within a single flat array and resolves collisions by probing — that is, systematically searching for an alternative empty slot inside the same array. This is in contrast to chaining, where each array slot holds a linked list of all keys that mapped to that index. Open addressing trades away the flexibility of dynamic chains for the benefits of spatial locality, simplicity, and reduced memory overhead.

Understanding open addressing requires grasping three interconnected ideas: how an alternative slot is found (the probe strategy), how the table's occupancy level affects performance (the load factor), and how deletions are managed safely (tombstones). Each of the three main probe strategies — linear probing, quadratic probing, and double hashing — offers a different trade-off between simplicity, clustering behavior, and probe distribution quality.

What Is Open Addressing?

In open addressing, when a collision occurs at a slot, the algorithm does not build a chain at that slot. Instead, it follows a probe sequence — a deterministic series of alternative indices within the same array — until it finds an empty slot. The key-value pair is then stored at that empty slot. Every element lives directly in the table array itself, with no auxiliary data structures.

This design has important consequences:

• The table must never be completely full. Probe sequences rely on encountering an empty slot either to place a new key (during insertion) or to confirm that a key is absent (during lookup). A completely full table has no empty slots, so probe sequences cannot terminate correctly. This is why open-addressed tables are always kept below a maximum load factor and resized before becoming full.
• Cache performance is often better than chaining. Because all entries share a contiguous array, accessing nearby slots during probing tends to hit the CPU cache. Linked list nodes in chaining are scattered across the heap, causing cache misses. For workloads where cache efficiency matters — which is most modern workloads — open addressing can outperform chaining even when the probe sequences are a little longer.
• Probe sequences must be consistent. Every operation (insert, lookup, delete) must follow the exact same probe sequence for a given key. If insertion used one sequence and lookup used another, a stored key could never be found.

Linear Probing

Linear probing is the simplest open addressing strategy. When a collision occurs at index h, the algorithm checks the very next slot, then the one after that, and so on — wrapping around the end of the array if necessary. The probe sequence formula is:

index = (hash(key) + i) % tableSize

where i starts at 0 and increments by 1 at each step. So the sequence of slots examined for a key with home slot h in a table of size M is:

h, (h+1)%M, (h+2)%M, (h+3)%M, ...

Consider a table of size 7 and a simple hash function hash(key) = key % 7. Suppose we insert the keys 10, 17, 24 in that order.

• Insert 10: 10 % 7 = 3. Slot 3 is empty → place 10 at slot 3.
• Insert 17: 17 % 7 = 3. Slot 3 is occupied. Probe slot 4 → empty → place 17 at slot 4.
• Insert 24: 24 % 7 = 3. Slot 3 occupied. Probe slot 4 → occupied. Probe slot 5 → empty → place 24 at slot 5.

Notice that slots 3, 4, and 5 form a contiguous block. This illustrates the core weakness of linear probing: primary clustering. Once a run of filled slots forms, any new key whose hash falls anywhere inside or immediately before that run will extend it further. A run of length k attracts new keys with probability proportional to k, so runs tend to grow longer over time, causing insertions and lookups to require more and more probes. In heavily loaded tables this can dramatically degrade average-case performance.

Despite clustering, linear probing has excellent cache behavior because the probed slots are adjacent in memory. For tables with low to moderate load factors, this cache advantage often makes linear probing faster in practice than more sophisticated methods.

Quadratic Probing

Quadratic probing addresses primary clustering by spacing probes farther apart as the probe count increases. Instead of checking every consecutive slot, the step size grows quadratically:

index = (hash(key) + i²) % tableSize

The probe sequence for home slot h becomes:

h, (h+1)%M, (h+4)%M, (h+9)%M, (h+16)%M, ...

Because colliding keys jump to different positions after the first collision, long contiguous runs do not form. This eliminates primary clustering. However, quadratic probing introduces a subtler problem called secondary clustering: any two keys that happen to share the same home slot will follow the exact same probe sequence, since the offsets depend only on i, not on the key itself. They will compete for the same set of candidate slots, just as if linear probing had been used for those specific keys.

There is also a mathematical concern: quadratic probing does not guarantee that the probe sequence will visit every slot in the table. If the probe sequence cycles back to already-visited slots before finding an empty one, an insertion can fail even though empty slots exist elsewhere. Two conditions together guarantee full coverage:

• The table size M must be a prime number.
• The load factor must stay below 0.5 (the table is less than half full).

Under these conditions it can be proven that at least half the slots will be reached, which is always enough to find an empty slot if the load factor is below 0.5. In practice, keeping load factors under 0.5 is more restrictive than the typical 0.75 threshold used with chaining, meaning quadratic probing wastes more memory per stored element.

Using the same example (table size 7, hash(key) = key % 7), inserting keys 10, 17, 24:

• Insert 10: slot 3 empty → place at 3.
• Insert 17: slot 3 occupied. i=1 → (3+1)%7 = 4, empty → place at 4.
• Insert 24: slot 3 occupied. i=1 → slot 4 occupied. i=2 → (3+4)%7 = 0, empty → place at 0.

Key 24 landed at slot 0 instead of slot 5, breaking up the cluster that linear probing would have created.

Double Hashing

Double hashing is the most sophisticated open addressing technique and generally provides the best probe distribution. It eliminates both primary and secondary clustering by making the step size depend on the key itself, not just on the probe count. Two independent hash functions are used:

index = (hash1(key) + i * hash2(key)) % tableSize

The probe sequence for a given key is:

hash1(key), hash1(key) + hash2(key), hash1(key) + 2*hash2(key), ...  (all mod M)

Because hash2(key) differs for different keys, even two keys with the same home slot will follow different probe sequences after the first collision. This breaks secondary clustering. And because neither sequence necessarily scans adjacent slots, primary clustering is also avoided.

Designing hash2 requires care:

• hash2 must never return 0. A step size of 0 would mean the algorithm probes the same slot forever, causing an infinite loop. A common safeguard is hash2(key) = R - (key % R) where R is a prime number smaller than the table size. This expression always yields a value between 1 and R.
• hash2 should be independent of hash1. If both functions produce correlated values, the probe sequences are less uniformly distributed and clustering can re-emerge.
• The table size should be prime. This ensures that for any nonzero step size s, the sequence h, h+s, h+2s, ... (mod M) visits all M slots before repeating, guaranteeing that every empty slot is reachable.

A typical double hashing setup for integer keys with table size M (prime) and a second prime R < M:

hash1(key) = key % M
hash2(key) = R - (key % R)

Inserting keys 10, 17, 24 into a size-7 table with R=5:

• hash2(10) = 5 - (10%5) = 5 - 0 = 5
• hash2(17) = 5 - (17%5) = 5 - 2 = 3
• hash2(24) = 5 - (24%5) = 5 - 4 = 1

• Insert 10: slot 3 empty → place at 3.
• Insert 17: slot 3 occupied. Step = 3. Next: (3+3)%7 = 6, empty → place at 6.
• Insert 24: slot 3 occupied. Step = 1. Next: (3+1)%7 = 4, empty → place at 4.

The three keys are distributed across non-adjacent slots with no clustering. The cost is computing two hash functions for every operation, which adds a small but constant overhead compared to linear or quadratic probing.

Probe Sequences and Slot Selection

Regardless of which technique is used, the logic of a probe sequence is the same in structure. The sequence begins at the key's home slot — the index returned by the primary hash function — and proceeds according to the probing formula until one of two things happens:

• An empty slot is found. During insertion, the key is placed here. During lookup, this confirms the key is not in the table (because if it had been inserted, the probe sequence would have stopped here at that time, and the key would be in this slot or a slot already examined).
• The target key is found in a slot. The operation succeeds.

A crucial invariant is that the probe sequence used during lookup must be identical to the one used during insertion. If a key was placed at position (h + 4) % M during insertion because slots h, (h+1)%M, and (h+4)%M followed the quadratic sequence, then lookup must follow that same path. There is no separate "search" path — the insert path and find path are the same.

This also means that the probe sequence is entirely deterministic given the key and the table size. No randomness is involved at runtime; the sequence is computed algebraically from the key's hash values and the probe formula.

Handling Deletions in Open Addressing

Deletion is the trickiest aspect of open addressing. Naively setting a deleted slot back to "empty" breaks the probe sequence invariant. Consider this scenario: key A and key B both hash to slot 5. A is inserted at slot 5, B probes forward and lands at slot 6. Later, A is deleted and slot 5 is marked empty. Now a lookup for B starts at slot 5, sees "empty", and concludes that B is not in the table — even though B is sitting at slot 6. The lookup terminated prematurely because the empty marker at slot 5 looked like the end of a chain that was never started.

The solution is to use a tombstone (also called a sentinel or deleted marker). When a slot is deleted, it is marked with a special value that means "this slot was once occupied but is now logically empty." The key distinction is:

• Tombstone during lookup: The probe sequence continues past a tombstone. The key might still be further along the sequence.
• Empty slot during lookup: The probe sequence terminates. The key is definitively absent.
• Tombstone during insertion: The slot can be reused. The algorithm records the first tombstone it encounters and, if the key is not found further along the sequence, places the new key at that tombstone slot (reclaiming the space).

In pseudocode, an insertion with tombstone handling looks like:

function insert(table, key, value):
    h = hash1(key)
    firstTombstone = -1
    i = 0
    while true:
        slot = probeSequence(h, i)
        if table[slot] == EMPTY:
            if firstTombstone != -1:
                table[firstTombstone] = (key, value)
            else:
                table[slot] = (key, value)
            return
        elif table[slot] == TOMBSTONE:
            if firstTombstone == -1:
                firstTombstone = slot
        elif table[slot].key == key:
            table[slot].value = value  // update existing
            return
        i++

The downside is that tombstones accumulate over time. Each tombstone is a slot that cannot be used to terminate a negative lookup (a search for a key that is absent), so negative lookups must probe through all tombstones until a genuinely empty slot is found. A table with many tombstones and few truly empty slots can suffer from degraded lookup performance even if the actual number of live entries is small. When tombstone density becomes problematic, the solution is a full rehash: allocate a new (possibly larger) array and reinsert every live key into it. Because no key is deleted during a fresh rehash, no tombstones are created, and the new table has genuine empty slots scattered throughout.

Load Factor and Performance in Open Addressing

The load factor α is defined as the ratio of the number of stored entries to the total number of slots:

α = n / M

where n is the number of live entries and M is the table size. Load factor is the single most important determinant of open addressing performance. Because probe sequences must find empty slots to terminate, and the probability of any given slot being empty is (1 − α), higher load factors mean longer expected probe sequences.

For linear probing, the expected number of probes for a successful lookup is approximately:

½ (1 + 1/(1 - α))

And for an unsuccessful lookup (or insertion):

½ (1 + 1/(1 - α)²)

These formulas (Knuth's analysis) show that at α = 0.5 the expected probes are modest, but at α = 0.9 unsuccessful lookups require on average about 50 probes — a massive degradation. The table below illustrates how dramatically probe count grows with load factor under linear probing:

Double hashing and quadratic probing perform better at high load factors than linear probing because they avoid clustering, but all open addressing strategies degrade sharply as α approaches 1.

To keep performance near O(1), open-addressed hash tables are resized whenever the load factor exceeds a chosen threshold — commonly 0.7 for double hashing, or 0.5 for quadratic probing. Resizing (also called rehashing) allocates a new array — typically about twice the size of the old one, with the new size chosen to be prime — and reinserts every live entry from the old table into the new one using the new table size in all hash function computations. This is an O(n) operation but happens infrequently enough that the amortized cost per insertion remains O(1).

A comparison of the three strategies across the dimensions that matter most in practice:

In summary, open addressing is a powerful and memory-efficient collision resolution paradigm whose performance is governed primarily by the choice of probing strategy and the table's load factor. Linear probing wins on cache efficiency but suffers from primary clustering. Quadratic probing avoids that clustering but introduces secondary clustering and requires restrictive load factor limits. Double hashing provides the best theoretical probe distribution at the cost of computing two hash functions and slightly reduced cache locality. All three share the same deletion semantics — tombstones — and all three benefit enormously from keeping the load factor well below 1 through timely rehashing.