Collision Resolution: Open Addressing

How Open Addressing Works

In open addressing, all $(key, value)$ pairs are stored directly in the hash table array (no linked lists). Each slot holds either a pair or is empty (NIL). When a collision occurs at slot $h(k)$, the algorithm probes alternative slots according to a deterministic sequence until an empty slot is found.

The table must have strictly more slots than stored keys: the load factor $\alpha = n/m < 1$.

The Probe Sequence

For key $k$, the $i$th probe (starting from $i=0$) is:

$h(k, i) = (h'(k) + f(i)) \bmod m$

where $h'(k)$ is the base hash function and $f(i)$ defines the probing strategy. The sequence must be a permutation of $\{0, 1, \ldots, m-1\}$ so every slot is reachable.

Linear Probing

$h(k, i) = (h'(k) + i) \bmod m$

The simplest strategy: if slot $h'(k)$ is occupied, try $h'(k)+1$, then $h'(k)+2$, and so on (wrapping around).

Primary clustering: contiguous runs of occupied slots form, and any key hashing anywhere into the run must probe through the entire run. Linear probing effectively reduces the selectivity of the hash function: keys that did not originally collide end up competing for the same slots. Using a step size other than 1 does not solve this (it just shifts where clustering appears).

Quadratic Probing

$h(k, i) = (h'(k) + c_1 i + c_2 i^2) \bmod m$

For example, with $c_1 = c_2 = 1$: probe sequence $h', h'+2, h'+6, h'+12, \ldots$ (differences $+1, +3, +5, +7, \ldots$). Starting from different $h'$ values produces different sequences, so keys that collide under $h'$ do not follow each other indefinitely.

Secondary clustering: keys that hash to the same $h'$ value still follow the same probe sequence and collide repeatedly. This is less severe than primary clustering.

Double Hashing

$h(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod m$

Uses a second independent hash function $h_2(k)$. To ensure $h_2(k)$ is always coprime to $m$ (so the probe sequence visits all slots), a common choice is:

$h_2(k) = (h_2'(k) \bmod (m-1)) + 1$

Double hashing approximates the uniform hashing assumption: each probe sequence is equally likely to be any permutation. It avoids both primary and secondary clustering, at the cost of computing a second hash function.

Insert, Search, and Delete

INSERT: start at $i=0$. Probe $h(k, i)$. If slot is NIL, insert there. If slot is occupied by a key that equals $k$, update the value. If a full cycle is made without finding an empty slot, the table is full (or the probe sequence was flawed).

SEARCH: start at $i=0$. Probe $h(k, i)$. If slot matches the key, return value. If an empty (NIL) slot is reached, the key is not present. If a full cycle completes, key not present.

DELETE: you cannot simply set the slot to NIL, because that would break probe sequences for other keys. A search for a key that probed past the now-deleted slot would falsely terminate at the NIL.

Instead, use a tombstone (deleted marker): when searching, a tombstone means “keep probing” (it is not an empty slot). When inserting, a tombstone counts as “available” (can be overwritten).

Performance

Under the uniform hashing assumption, the expected number of probes for:

• Unsuccessful search: $\frac{1}{1-\alpha}$
• Successful search: $\frac{1}{\alpha}\ln\frac{1}{1-\alpha}$

Example with $\alpha = 0.5$: unsuccessful search expects $\frac{1}{0.5} = 2$ probes; successful search expects $\frac{1}{0.5}\ln 2 \approx 1.39$ probes.

With $\alpha = 0.9$: unsuccessful expects $\frac{1}{0.1} = 10$ probes; successful expects $\frac{1}{0.9}\ln 10 \approx 2.56$ probes.

Performance degrades sharply as $\alpha \to 1$. Typical implementations rehash when $\alpha$ exceeds $0.5$.

Resizing with Open Addressing

Maintain counters for the number of live keys ($n_k$) and tombstones ($n_m$). When $n_k + n_m$ exceeds a threshold (e.g. $0.5 \cdot m$):

• If $n_k \gg n_m$: rehash into a larger table.
• If $n_k \approx n_m$: rehash into a table of the same size (purging tombstones).
• If $n_k \ll n_m$: rehash into a smaller table.

Tables sizes are often chosen as primes to improve hash function behaviour.

Summary

Probing Method	Probe Sequence	Clustering Issue
Linear	$h' + i$	Primary clustering
Quadratic	$h' + c_1 i + c_2 i^2$	Secondary clustering
Double hashing	$h_1 + i \cdot h_2$	Negligible
Tombstone	Deleted marker	Enables correct deletion
Load factor limit	$\alpha < 1$	Typically keep $\alpha \le 0.5$
Expected unsuccessful probes	$\frac{1}{1-\alpha}$	Under uniform hashing
Expected successful probes	$\frac{1}{\alpha}\ln\frac{1}{1-\alpha}$	Under uniform hashing