= Linear probing
{wiki}
An <open addressing> probe rule that visits $h_m(k),h_m(k)+1,h_m(k)+2,\ldots$ modulo $m$, using <modular arithmetic>, until a matching record or an appropriate stopping slot is found.<6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff/Lecture 10: Hashing III: Open Addressing>[6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff; Lecture 10: Hashing III: Open Addressing, p. 3, Linear Probing formula]{ref}
For capacity $m>0$, the <hash table probe> numbered $i$, starting at zero, inspects the <array index>
$$
p_i(k)=(h_m(k)+i)\bmod m,\qquad 0\leq i<m.
$$
The <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`.<Open Data Structures: An Introduction by Pat Morin/5.2 LinearHashTable: Linear Probing>[Open Data Structures: An Introduction by Pat Morin; Section 5.2, three entry types and find: nil stops lookup, del does not]{ref}
For an original example, take an eight-slot <array>, <integer> <hash table keys>, and the <hash function> $h_8(k)=k\bmod8$. 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>, are
$$
\begin{aligned}
0 &: 0, &8 &: 0\to1,\\
16 &: 0\to1\to2, &9 &: 1\to2\to3.
\end{aligned}
$$
The 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$.
\Image[/linear-probing-insertion-probe-traces.png]
{title=Four insertions build a <linear probing cluster>, followed by lookup of <hash table key> $16$}
{id=linear-probing-insertion-probe-traces}
{description=Original deterministic eight-slot example, with <hash table keys> shown and associated values omitted. Orange numbers count <hash table probes> in order; green marks placement or a match. Each row follows the preceding row.}
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\leq 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.<6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff/Lecture 10: Hashing III: Open Addressing>[6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff; Lecture 10: Hashing III: Open Addressing, pp. 1–2, probe permutation requirement and Search loop with m trials]{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.
Back to article page
