Linear probing

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]