Open Addressing Collision Resolution

An open-addressing hash table is a single array `T[0..m-1]` of size `m`. Every key `k` is mapped, not to one slot, but to an entire probe sequence of slot indices ``` h(k, 0), h(k, 1), h(k, 2), ..., h(k, m-1) ``` which is a permutation of `{0, 1, ..., m-1}` — every slot is eventually visited if probing continues long enough. To insert `k`, we walk the sequence starting at attempt `0` and place `k` in the first empty slot we find. To search for `k`, we walk the same sequence and stop as soon as we find `k` (success) or find an empty slot (failure — since `k`, if present, would have been placed there or earlier during insertion, an empty slot proves `k` is absent). This is the fundamental invariant that makes open addressing work: an insertion for key `k` never skips over an empty slot in `k`'s own probe sequence, because insertion always stops at the first empty slot it encounters. Consequently, if `k` is in the table, it lies at the first slot in its probe sequence that is not occupied by a different, earlier-inserted key. Searching along the same sequence and stopping at the first empty slot is therefore guaranteed to find `k` if it is present — provided no slot has been silently emptied since insertion. That last proviso is exactly why naive deletion is unsafe, and why tombstones exist. The load factor `α = n/m` (number of stored keys over table size) governs everything: it must always satisfy `α ≤ 1` since every key needs its own slot, and in practice tables are resized (typically doubled) once `α` exceeds a threshold like `0.7`. All complexity results below are stated as functions of `α`, under the idealized assumption of uniform hashing: each key's probe sequence is treated as an independently and uniformly chosen permutation of the `m` slots. Real probe sequences are deterministic functions of the key, so uniform hashing is a modeling assumption, but it accurately predicts the qualitative and even quantitative behavior of double hashing, and gives useful (if imperfect) intuition for linear and quadratic probing.

Linear probing uses ``` h(k, i) = (h'(k) + i) mod m ``` where `h'` is an ordinary hash function. On collision, we simply try the next slot, wrapping around. It is maximally cache-friendly (sequential memory access) but produces primary clustering: once a run of occupied slots forms, any key hashing into that run extends it, so long runs grow even longer, which self-reinforces and degrades performance as `α` grows.

Quadratic probing uses ``` h(k, i) = (h'(k) + c1i + c2i^2) mod m ``` for constants `c1, c2` (a common simple choice is `c1 = c2 = 1`, or the classic `c1 = 0, c2 = 1` giving `h'(k) + i^2`). This spreads out slots faster than linear probing, avoiding primary clustering, but two keys with the same `h'(k)` produce identical probe sequences — a milder problem called secondary clustering. A further subtlety: with poorly chosen constants and table size, quadratic probing may not visit all `m` slots, so insertion can fail even when the table is not full. A standard remedy is to make `m` a prime and use `c1 = c2 = 1/2` (with `m` prime and probing `h'(k) + (i^2+i)/2`), which provably visits every slot.

Double hashing uses two hash functions: ``` h(k, i) = (h1(k) + i h2(k)) mod m ``` where `h2(k)` must never be `0` and must be <strong>coprime to `m`</strong> — guaranteed automatically if `m` is a power of two and `h2` always returns an odd number, or if `m` is prime and `h2(k) ∈ {1, ..., m-1}`. This makes the probe sequence depend on the key through two* independent-looking quantities, so two keys colliding at attempt `0` almost certainly diverge afterward. Double hashing is the closest of the three to the uniform-hashing ideal, at the cost of computing a second hash function and slightly worse cache locality than linear probing.

Pseudocode

``` // m = table size, T[0..m-1] slots, each EMPTY, OCCUPIED(key), or DELETED (tombstone) function PROBE(k, i): // choose ONE of the following schemes // linear: return (h1(k) + i) mod m // quadratic: return (h1(k) + c1i + c2i*i) mod m // double hash: return (h1(k) + i h2(k)) mod m ... function INSERT(T, k): firstDeleted <- NONE for i in 0 .. m-1: j <- PROBE(k, i) if T[j] is EMPTY: slot <- firstDeleted if firstDeleted != NONE else j T[slot] <- OCCUPIED(k) return slot else if T[j] is DELETED and firstDeleted == NONE: firstDeleted <- j // reuse tombstone slot if k is new else if T[j] is OCCUPIED(k): return j // key already present (optional: update) error "table full" // triggers resize in practice function SEARCH(T, k): for i in 0 .. m-1: j <- PROBE(k, i) if T[j] is EMPTY: return NOT_FOUND // correctness: empty slot proves absence else if T[j] is OCCUPIED(k): return j // if T[j] is DELETED, or OCCUPIED with a different key, keep probing return NOT_FOUND function DELETE(T, k): j <- SEARCH(T, k) if j == NOT_FOUND: return false T[j] <- DELETED // tombstone, NOT EMPTY return true ``` The critical correctness detail is in `SEARCH`: it terminates on an `EMPTY` slot but keeps going* through a `DELETED` slot, since a deleted slot might have been "jumped over" during the original insertion of some other key still further along the sequence. `INSERT` opportunistically reuses the first tombstone it passes (if the key turns out not to already be in the table), which reclaims space without breaking future searches.

Space: `Θ(m)` — one array slot per table entry, no auxiliary pointers, in contrast to chaining's per-key node overhead. This is open addressing's main structural advantage.

Time, under uniform hashing. Let `α = n/m < 1` be the load factor. The classical result (proved via indicator random variables over the idealized uniform probe-sequence model) states:

• Unsuccessful search / insertion (search continues until an empty slot is hit): expected number of probes is

``` E[probes] ≤ 1 / (1 − α) ```

• Successful search: expected number of probes is at most

``` E[probes] ≤ (1/α) · ln(1/(1 − α)) ``` Proof sketch (unsuccessful search). Model each probe as landing, independently and uniformly, on one of the `m` slots (this is the uniform-hashing idealization). Let `p_i` be the probability that the first `i` probes all hit occupied slots. Since there are `n` occupied slots among `m` total and each probe is uniform over the remaining slots in this idealization, ``` p_i ≤ (n/m)^i = α^i. ``` The expected number of probes is `E[probes] = Σ_{i≥0} p_i ≤ Σ_{i≥0} α^i = 1/(1 − α)`, using the geometric series identity since `0 ≤ α < 1`. This immediately shows why `α` must be bounded away from `1`: as `α → 1`, expected probes blow up (e.g., at `α = 0.9`, expect `10` probes; at `α = 0.99`, expect `100`). Successful search reduces to an average, over all `n` keys currently in the table, of the unsuccessful-search cost at the moment each key was inserted — because a successful search for `k` retraces exactly the probes made when `k` was inserted. Averaging the bound `1/(1−i/m)` over insertion indices `i = 0, ..., n−1` and approximating the sum by an integral yields the stated `(1/α)ln(1/(1−α))` bound.

Honesty about the idealization. These bounds rigorously hold for double hashing only under an additional idealized assumption (that `h1, h2` behave like independent uniform random functions), which real hash functions only approximate — but empirically double hashing tracks the bound closely. Linear probing provably does worse: a classical result (Knuth) shows linear probing's expected cost for an unsuccessful search is closer to ``` ½ (1 + 1/(1−α)^2) ``` which grows faster than `1/(1−α)` as `α → 1`, quantifying primary clustering precisely — long runs of occupied slots become likely and self-reinforcing. Quadratic probing sits in between: it avoids primary clustering (no tendency for a whole run to merge) but two keys with equal `h1` share a probe sequence, causing secondary clustering, which is asymptotically milder than linear probing's but still real.

Correctness invariant (formal). Define the invariant I: for every key `k` ever inserted and not yet deleted, `k` resides at the first slot in its probe sequence `h(k,0), h(k,1), ...` that is not `EMPTY` (tombstones count as non-empty). `INSERT` establishes I by construction (it places `k` at the first non-occupied slot, converting a tombstone or empty slot to occupied). `DELETE` preserves I for all other keys because it only ever writes a `DELETED` marker, never `EMPTY`, into a slot that lay along some other key's probe sequence — so no other key's "first non-empty slot" claim is disturbed. `SEARCH` is correct given I: walking the probe sequence and stopping only at a genuinely `EMPTY` slot is guaranteed to reach `k`'s slot before (or at) the first empty slot, since by I, `k` sits at exactly that first non-empty position. This is precisely why treating a deleted slot as `EMPTY` during search — the natural but wrong implementation — breaks the invariant's use, not its establishment: it makes `SEARCH` stop too early, at a hole that a later key's probe sequence had to skip over.

Tradeoffs, honestly stated.

A long-running table with heavy insert/delete churn accumulates tombstones, which inflate probe lengths even at moderate `α` since tombstones count as "occupied" during search. Production implementations periodically rehash (rebuild into a fresh array, dropping tombstones) once the tombstone-plus-key count crosses a threshold, distinct from the load-factor resize trigger.

Table size `m = 7` (prime, convenient for double hashing), using ``` h1(k) = k mod 7 h2(k) = 1 + (k mod 5) // guaranteed in {1,...,5}, coprime to 7 since 7 is prime ``` Insert keys `10, 22, 3, 24, 12` with double hashing, `h(k,i) = (h1(k) + i·h2(k)) mod 7`.

Note how `10`, `3`, and `24` all share `h1 = 3` (they collide at attempt `0`), yet their step sizes `h2 = 1, 4, 5` are all different, so they immediately diverge onto different sequences — this is exactly what double hashing buys over linear probing, where all three would follow the identical sequence `3, 4, 5, 6, 0, ...` and pile into one long run. Now delete key `22` (slot `1`): `T[1] ← DELETED`. Table: `[3, ✗, _, 10, _, 12, 24]`. Search for `24`: `h1=3, h2=5`, sequence `3, (3+5)%7=1, (3+10)%7=6`.

• `i=0, j=3`: occupied with `10 ≠ 24` → continue.
• `i=1, j=1`: `DELETED` → must continue, not stop, even though this looks like a hole.
• `i=2, j=6`: occupied with `24` → found.

If deletion had instead written `EMPTY` at slot `1`, the search would have incorrectly halted at `i=1` and reported `24` as absent, even though it is present at slot `6` — this is exactly the bug tombstones prevent, traced concretely. Search for `9` (never inserted): `h1(9)=2, h2(9)=1+(9 mod 5)=5`, sequence `2, 0, 5, 3, ...`

• `i=0, j=2`: `EMPTY` → stop, report not found, correctly, after a single probe — because slot `2` really has never been touched by any key's insertion.

Open addressing's key ideas — probe sequences, clustering analysis, and the double-hashing remedy — were formalized during the early development of file and memory indexing systems in the 1950s-60s, then given rigorous mathematical treatment by Donald Knuth, whose analysis of linear probing's clustering (the `~1/(1-α)^2` behavior) remains the standard reference derivation. The broader theory of Hash Functions that probe sequences depend on, and the underlying Hash Tables and Direct Addressing model that open addressing specializes, were being formalized in the same period by researchers at IBM and Bell Labs building the first large-scale symbol tables and databases.

Open addressing is the storage strategy behind CPython's `dict` and `set` (using a pseudo-random perturbation-based probe sequence closely related to double hashing), Google's Abseil `flat_hash_map`/`flat_hash_set` (SwissTable design, using metadata bytes plus linear-ish group probing tuned for SIMD), and the `robin_hood`/`ankerl` unordered map libraries used across performance-sensitive C++ services. Database engines use open-addressed hash indexes for in-memory join and aggregation buffers where allocation-free, cache-line-aligned storage measurably improves throughput over chained alternatives. Embedded and real-time systems favor open addressing because it avoids dynamic memory allocation inside the collision-resolution path entirely — everything lives in one pre-sized array — which is essential when heap fragmentation or allocator latency is unacceptable. Any system explaining "why does my hash map slow down as it fills up" is really asking a question this article answers precisely: it is the `1/(1-α)` (or worse, for linear probing) growth in expected probe count as load factor approaches one.

Ask the tutor: How would you modify the expected-probe-count analysis if the hash function is not uniform but has some keys colliding with higher probability?