Open addressing

A hash table collision-handling method storing at most one live record per array slot. A hash function chooses a starting slot, and a probe rule chooses further slots. Unlike separate chaining, records occupy the slots themselves.

An open addressing probe rule that visits $h_m(k),h_m(k)+1,h_m(k)+2,\dots$ modulo $m$, using modular arithmetic, until a matching record or an appropriate stopping slot is found.^[ref]

For capacity $m>0$, the hash table probe numbered $i$, starting at zero, inspects the array indexThe hash function $h_m$ gives the first array index. Each subsequent hash table probe moves one slot forward, wrapping from $m-1$ to $0$ by modular arithmetic. Keep the hash function and key equality fixed while hash table records are stored.

Use three distinguishable slot states: occupied by a live hash table record; never used since initialization or rebuilding, written E; or deleted, written D, a tombstone in open addressing. Lookup compares occupied hash table keys using key equality, stops at E, and continues past D.^[ref]

For an original example, take an eight-slot array, integer hash table keys, and the hash function $h_8(k)=k\mathrm{mod}8$. Start with all slots E and insert the hash table records $(0,A),(8,B),(16,C),(9,V)$ in that order. The insertion hash table probe traces, expressed as array indices, areThe resulting array holds hash table keys $0,8,16,9$ at array indices $0,1,2,3$, with E in the other four slots. The first three hash table keys have the same initial array index, a hash collision; the fourth begins at $1$ but joins the same linear probing cluster. Lookup of $16$ examines array indices $0,1,2$, rejecting $0,8$ before returning $C$. Lookup of absent $24$ examines $0,1,2,3,4$, including the stopping E: five hash table probes for a hash table load factor $\alpha =4/8=1/2$.

Bound lookup to at most $m$ hash table probes, even if no E remains. For algorithm termination, the first $m$ array indices are distinct: equality of $p_i(k)$ and $p_j(k)$ implies that $m$ divides $i-j$ by modular arithmetic, and $0\le i,j<m$ forces $i=j$. They therefore cover the entire finite set of slots exactly once. If no occupied hash table key matches and no E is encountered, exhausting these $m$ hash table probes establishes absence; wrapping around again supplies no new information.^[ref]

The attraction is a compact array and a simple hash table probe rule. Consecutive slots can benefit from spatial locality, although actual memory cache behavior depends on representation and hardware. Correctness rests on preserving the search route; speed depends on how long that route becomes. The linear probing cluster below explains why even a moderate hash table load factor gives no universal constant lookup bound.

A maximal consecutive run of occupied or deleted slots in linear probing, bounded by never-used slots when any exist; adjacency wraps around by modular arithmetic. Deleted slots still belong to the search run.^[ref]

In the eight-slot example, array indices $0,1,2,3$ form one linear probing cluster. Inserting absent hash table key $10$ starts at $2$, passes the occupied slots $2,3$, and fills $4$. This extends the same linear probing cluster despite $10$ having a different initial array index from $0,8,16$. A hash collision at the initial slot is enough to make later slots compete too.

For a worst-case family, insert integer hash table keys $0,m,2m,\dots ,(n-1)m$ into an empty capacity-$m$ array, using the hash function $h_m(k)=k\mathrm{mod}m$, where $1\le n<m$. They occupy array indices $0,\dots ,n-1$. Lookup of absent $nm$ needs $n+1$ hash table probes. Taking $n=\lfloor m/2\rfloor$ gives hash table load factor at most $1/2$ while the number of hash table probes grows with $m$. Thus occupancy alone cannot promise constant lookup work.

Before any rebuilding, bounded lookup, deletion by hash table key, and insertion with a duplicate check each have worst-case $O(m)$ time complexity in Big O notation, assuming constant-cost hash function evaluation, array access and key equality. The counterexample gives a matching linear worst-case growth in the number of hash table probes. Hash table resizing is additional work; expensive string comparisons or hashing also fall outside these constant-cost assumptions.

In an insertion-only table, an absent hash table key starting anywhere inside a linear probing cluster reaches its far end. Filling a one-slot gap can merge two runs, joining hash table keys with different initial array indices into one long search route. The insertion of $10$ above exhibits this effect without a hash collision with $0$ at their initial slots.^[ref]

A deleted-slot marker in open addressing. Lookup continues past it because a hash collision may have displaced a match further along. Linear probing can reuse the slot for insertion after checking for an existing equal key. A genuinely empty slot can terminate lookup; this marker cannot.^[ref]

Delete hash table key $8$ from the original eight-slot example. Writing E into array index $1$ makes lookup of $16$ inspect $0,1$ and incorrectly report absence, although its hash table record remains at $2$. Writing D instead makes lookup pass $1$ and reach $2$, returning $C$ after three hash table probes. The deleted slot must remember that the search route once continued through it.

A short algorithm correctness proof uses this invariant: no never-used slot precedes a stored hash table key along its linear probing route. Initially the claim is vacuous. Insertion places a new hash table record no later than the first E, possibly at an earlier D, and cannot create an E before another stored hash table record. Replacing a value leaves all slots occupied as before. Deletion to D also creates no E. By mathematical induction over operations, the invariant persists, so stopping lookup at E is sound. Deletion directly to E invalidates that argument, as the diagram shows.

To implement the hash table map operation put(k,v) in one bounded scan, remember the first D encountered, but keep checking occupied hash table keys. A later key equality match means replace that hash table record's value and stop. Only after reaching E, or completing $m$ hash table probes, is absence established. Then insert at the remembered D, if any; otherwise use the stopping E. If all $m$ slots are occupied and no match exists, report full or rebuild before trying again. Merely finding D is not permission to create a second equal hash table key.^[ref]

Continue from the correctly deleted example, with hash table keys $0,16,9$ at array indices $0,2,3$ and D at $1$. put(16,Z) examines $0,1,2$ and updates the value at $2$, leaving $1$ deleted and retaining three live hash table records. Inserting immediately at $1$ would instead create two copies of $16$. Now put(24,W) examines $0,1,2,3,4$, proves absence at E, and places the new hash table record at the remembered array index $1$. The hash table load factor rises from $3/8$ to $4/8$; reusing D avoids extending the linear probing cluster to $4$.

For a boundary case, fill all eight slots with hash table keys $0,1,\dots ,7$ and then delete all eight to D. The live hash table load factor is zero, but absent lookup of $16$ still needs eight hash table probes. put(16,C) also checks eight slots before reusing the first D, at array index $0$. A loop that waits indefinitely for E would never finish in this state. Rebuilding from the live hash table records into a fresh array removes each tombstone in open addressing and restores never-used stopping slots.^[ref]

One inspection of an array slot during an open addressing operation. Its array index follows the chosen probing rule; its contents determine whether to continue, return a matching hash table record, or establish absence.