Hubbry Logo
search
logo
Linear probing avatar
Linear probing
Linear probing
current hub
2024440

Linear probing

logo
Community Hub0 Subscribers
Read side by side
Linear probing
View on Wikipedia
from Wikipedia

The collision between John Smith and Sandra Dee (both hashing to cell 873) is resolved by placing Sandra Dee at the next free location, cell 874.

Linear probing is a scheme in computer programming for resolving collisions in hash tables, data structures for maintaining a collection of key–value pairs and looking up the value associated with a given key. It was invented in 1954 by Gene Amdahl, Elaine M. McGraw, and Arthur Samuel (and, independently, by Andrey Yershov[1]) and first analyzed in 1963 by Donald Knuth.

Along with quadratic probing and double hashing, linear probing is a form of open addressing. In these schemes, each cell of a hash table stores a single key–value pair. When the hash function causes a collision by mapping a new key to a cell of the hash table that is already occupied by another key, linear probing searches the table for the closest following free location and inserts the new key there. Lookups are performed in the same way, by searching the table sequentially starting at the position given by the hash function, until finding a cell with a matching key or an empty cell.

As Thorup & Zhang (2012) write, "Hash tables are the most commonly used nontrivial data structures, and the most popular implementation on standard hardware uses linear probing, which is both fast and simple."[2] Linear probing can provide high performance because of its good locality of reference, but is more sensitive to the quality of its hash function than some other collision resolution schemes. It takes constant expected time per search, insertion, or deletion when implemented using a random hash function, a 5-independent hash function, or tabulation hashing. Good results can also be achieved in practice with other hash functions such as MurmurHash.[3]

Operations

[edit]

Linear probing is a component of open addressing schemes for using a hash table to solve the dictionary problem. In the dictionary problem, a data structure should maintain a collection of key–value pairs subject to operations that insert or delete pairs from the collection or that search for the value associated with a given key. In open addressing solutions to this problem, the data structure is an array T (the hash table) whose cells T[i] (when nonempty) each store a single key–value pair. A hash function is used to map each key into the cell of T where that key should be stored, typically scrambling the keys so that keys with similar values are not placed near each other in the table. A hash collision occurs when the hash function maps a key into a cell that is already occupied by a different key. Linear probing is a strategy for resolving collisions, by placing the new key into the closest following empty cell.[4][5]

[edit]

To search for a given key x, the cells of T are examined, beginning with the cell at index h(x) (where h is the hash function) and continuing to the adjacent cells h(x) + 1, h(x) + 2, ..., until finding either an empty cell or a cell whose stored key is x. If a cell containing the key is found, the search returns the value from that cell. Otherwise, if an empty cell is found, the key cannot be in the table, because it would have been placed in that cell in preference to any later cell that has not yet been searched. In this case, the search returns as its result that the key is not present in the dictionary.[4][5]

Insertion

[edit]

To insert a key–value pair (x,v) into the table (possibly replacing any existing pair with the same key), the insertion algorithm follows the same sequence of cells that would be followed for a search, until finding either an empty cell or a cell whose stored key is x. The new key–value pair is then placed into that cell.[4][5]

If the insertion would cause the load factor of the table (its fraction of occupied cells) to grow above some preset threshold, the whole table may be replaced by a new table, larger by a constant factor, with a new hash function, as in a dynamic array. Setting this threshold close to zero and using a high growth rate for the table size leads to faster hash table operations but greater memory usage than threshold values close to one and low growth rates. A common choice would be to double the table size when the load factor would exceed 1/2, causing the load factor to stay between 1/4 and 1/2.[6]

Deletion

[edit]
When a key–value pair is deleted, it may be necessary to move another pair backwards into its cell, to prevent searches for the moved key from finding an empty cell.

It is also possible to remove a key–value pair from the dictionary. However, it is not sufficient to do so by simply emptying its cell. This would affect searches for other keys that have a hash value earlier than the emptied cell, but that are stored in a position later than the emptied cell. The emptied cell would cause those searches to incorrectly report that the key is not present.

Instead, when a cell i is emptied, it is necessary to search forward through the following cells of the table until finding either another empty cell or a key that can be moved to cell i (that is, a key whose hash value is equal to or earlier than i). When an empty cell is found, then emptying cell i is safe and the deletion process terminates. But, when the search finds a key that can be moved to cell i, it performs this move. This has the effect of speeding up later searches for the moved key, but it also empties out another cell, later in the same block of occupied cells. The search for a movable key continues for the new emptied cell, in the same way, until it terminates by reaching a cell that was already empty. In this process of moving keys to earlier cells, each key is examined only once. Therefore, the time to complete the whole process is proportional to the length of the block of occupied cells containing the deleted key, matching the running time of the other hash table operations.[4]

Alternatively, it is possible to use a lazy deletion strategy in which a key–value pair is removed by replacing the value by a special flag value indicating a deleted key. However, these flag values will contribute to the load factor of the hash table. With this strategy, it may become necessary to clean the flag values out of the array and rehash all the remaining key–value pairs once too large a fraction of the array becomes occupied by deleted keys.[4][5]

Properties

[edit]

Linear probing provides good locality of reference, which causes it to require few uncached memory accesses per operation. Because of this, for low to moderate load factors, it can provide very high performance. However, compared to some other open addressing strategies, its performance degrades more quickly at high load factors because of primary clustering, a tendency for one collision to cause more nearby collisions.[4] Additionally, achieving good performance with this method requires a higher-quality hash function than for some other collision resolution schemes.[7] When used with low-quality hash functions that fail to eliminate nonuniformities in the input distribution, linear probing can be slower than other open-addressing strategies such as double hashing, which probes a sequence of cells whose separation is determined by a second hash function, or quadratic probing, where the size of each step varies depending on its position within the probe sequence.[8]

Analysis

[edit]

Using linear probing, dictionary operations can be implemented in constant expected time. In other words, insert, remove and search operations can be implemented in O(1), as long as the load factor of the hash table is a constant strictly less than one.[9]

In more detail, the time for any particular operation (a search, insertion, or deletion) is proportional to the length of the contiguous block of occupied cells at which the operation starts. If all starting cells are equally likely, in a hash table with N cells, then a maximal block of k occupied cells will have probability k/N of containing the starting location of a search, and will take time O(k) whenever it is the starting location. Therefore, the expected time for an operation can be calculated as the product of these two terms, O(k2/N), summed over all of the maximal blocks of contiguous cells in the table. A similar sum of squared block lengths gives the expected time bound for a random hash function (rather than for a random starting location into a specific state of the hash table), by summing over all the blocks that could exist (rather than the ones that actually exist in a given state of the table), and multiplying the term for each potential block by the probability that the block is actually occupied. That is, defining Block(i,k) to be the event that there is a maximal contiguous block of occupied cells of length k beginning at index i, the expected time per operation is

This formula can be simplified by replacing Block(i,k) by a simpler necessary condition Full(k), the event that at least k elements have hash values that lie within a block of cells of length k. After this replacement, the value within the sum no longer depends on i, and the 1/N factor cancels the N terms of the outer summation. These simplifications lead to the bound

But by the multiplicative form of the Chernoff bound, when the load factor is bounded away from one, the probability that a block of length k contains at least k hashed values is exponentially small as a function of k, causing this sum to be bounded by a constant independent of n.[4] It is also possible to perform the same analysis using Stirling's approximation instead of the Chernoff bound to estimate the probability that a block contains exactly k hashed values.[5][10]

In terms of the load factor α, the expected time to perform a successful search on a random key is O(1 + 1/(1 − α)), and the expected time to perform an unsuccessful search (or the insertion of a new key) is O(1 + 1/(1 − α)2).[11] For constant load factors, with high probability, the longest probe sequence (among the probe sequences for all keys stored in the table) has logarithmic length.[12]

Primary Clustering

[edit]
Main article: Primary clustering

Linear probing hash tables suffer from a problem known as primary clustering, in which elements to group together into long contiguous runs.[13][11] In terms of the load factor α, the expected length of the run containing a given element is .[11] This is why insertions take time , as opposed to the running time of achieved by other open-addressed hash tables such as uniform probing and double hashing.[11] Primary clustering also affects unsuccessful searches, since like insertions, they must travel to the end of a run.[11] Some variations of linear probing are able to achieve better bounds for unsuccessful searches and insertions, by using techniques that reduce primary clustering.[14]

Choice of hash function

[edit]

Because linear probing is especially sensitive to unevenly distributed hash values,[8] it is important to combine it with a high-quality hash function that does not produce such irregularities.

The analysis above assumes that each key's hash is a random number independent of the hashes of all the other keys. This assumption is unrealistic for most applications of hashing. However, random or pseudorandom hash values may be used when hashing objects by their identity rather than by their value. For instance, this is done using linear probing by the IdentityHashMap class of the Java collections framework.[15] The hash value that this class associates with each object, its identityHashCode, is guaranteed to remain fixed for the lifetime of an object but is otherwise arbitrary.[16] Because the identityHashCode is constructed only once per object, and is not required to be related to the object's address or value, its construction may involve slower computations such as the call to a random or pseudorandom number generator. For instance, Java 8 uses an Xorshift pseudorandom number generator to construct these values.[17]

For most applications of hashing, it is necessary to compute the hash function for each value every time that it is hashed, rather than once when its object is created. In such applications, random or pseudorandom numbers cannot be used as hash values, because then different objects with the same value would have different hashes. And cryptographic hash functions (which are designed to be computationally indistinguishable from truly random functions) are usually too slow to be used in hash tables.[18] Instead, other methods for constructing hash functions have been devised. These methods compute the hash function quickly, and can be proven to work well with linear probing. In particular, linear probing has been analyzed from the framework of k-independent hashing, a class of hash functions that are initialized from a small random seed and that are equally likely to map any k-tuple of distinct keys to any k-tuple of indexes. The parameter k can be thought of as a measure of hash function quality: the larger k is, the more time it will take to compute the hash function but it will behave more similarly to completely random functions. For linear probing, 5-independence is enough to guarantee constant expected time per operation,[19] while some 4-independent hash functions perform badly, taking up to logarithmic time per operation.[7]

Another method of constructing hash functions with both high quality and practical speed is tabulation hashing. In this method, the hash value for a key is computed by using each byte of the key as an index into a table of random numbers (with a different table for each byte position). The numbers from those table cells are then combined by a bitwise exclusive or operation. Hash functions constructed this way are only 3-independent. Nevertheless, linear probing using these hash functions takes constant expected time per operation.[5][20] Both tabulation hashing and standard methods for generating 5-independent hash functions are limited to keys that have a fixed number of bits. To handle strings or other types of variable-length keys, it is possible to compose a simpler universal hashing technique that maps the keys to intermediate values and a higher quality (5-independent or tabulation) hash function that maps the intermediate values to hash table indices.[2][21]

In an experimental comparison, Richter et al. found that the Multiply-Shift family of hash functions (defined as ) was "the fastest hash function when integrated with all hashing schemes, i.e., producing the highest throughputs and also of good quality" whereas tabulation hashing produced "the lowest throughput".[3] They point out that each table look-up require several cycles, being more expensive than simple arithmetic operations. They also found MurmurHash to be superior than tabulation hashing: "By studying the results provided by Mult and Murmur, we think that the trade-off for by tabulation (...) is less attractive in practice".

History

[edit]

The idea of an associative array that allows data to be accessed by its value rather than by its address dates back to the mid-1940s in the work of Konrad Zuse and Vannevar Bush,[22] but hash tables were not described until 1953, in an IBM memorandum by Hans Peter Luhn. Luhn used a different collision resolution method, chaining, rather than linear probing.[23]

Knuth (1963) summarizes the early history of linear probing. It was the first open addressing method, and was originally synonymous with open addressing. According to Knuth, it was first used by Gene Amdahl, Elaine M. McGraw (née Boehme), and Arthur Samuel in 1954, in an assembler program for the IBM 701 computer.[9] The first published description of linear probing is by Peterson (1957),[9] who also credits Samuel, Amdahl, and Boehme but adds that "the system is so natural, that it very likely may have been conceived independently by others either before or since that time".[24] Another early publication of this method was by Soviet researcher Andrey Ershov, in 1958.[25]

The first theoretical analysis of linear probing, showing that it takes constant expected time per operation with random hash functions, was given by Knuth.[9] Sedgewick calls Knuth's work "a landmark in the analysis of algorithms".[11] Significant later developments include a more detailed analysis of the probability distribution of the running time,[26][27] and the proof that linear probing runs in constant time per operation with practically usable hash functions rather than with the idealized random functions assumed by earlier analysis.[19][20]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Linear probing

View on Grokipedia
from Grokipedia
Linear probing is a collision resolution strategy employed in open-addressing hash tables, a data structure for storing key-value pairs where all elements reside directly in an array of fixed size.[1] Upon encountering a collision during insertion—when the computed hash index is already occupied—the algorithm probes sequentially forward from that position by incrementing the index by 1 modulo the table size until an empty slot is found, at which point the new element is inserted.[2] This method, also known as linear open addressing, contrasts with chaining by avoiding linked lists and instead redistributing collided elements within the primary array.[3] For searching and deletion, linear probing follows the same probe sequence as insertion to maintain consistency. In a search, starting from the initial hash index, the algorithm checks each subsequent slot until it finds the target key, an empty slot (indicating absence), or a full cycle of the table.[1] Deletion requires marking slots as "deleted" rather than emptying them, to preserve probe paths for future operations; a full removal occurs only during rehashing when the table is resized, typically doubling in capacity and reinserting all elements into a new array.[4] This approach ensures that searches and insertions remain efficient as long as the load factor α (ratio of elements to table size) stays below approximately 0.75.[5] One key advantage of linear probing is its simplicity in implementation and favorable cache locality, as probes access consecutive memory locations, potentially outperforming chained hashing in modern hardware.[6] However, it suffers from primary clustering, where consecutive occupied slots form dense groups, lengthening probe sequences for nearby keys and degrading performance as the table fills; this can lead to up to O(n worst-case time for operations in highly loaded tables.[7] To mitigate clustering, variants like quadratic probing or double hashing adjust the probe step size, though linear probing remains widely used in applications prioritizing speed over load tolerance.[8] Performance analysis under the uniform hashing assumption reveals that the average number of probes for a successful search in a linear probing hash table is 12(1+11−α)\frac{1}{2} \left(1 + \frac{1}{1 - \alpha}\right), while unsuccessful searches average 12(1+1(1−α)2)\frac{1}{2} \left(1 + \frac{1}{(1 - \alpha)^2}\right), highlighting the quadratic sensitivity to load factor.[9] These formulas, derived from probabilistic models, underscore the importance of resizing before α exceeds 0.5 for balanced efficiency.[10]

Background

Hash tables and collision resolution

A hash table is a data structure that stores key-value pairs in an array of fixed size, using a hash function to compute an index for each key, thereby enabling average-case constant-time O(1) performance for insertions, deletions, and lookups.[11][12] The hash function transforms a key into a non-negative integer within the range of array indices, ideally distributing keys uniformly to minimize overlaps.[11] Collisions occur when two or more distinct keys map to the same array index via the hash function, a situation inevitable given the finite table size relative to the potentially vast key space.[11][13] For example, in a table of size 10, the keys "David" and "Eva" might both hash to index 4, requiring a resolution strategy to maintain data integrity and accessibility.[11] To address collisions, hash tables employ resolution techniques such as separate chaining or open addressing. In separate chaining, each array slot holds a linked list, with colliding keys appended to the list at the hashed index; this approach simplifies implementation and supports high occupancy without severe degradation, though it incurs extra space for list pointers and may involve traversal costs.[11][13] Conversely, open addressing resolves collisions by searching for an unoccupied slot within the array itself, promoting space efficiency by eliminating pointer overhead, but risking longer probe sequences as the table fills, which can amplify access times.[11][12] The load factor α, defined as the number of keys n divided by the table size m (α = n/m), quantifies table utilization and directly influences collision frequency; values approaching 1 heighten resolution demands, potentially eroding the O(1) performance guarantee.[11][12] Linear probing serves as one technique within the open addressing paradigm.[12]

Open addressing overview

Open addressing, also known as closed hashing, is a collision resolution technique in hash tables where all elements are stored directly within the table's array, without using external lists or chains. When a collision occurs—meaning the computed hash index for a key is already occupied—the method resolves it by systematically probing subsequent slots in the array to find an empty one, guided by a secondary probe function $ h(k, i) $, where $ k $ is the key and $ i $ is the probe count starting from 0. This approach was first formalized as a practical method for random-access storage systems.[14] Unlike separate chaining, which appends collided keys to linked lists at each array slot and incurs overhead from pointer storage, open addressing maintains a single contiguous array, reducing memory usage by avoiding pointers and enabling more compact data representation. However, this efficiency comes at the cost of potentially longer probe sequences as the load factor—the ratio of stored elements to array size—increases, since unsuccessful searches must traverse occupied slots until an empty one or the key is found.[15] Several variants of open addressing differ in how the probe sequence is generated to mitigate clustering, where consecutive probes tend to examine nearby slots. Linear probing uses a constant step size of 1, advancing sequentially from the initial hash position. Quadratic probing employs a step size of $ i^2 $, producing a nonlinear sequence that spreads probes more evenly. Double hashing utilizes a secondary hash function to determine the step size, typically $ h_2(k) $, yielding the probe offset as $ i \times h_2(k) \mod m $, where $ m $ is the table size, for greater permutation quality. The general insertion procedure in open addressing follows this skeleton: 
function insert(key k):
    i ← 0
    repeat:
        slot ← (h₁(k) + [probe](/page/P.R.O.B.E.)(k, i)) mod m
        if table[slot] is empty or is deleted:
            table[slot] ← k
            return
        i ← i + 1
    until i == m  // table full, handle resize or failure
Here, $ h_1 $ is the primary hash, and probe is the variant-specific function (e.g., probe(k, i) = i for linear). Search and verification follow a similar loop, terminating on match, empty slot, or exhaustion.[15][16] Open addressing offers advantages in modern systems, particularly cache efficiency, as probe sequences often access contiguous memory locations, improving locality and reducing cache misses compared to scattered chain traversals. Nonetheless, it presents challenges in deletion, where simply removing an element could disrupt probe paths for other keys, necessitating markers like tombstones to preserve sequence integrity during searches. Additionally, the method is prone to clustering, where insertions form dense groups of occupied slots, exacerbating probe lengths and limiting effective load factors to around 0.7–0.8 for practicality.[17][18][15]

Core operations

Search procedure

In linear probing, the search procedure begins by computing the initial hash position $ h(k) = \hash(k) \mod m $, where $ k $ is the key, $ \hash $ is the hash function, and $ m $ is the table size. The algorithm then probes sequentially forward from this position using the probe sequence $ h(k, i) = (h(k) + i) \mod m $ for $ i = 0, 1, 2, \dots $, examining each slot until it either locates the key $ k $, encounters an empty slot (indicating the key is absent), or completes a full cycle through the table (indicating the table is full and the key is not present).[19][20] The following pseudocode illustrates the search algorithm, incorporating the loop termination conditions: 
Algorithm Search(table T, key k, size m)
    i ← 0
    while true do
        j ← (hash(k) + i) mod m
        if T[j] is empty then
            return not found  // Key absent
        if T[j].key = k then
            return found  // Key located at j
        i ← i + 1
        if i = m then
            return not found  // Table full, key absent
    end while
This procedure ensures that all potential positions in the probe sequence are checked without prematurely stopping unless justified by an empty slot or full cycle.[19][20] Consider a hash table of size 4 with initial empty slots, after insertions of "apple" (hash value 1) and "banana" (hash value 3), resulting in slots: [empty, "apple", empty, "banana"]. Searching for "apple" starts at index 1, finds the key immediately, and returns success after one probe. In contrast, searching for "cherry" (hash value 0) probes index 0 (empty), terminates immediately, and returns not found.[21][22] To support deletions without disrupting searches, deleted slots are marked as occupied (e.g., with a special "deleted" indicator) rather than empty, requiring the search to continue probing past them until an empty slot or the key is found.[19][20]

Insertion process

In linear probing, the insertion process begins by computing the initial hash value $ h'(k) $ for the key $ k $, where the hash table $ T $ has size $ m $. The algorithm then follows the probe sequence $ h(k, i) = (h'(k) + i) \mod m $ for $ i = 0, 1, \dots $, sequentially checking each slot starting from $ h'(k) $. If the key $ k $ is found at any slot, the insertion terminates without adding a duplicate. Otherwise, the key is placed in the first empty slot encountered (typically denoted as NIL). If the probing completes a full cycle through all $ m $ slots without finding an empty one, the table is considered full, and an overflow error is raised.[23] The following pseudocode outlines the insertion procedure, adapted from standard open-addressing implementations: 
HASH-INSERT(T, k)
1  i ← 0
2  repeat
3      j ← (h'(k) + i) mod m
4      if T[j] is empty
5          T[j] ← k
6          return j
7      else if T[j] = k
8          return j  // key already present
9      i ← i + 1
10 until i = m
11 error "[hash table](/page/Hash_table) overflow"
This procedure ensures that insertions respect the probe sequences used for searches, preventing overwrites of existing keys.[23] To maintain performance, practical implementations monitor the load factor $ \alpha = n/m $ (where $ n $ is the number of elements) and suggest resizing the table—typically by doubling $ m $ and rehashing all elements—when $ \alpha $ exceeds a threshold like 0.7, as higher loads degrade probe lengths significantly in linear probing.[24] For example, consider a hash table of size $ m = 5 $ with an initial hash function where $ h'(\text{"dog"}) = 2 $, and slots 2 and 3 already occupied by other keys. The probe sequence starts at slot 2 (occupied), moves to slot 3 (occupied), then slot 4 (empty), inserting "dog" there.[23] The insertion process relies on the same probing mechanism as search to detect duplicates and locate empty slots, ensuring consistency across operations without overwriting valid entries.[23]

Deletion handling

Deletion in linear probing hash tables presents a challenge because simply setting a slot to empty after removing a key can disrupt the probe sequences of other keys that would have continued searching through that position, potentially causing those keys to become unfindable during subsequent searches. To address this, the standard approach uses special markers known as tombstones or "deleted" flags placed in the slots of removed keys. These markers indicate that the slot is available for future insertions but is treated as occupied during searches to preserve the integrity of probe sequences. The deletion algorithm begins by performing the standard linear probing search to locate the key. If the key is found, the slot's value is replaced with the deleted marker rather than being set to empty. Searches and insertions are modified accordingly: during a search, if a tombstone is encountered, the probing continues as if the slot were occupied by a non-matching key; for insertion, tombstones are considered available slots, allowing new keys to be placed there and potentially reusing the space without breaking existing chains. The following pseudocode illustrates the deletion process: 
function DELETE(key):
    i ← 0
    start ← HASH(key) mod m
    while true do
        j ← (start + i) mod m
        if table[j] is empty:
            return  // key not found
        if table[j] = key:
            table[j] ← deleted  // place tombstone
            return
        i ← i + 1
        if i = m:
            return  // table full, key not found
    end while
This ensures that probe sequences remain continuous for other elements. However, repeated deletions lead to an accumulation of tombstones, which effectively increase the load factor by occupying slots without holding useful data, thereby lengthening average probe sequences and degrading overall performance over time. To mitigate this, implementations often monitor the number of tombstones and trigger periodic rehashing into a larger table or compaction to remove them when they reach a threshold, such as half the table size. Consider an example with a hash table using linear probing and a simple hash function where both "apple" and "banana" hash to position 2. "Apple" is inserted first at 2. "Banana" collides at 2, probes to 3 (empty), and is inserted there (position 1 and 4+ empty). Deleting "apple" at position 2 by setting it to a tombstone allows a search for "banana" to start at 2 (tombstone, continue probing), reach 3, and find it correctly, whereas setting position 2 to empty would stop the search prematurely. Subsequent insertion of a new key hashing to 2 could then reuse the tombstone slot.

Performance analysis

Load factor impact

The load factor α in linear probing is defined as the ratio of the number of stored elements n to the table size m, or α = n/m.[25] Linear probing achieves efficient performance when α remains below 0.7–0.8, but degrades sharply as α nears 1.0 due to substantially longer probe sequences required for operations.[5][25] To sustain efficiency, implementations typically resize the table by doubling its size and rehashing all elements when α exceeds a threshold such as 0.7, which keeps the load factor in a range where probe lengths stay manageable.[26] Empirical analysis under uniform hashing reveals that at α = 0.5, the expected probes for a successful search average about 1.5, while unsuccessful searches or insertions require around 2.5; at α = 0.9, these rise to approximately 5.5 and over 50 probes, respectively, highlighting the method's vulnerability at high loads.[25]
Load Factor αSuccessful Search (Probes)Unsuccessful Search (Probes)
0.251.21.4
0.501.52.5
0.672.05.0
0.752.58.5
0.905.550.5
Compared to chaining, linear probing in open addressing is more sensitive to elevated α since the table fills to capacity at α = 1, but offers speed advantages at low α by eliminating pointer traversals in linked lists.[26]

Probe sequence length

In linear probing, the expected number of probes for an unsuccessful search is given by 12(1+1(1−α)2)\frac{1}{2} \left(1 + \frac{1}{(1 - \alpha)^2}\right), where α\alpha denotes the load factor, representing the ratio of occupied slots to total table size. This formula arises from probabilistic analysis assuming uniform hashing, where the positions of empty slots follow a geometric distribution with success probability 1−α1 - \alpha. Specifically, the probability that a probe sequence requires exactly kk probes is (1−α)αk−1(1 - \alpha) \alpha^{k-1} under the approximation of independent probes, leading to the expected value via summation: ∑k=1∞k(1−α)αk−1=11−α\sum_{k=1}^{\infty} k (1 - \alpha) \alpha^{k-1} = \frac{1}{1 - \alpha}; however, the more precise derivation in linear probing accounts for the sequential nature by averaging over the squared term to yield the quadratic form.[27] For a successful search, the expected probe length simplifies to 12(1+11−α)\frac{1}{2} \left(1 + \frac{1}{1 - \alpha}\right), derived similarly by considering the average position of inserted keys relative to their hash locations, again rooted in the geometric distribution of empty slots encountered during insertions. This reflects the fact that successful searches tend to probe fewer locations on average, as they terminate upon finding the key rather than an empty slot. In the worst case, probe sequences can require up to O(m)O(m) probes, where mm is the table size, occurring when the table is nearly full or when long clusters force traversal of most slots. The distribution of probe lengths approximates an exponential (or discrete geometric) form at moderate load factors α\alpha.[27] Theoretical predictions from these equations align closely with empirical results from simulations for load factors up to α=0.8\alpha = 0.8, beyond which clustering effects begin to deviate outcomes from the ideal model.[28]

Clustering issues

Primary clustering explanation

Primary clustering is a phenomenon observed in linear probing hash tables, where keys that hash to nearby indices tend to form long, contiguous runs of occupied slots, thereby extending the probe sequences for subsequent insertions and searches in that region of the table. This occurs because the probe sequence in linear probing advances by a fixed step size of 1, causing collided keys to sequentially fill adjacent slots and create dense clusters around the initial hash locations. The root cause stems from this uniform linear progression: when multiple keys hash to slots in close proximity—say, indices 5, 6, or 7—they occupy a continuous block starting from the earliest available slot in that range, forcing later probes to traverse the entire cluster before finding an empty slot or the target key. For instance, consider a hash table of size 13 with initial hashes placing keys at positions 5 (occupies 5), then 6 (occupies 6), and another at 5 (collides and occupies 7); a subsequent key hashing to 7 now must probe through 7 (occupied), 8, and beyond, extending the effective run to slots 5–7 and growing the cluster further with each similar collision.[4] To illustrate cluster growth, envision a linear array representing the hash table slots (0 to 12), initially all empty (denoted as ·). After inserting a key hashing to slot 3 (occupies 3: · · · X · · · · · · · · ·), a second key hashing to 4 (occupies 4: · · · X X · · · · · · · ·), and a third hashing to 3 (probes to 5: · · · X X X · · · · · · ·), a cluster forms at positions 3–5. A fourth key hashing to 2 (if empty, occupies 2, but if another collision arises nearby, it joins or extends the run: · · X X X X · · · · · · ·). Over repeated insertions near this region, the cluster expands contiguously, as shown by the progressive filling of sequential slots.[29][30] This primary clustering in linear probing differs from secondary clustering seen in other open-addressing schemes like quadratic or double hashing, where the issue arises specifically when multiple keys share the exact same initial hash value and thus follow identical probe sequences, rather than from the adjacency of different hash values.[31]

Effects on performance

Primary clustering degrades the performance of linear probing by creating long runs of occupied slots, which significantly increase the length of probe sequences in affected regions. In the worst case, insertions or searches starting near a cluster can require traversing the entire run, leading to probe counts that approximate O(1/(1 - \alpha)^2) for unsuccessful operations at load factor \alpha, far exceeding the expected O(1) amortized time under uniform distribution assumptions. This results in practical average probe lengths that are 2-3 times longer than those in clustering-resistant methods like double hashing at moderate load factors, with variance in access times rising due to some operations resolving quickly while others suffer extended traversals through clusters.[19] The sequential nature of linear probing probes benefits cache locality by accessing contiguous memory locations, often yielding fewer cache misses than scattered probing schemes. However, in clustered regions, long probe sequences can span multiple cache lines, incurring misses at cluster boundaries and amplifying the overall slowdown, particularly for larger table sizes where spatial locality advantages diminish.[17] Empirical analyses confirm these impacts, showing linear probing's average unsuccessful probe length rising sharply with clustering. For instance, at \alpha = 0.7, linear probing requires approximately 6 probes on average for unsuccessful searches, compared to about 3.3 for double hashing, representing a roughly 80% slowdown in probe count due to clustering effects. At higher loads like \alpha = 0.9, this gap widens to 5 times more probes (50.5 vs. 10). The following table summarizes average unsuccessful probe lengths from theoretical models and simulations, highlighting the degradation:
Load Factor (\alpha)Linear Probing (Clustered)Double Hashing (Uniform)Slowdown Factor
0.52.52.01.25x
0.76.13.31.85x
0.950.510.05.05x
These results underscore how clustering transforms linear probing's theoretical efficiency into practical bottlenecks at loads above 0.5.[19][17] Deletions compound these issues through the use of tombstones (marked deleted slots), which do not create gaps but force subsequent probes to continue past them, effectively extending cluster lengths and increasing the number of steps needed to find empty slots or confirm absences. This raises the effective load factor and probe counts, with analyses showing insertions can take \Theta(x^2) time at load factor 1 - 1/x without mitigation, though tombstones introduce some anti-clustering in mixed workloads. In practice, frequent deletions can inflate average search times beyond insertion-only scenarios at \alpha = 0.7, necessitating periodic rehashing to restore performance.[32]

Hash function selection

Ideal hash function properties

For optimal performance in linear probing, a hash function must generate values that are uniformly distributed across the table indices [0, m-1], where m denotes the table size, thereby reducing the probability of initial collisions among inserted keys.[33] This property aligns with the simple uniform hashing assumption, under which each key hashes independently and with equal probability to any slot, promoting even spread and minimizing early clustering tendencies.[27] Furthermore, the hash function should demonstrate the avalanche effect, such that even a minor alteration in the input key—such as flipping a single bit—produces a markedly different hash value, on average changing roughly half the output bits to disrupt potential patterns in key similarities.[34] This diffusion quality ensures that related keys do not predictably map to nearby slots, which is particularly beneficial in linear probing where sequential searches amplify localized biases. To avoid inherent correlations between hash outputs and the linear probe increments (which could exacerbate natural clustering in modular arithmetic), the function requires a degree of statistical independence from the probing mechanism; research establishes that at least 5-wise independent hashing suffices to achieve expected constant-time operations by bounding probe sequence lengths effectively.[35] Such well-designed hash functions interact favorably with the load factor α (the ratio of occupied slots to table size), as their uniformity and independence postpone the buildup of probe chains, sustaining efficient insertions and searches at higher α values—typically up to around 0.5 to 0.7—before degradation sets in.[33] In implementation, the uniformity of candidate hash functions is empirically assessed via the chi-squared goodness-of-fit test, which compares the observed frequency of hash values across bins against the expected uniform distribution, with low p-values indicating non-random deviations that could impair probing efficiency.[36]

Practical choices and examples

For integer keys, a simple and common hash function in linear probing tables is the modulo operation, defined as $ h(k) = k \mod m $, where $ k $ is the key and $ m $ is the table size; this maps keys uniformly to slots when $ m $ is chosen appropriately.[11] For example, in a table of size 10, inserting keys 5, 15, and 25 would all hash to slot 5, requiring linear probing to resolve collisions by checking subsequent slots.[4] For string keys, polynomial rolling hashes are widely used to treat the string as a base-$ b $ number in base-$ m $ arithmetic, computed as $ h(s) = \left( \sum_{i=0}^{n-1} s[i] \cdot b^{n-1-i} \right) \mod m $, where $ s[i] $ is the character code at position $ i $, $ n $ is the string length, and $ b $ is typically 31 or 37 to balance computation speed and distribution quality.[37][38] This approach avoids overflow issues by computing incrementally: initialize hash to 0, then for each character $ c $, update as $ \text{hash} = (\text{hash} \cdot b + c) \mod m $.[37] 
int hash = 0;
for (int i = 0; i < s.[length](/page/Length)(); i++) {
    hash = (hash * 31 + s.charAt(i)) % m;
}
In implementations like those in educational algorithms libraries, Java's built-in String.hashCode() method—which uses a polynomial rolling hash with base 31—is directly adapted for linear probing by taking the absolute value and modulo $ m $, ensuring compatibility with the table size while leveraging the language's standard for string hashing.[39] For instance, the LinearProbingHashST class computes the initial probe as hash = (key.hashCode() & 0x7fffffff) % m, then applies linear offsets.[39] Practical trade-offs favor simple modulo or polynomial hashes for their computational speed in general-purpose linear probing tables, as they require only basic arithmetic operations and achieve good uniformity without excessive overhead.[22] In contrast, non-cryptographic hashes like MurmurHash offer superior avalanche properties for better distribution against patterned inputs, making them suitable for high-performance scenarios, but they involve more complex bit manipulations that increase computation time, rendering them overkill for typical non-security-sensitive uses. Cryptographic hashes, such as SHA-256, provide strong collision resistance but are significantly slower due to their security-focused design, and are rarely used in linear probing unless data integrity is paramount.[22] During rehashing upon table resize, selecting a new size $ m $ that is prime is essential to preserve hash uniformity, as primes minimize systematic biases in the modulo distribution for common key patterns, reducing clustering in linear probing.[22][40] For example, resizing from 100 to the next prime (e.g., 101) ensures that previously clustered probes spread more evenly under the same hash function.[22]

Historical development

Origins and key contributors

Linear probing emerged in the early 1950s as a collision resolution technique within open addressing schemes for hash tables, developed by a team of IBM researchers including Gene Amdahl, Elaine M. Boehme (later McGraw), Nathaniel Rochester, and Arthur Samuel. Their work was part of an assembler program for the IBM 701, one of the first commercial scientific computers, where efficient symbol table management required handling key collisions without external storage overflow. This innovation allowed for simple, memory-resident lookups by sequentially probing adjacent slots, addressing the limitations of early hashing methods that relied on chaining or rehashing.[41] The method gained formal recognition through W. Wesley Peterson's seminal 1957 paper, "Addressing for Random-Access Storage," published in the IBM Journal of Research and Development. In this work, Peterson defined open addressing and provided the first detailed analysis of linear probing's performance for random-access file systems, estimating access times and highlighting its advantages in speed and flexibility over traditional sequential or sorted indexing. Independently, Soviet computer scientist Andrey P. Ershov described a similar linear open addressing approach in 1958 (originally presented in 1957), based on empirical tests for programming language implementations.[41] Linear probing arose amid the transition from punched-card batch processing to direct-access storage devices in the 1950s, where punched-card systems demanded faster, non-sequential data retrieval for indexing large files without exhaustive sorting. Unlike earlier methods that processed records in fixed order, linear probing enabled approximate random access, reducing I/O operations in emerging drum and disk-based systems.[41] By the early 1960s, the technique saw adoption in IBM's file organization and database prototypes, incorporating hashing principles for efficient record retrieval in commercial data processing applications.

Evolution and related methods

In the 1970s, refinements to linear probing addressed key operational challenges, particularly the handling of deletions. Donald Knuth formalized the use of tombstones—special markers for deleted entries—to preserve the integrity of probe sequences during searches and insertions, preventing the disruption of subsequent probes that could occur if slots were simply emptied.[42] This approach ensured that deletions did not break the chain of occupied slots, maintaining the expected performance bounds analyzed in Knuth's work.[42] By the 1980s, linear probing gained practical adoption in programming languages and standard libraries. The hsearch function, part of the POSIX standard and implemented in systems like GNU C Library, utilized linear probing for open-addressing hash tables, providing a simple mechanism for managing key-value pairs in resource-constrained environments. This integration highlighted linear probing's appeal for straightforward implementations without dynamic memory allocation. Linear probing's primary clustering issues, where consecutive probes form long runs of occupied slots, directly inspired related collision resolution methods. Double hashing, which employs a secondary hash function to compute variable probe steps, emerged as an early variant to mitigate this clustering by distributing probes more uniformly across the table.[43] As a modern descendant, cuckoo hashing (introduced in 2001) builds on probing concepts by allowing key relocations between multiple hash locations, achieving constant-time worst-case lookups while avoiding the linear scan's degradation.[44] Post-2000 optimizations further evolved linear probing for contemporary hardware. Hopscotch hashing, proposed in 2008, enhances locality by restricting entries to a fixed "neighborhood" around their ideal hash position, reducing cache misses and supporting higher load factors than standard linear probing without extensive rehashing.[45] These advancements addressed lingering inefficiencies in cache-sensitive applications. Despite these developments, linear probing has declined in favor of separate chaining for high-load scenarios, where clustering causes probe lengths to grow quadratically, leading to performance bottlenecks beyond load factors of 0.7.[46] It persists in modern uses like CPython's dictionary implementation (as of Python 3.12), which employs open addressing with probing variants valued for their cache efficiency and simplicity, and in embedded systems where pointer-free structures minimize memory overhead.[47]

References

  1. Linear probing – Clayton Cafiero - University of Vermont
  2. 15.6. Collision Resolution - OpenDSA
  3. [PDF] Collision Resolution
  4. [PDF] Lecture 4: Hashing, Chaining, and Probing Analysis - Rice University
  5. [PDF] CMSC 420: Lecture 16 Hashing - UMD Computer Science
  6. [PDF] Lecture 10: Hash Collision Resolutions - Washington
  7. [PDF] CSE 100: HASHING
  8. [PDF] Hash Tables - GMU CS Department
  9. [PDF] Hash Tables - Algorithms, 4th Edition
  10. [PDF] Hash Table Analysis - Rose-Hulman
  11. [PDF] Chapter 5. Hash Tables
  12. [PDF] Lecture 16 - UCSD CSE
  13. 9.4. Separate Chaining — Data Structures and Algorithms
  14. Addressing for Random-Access Storage | Semantic Scholar
  15. The art of computer programming: sorting and searching (volume 3 ...
  16. Universal Classes of Hash Functions - Semantic Scholar
  17. [PDF] How Caching Affects Hashing - CS@Cornell
  18. [PDF] On Deletions in Open Addressing Hashing - UPCommons
  19. [PDF] Chapter 19 Hashing - CMU School of Computer Science
  20. [PDF] Hash Tables
  21. Open Addressing: Handling collision in hashing - Emory CS
  22. [PDF] CS 3137 Class Notes 1 What is Hashing?
  23. None
  24. 19.5 Resizing & Hash Table Performance | CS61B Textbook
  25. [PDF] Lecture 24 — Hash Tables - CMU School of Computer Science
  26. None
  27. [PDF] Contents 1 Open-address hash tables - People | MIT CSAIL
  28. [PDF] Tabulation Based 5-Universal Hashing and Linear Probing
  29. [PDF] CSE 332 - Washington
  30. Hashing Review - andrew.cmu.ed
  31. [PDF] CMSC 420: Lecture 11 Hashing - Handling Collisions
  32. Linear Probing Revisited: Tombstones Mark the Death of Primary ...
  33. [PDF] Algorithms - cs.Princeton
  34. CS202 Lecture notes -- Hashing - UTK-EECS
  35. [cs/0612055] Linear Probing with Constant Independence - arXiv
  36. [PDF] CS 310: Hashing Basics and Hash Functions - GMU CS Department
  37. [PDF] CMSC 341 Lecture 17 Hashing, Parts 1 & 2 - UMBC
  38. LinearProbingHashST.java - Algorithms, 4th Edition
  39. [PDF] Hashing
  40. [PDF] Sorting & Searching § Chapter 6, Searching: Hashing: History
  41. Addressing for random-access storage - ACM Digital Library
  42. (PDF) The Legendary IBM 1401 Data Processing System
  43. The Art of Computer Programming (TAOCP)
  44. The analysis of double hashing(Extended Abstract)
  45. [PDF] Cuckoo Hashing
  46. [PDF] Hopscotch Hashing - People | MIT CSAIL
  47. [PDF] Lecture 26 — Hash Tables - CMU School of Computer Science
  48. Internals of sets and dicts | Fluent Python, the lizard book
User Avatar
No comments yet.