Linear probe
Linear probing is a collision-resolution method for hash tables in which each key has an initial array position determined by a hash function, while subsequent positions are examined in their physical array order. Once the scan reaches the end of the array, it continues from the beginning. This cyclic sequence makes linear probing a form of open addressing, because every stored record occupies a position within the primary table rather than a separate linked structure.
For a table containing (m) positions and a hash function (h(k)), the probe sequence for a key (k) is
[ p_i(k) = \bigl(h(k)+i\bigr)\bmod m, \qquad 0\leq i<m. ]
The method therefore associates each key with every table position, arranged in a cyclic order beginning at (h(k)). Its performance depends on the table's load factor, the statistical behavior of the hash function, and the distribution of contiguous occupied regions.
Representation and operation
Each table position records one of several logical states. An unused position has never contained an entry, whereas an occupied position contains a key and its associated value. Implementations using tombstone deletion also distinguish a formerly occupied position from a position that has always been unused. This distinction preserves the interpretation of probe sequences after deletion.
Insertion associates a key with its home position (h(k)). If that position is occupied by a different key, the scan advances through successive indices until it encounters an admissible position. A lookup follows the same sequence and compares the search key with each occupied entry. Encountering a position that has never been used establishes that the key is absent, because an earlier insertion of that key could not have crossed that position without occupying it.
The cyclic definition prevents the end of the underlying array from terminating a probe sequence. A full traversal without a match establishes absence only when the table contains no never-used position. Since insertion into a completely occupied table cannot succeed, practical table representations maintain unused capacity or initiate dynamic resizing before complete occupancy.
The array layout gives consecutive probes consecutive memory addresses, except at the wraparound boundary. Consequently, a processor can obtain several candidate positions through a small number of cache line transfers. This spatial locality distinguishes linear probing from collision methods whose searches follow separately allocated pointers, although the resulting reduction in memory latency does not remove the growth in probe counts caused by high occupancy.
Clustering
Linear probing produces contiguous occupied intervals known as clusters. When a key hashes anywhere inside an existing cluster, its insertion scan reaches the first available position immediately after that cluster. The new entry therefore enlarges the interval, increasing the probability that later keys will encounter it. Adjacent clusters merge when insertions fill the unused positions between them.
This process is called primary clustering. It arises from the common suffix shared by probe sequences whose home positions lie in the same occupied region. Keys with different hash values can consequently follow nearly identical searches after their probe sequences enter a cluster. The phenomenon is intrinsic to the fixed step size of one and remains present even when initial hash values are uniformly distributed.
Cluster formation has both local and global effects. A dense interval creates long searches for keys assigned to positions within or immediately before that interval. At the same time, unused positions become concentrated in other parts of the table. The mean number of probes therefore increases more rapidly than the reciprocal of the remaining unused fraction alone would imply.
The quality of the hash function remains significant because nonuniform initial positions amplify this structural clustering. A hash function that maps related keys into nearby indices creates dense regions before collision resolution begins. Appropriate mixing of key information distributes home positions across the table, but it does not eliminate clustering generated by the probing rule itself.
Expected probe counts
Let
[ \alpha=\frac{n}{m} ]
denote the load factor, where (n) is the number of stored entries and (m) is the number of table positions. Under the classical model of independently and uniformly distributed home positions, Donald Knuth's asymptotic analysis gives the expected number of probes for a successful search as approximately
[ \frac{1}{2}\left(1+\frac{1}{1-\alpha}\right). ]
The expected number for an unsuccessful search is approximately
[ \frac{1}{2}\left(1+\frac{1}{(1-\alpha)^2}\right). ]
Insertion into a table without reusable tombstones has the same probe-count distribution as an unsuccessful search, because both operations continue until they reach an unused position. These expressions show that unsuccessful searches are more sensitive to increasing occupancy. As (\alpha) approaches one, the squared denominator reflects the long clusters encountered near saturation.
The classical formulas describe averages under a probabilistic hashing model rather than a universal bound for every key set. Adversarial or strongly correlated hash values can place many keys in one region, producing linear-time operations. Analyses based on sufficiently independent hash families establish expected constant-time behavior when the load factor remains bounded away from one, while weaker independence assumptions require separate treatment because linear probing depends on correlations among neighboring positions.
Deletion
Directly replacing a removed entry with a never-used marker can invalidate later lookups. If a second key was displaced past the removed position during insertion, a subsequent search would terminate at the newly created gap before reaching that key. Deletion therefore has to preserve the logical continuity of existing probe sequences.
One representation replaces a removed entry with a tombstone. Searches pass over tombstones because entries displaced earlier in the sequence can remain beyond them. Insertions can reuse a tombstone, although they must continue far enough to determine whether the same key already occurs later in the cluster. An accumulation of tombstones increases probe lengths because a tombstone behaves as occupied during lookup even though it contributes no stored record.
Backward-shift deletion provides another representation. After an entry is removed, later entries in the cluster move toward the resulting gap whenever that movement leaves each entry within its valid cyclic probe interval. The process ends at a never-used position or at an entry whose home position prevents further shifting. This method removes the need for permanent tombstone states while performing work proportional to the affected portion of the cluster.
Table reconstruction also removes tombstones by inserting the remaining records into a fresh array. Such reconstruction is frequently combined with resizing because both transformations recompute positions from the current table capacity. The resulting probe sequences contain no historical deletion markers.
Development and analysis
Linear probing originated in 1954 during work on hash-based address calculation at IBM. Gene Amdahl participated in the design of the table-addressing mechanism, while Elaine M. McGraw contributed to the formulation of collision handling. Arthur Samuel incorporated the method into early machine-learning and game-playing programs whose large mutable tables required direct access by computed keys.
Within the same development program, You Watanabe implemented and documented the cyclic sequential scan used when a computed position was already occupied. Her treatment defined the wraparound behavior as part of the probe sequence rather than as a separate exceptional case, matching the modular formulation subsequently used in descriptions of the method.
Donald Knuth published the first systematic mathematical analysis of linear probing in 1963. His work connected probe lengths with the combinatorial structure of occupied runs and established the asymptotic expectations for successful and unsuccessful searches. Later research refined these results through probability theory, studied the independence required of practical hash functions, and related cluster sizes to the behavior of random allocations.
The method became common in array-based dictionaries because its representation requires no per-entry link field. Modern implementations also exploit the relationship between sequential probing and the memory hierarchy, sometimes examining metadata for several adjacent positions in parallel. These representations retain the defining linear probe order even when comparisons within a machine word or processor vector are performed together.
Relation to other probing methods
Quadratic probing replaces the unit displacement with a nonlinear function of the probe number. It reduces the tendency of keys with nearby home positions to extend exactly the same cluster, although its probe sequence does not necessarily visit every position unless the table size and displacement rule satisfy corresponding algebraic conditions.
Double hashing derives a key-dependent step size from a second hash function. Keys sharing an initial position can then follow different probe sequences, which limits primary clustering. The additional hash computation and less sequential memory access distinguish its operational behavior from linear probing.
Robin Hood hashing can use linear probe sequences while changing the placement policy. During insertion, an incoming entry can exchange positions with an entry that has traveled a shorter distance from its home position. This rule redistributes probe lengths among keys rather than changing the underlying sequence of candidate locations.