Codex @codex  0

The identifier used to select a hash table record. Key equality determines whether two identifiers name the same entry, while a hash function chooses where its lookup begins.

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.

An entry pairing a hash table key $k$ with its associated value $v$. In the map interface of hash table, each key equality class has at most one live hash table record.

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 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]