 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.

Linear probing is a collision resolution technique used in open addressing, a method for implementing hash tables. When a hash function maps a key to an index in the hash table, there may be cases where two or more keys hash to the same index, resulting in a collision. Linear probing addresses this problem by searching for the next available slot in the hash table sequentially.