Linear probing is a way to handle collisions in a hash table. When two items hash to the same position, linear probing simply steps forward through the table, one slot at a time, until it finds an empty spot. It’s one of the most straightforward collision resolution strategies in computer science, and thanks to how well it plays with modern hardware, it remains widely used in practice.
How Linear Probing Works
A hash table stores data by running each key through a hash function, which converts the key into an index in an array. The problem is that two different keys can produce the same index. This is called a collision, and every hash table needs a strategy for dealing with it.
Linear probing handles collisions by scanning forward from the collision point. If a key hashes to position 5 but that slot is already taken, it checks position 6, then 7, then 8, and so on until it finds an open slot. The increment between checks is typically 1. If the probe reaches the end of the array, it wraps around to the beginning and keeps going. This sequence of indices is called the probe sequence.
The same probe sequence applies to all three core operations:
- Insert: Hash the key, then walk forward until you find an empty slot. Place the item there.
- Find: Hash the key, then walk forward comparing keys at each slot. Stop when you find the key you’re looking for or hit an empty slot (meaning the key isn’t in the table).
- Delete: This one requires special handling, covered below.
The Deletion Problem and Tombstones
You can’t simply empty a slot when deleting from a linear probing table. Imagine three keys, A, B, and C, all hashed to the same index and stored in consecutive slots. If you delete B by clearing its slot, a later search for C would hit that empty gap and incorrectly conclude C doesn’t exist. The empty slot breaks the probe chain.
The standard solution is tombstone deletion. Instead of truly emptying the slot, you mark it with a special “deleted” flag. During a search, tombstones are treated as occupied, so the probe sequence keeps going past them. During an insert, tombstones are treated as empty, so new items can reclaim that space. This preserves the integrity of every probe chain while still allowing the table to reuse deleted slots.
Primary Clustering
Linear probing’s biggest weakness is a phenomenon called primary clustering. Because every collision sends items to the very next slot, occupied slots tend to form long, contiguous blocks. Once a cluster forms, any new key that hashes to any position within that cluster will land at the end of it, making it even longer. Clusters grow into bigger clusters, and bigger clusters attract even more collisions.
This feedback loop means that as the table fills up, probe sequences get progressively longer. A table that’s 90% full will frequently require scanning through dozens of slots for a single lookup, while a table at 50% capacity rarely needs more than a couple of probes.
Load Factor and Performance Thresholds
The load factor is the ratio of stored items to total table size. It’s the single most important number governing linear probing performance. The expected number of probes for a successful search is 0.5 × (1 + 1/(1 − α)), where α is the load factor. For an unsuccessful search or insertion, it’s 0.5 × (1 + 1/(1 − α)²).
To put those formulas in concrete terms: at a load factor of 0.5, a successful search takes about 1.5 probes on average and an unsuccessful search takes about 2.5. At 0.7, those numbers rise to roughly 2.2 and 6.1. At 0.9, you’re looking at 5.5 and 50.5. The curve isn’t gradual; it accelerates sharply once you pass about 70% capacity. That’s why most implementations trigger a resize (called rehashing) when the load factor hits 0.7. Rehashing allocates a larger array and re-inserts every item, which resets the clusters and restores fast lookups.
In the worst case, when the table is nearly full or the hash function produces many collisions, performance degrades to O(n), meaning every operation might need to scan the entire table. Keeping the load factor low prevents this from happening in practice.
Why Modern Hardware Favors Linear Probing
On paper, linear probing looks inferior to more sophisticated alternatives because of clustering. In practice, it often outperforms them. The reason is CPU cache behavior.
When your processor reads one memory address, it doesn’t fetch just that address. It pulls an entire block of nearby memory (a cache line) into fast on-chip storage. Linear probing exploits this perfectly: the next slot you need to check is right next to the one you just checked, so it’s almost certainly already in the cache. The CPU’s hardware prefetcher can even anticipate the access pattern and load upcoming slots before you ask for them.
With small slot sizes (8 to 16 bytes each), you can probe through 8 to 16 consecutive slots in the time it takes to fetch a single non-adjacent memory location. This means a linear probe sequence of five or six steps can be faster than a single probe that jumps to a random part of memory. For tables with reasonable load factors, this cache advantage more than compensates for the extra probes caused by clustering.
How It Compares to Other Strategies
Linear probing is one of several open addressing strategies. The alternatives modify the probe sequence to reduce clustering, but each comes with tradeoffs.
- Quadratic probing spaces out its checks using squares: if the initial hash is h, it checks h, h+1, h+4, h+9, h+16, and so on. This breaks up the long contiguous clusters that plague linear probing, since items that collide don’t pile up in adjacent slots. The downside is that the jumps quickly get large enough to leave the current cache line, losing the speed advantage of sequential memory access.
- Double hashing uses a second hash function to determine the step size. If a key hashes to position h and the second hash produces a step size of 3, the probe sequence is h, h+3, h+6, h+9, and so on. Because different keys produce different step sizes, the probe sequences are essentially unique per key. This eliminates clustering almost entirely, but every probe jumps to a potentially distant memory location, so cache performance is poor.
The key insight from Cornell University’s analysis: in linear probing, the interval between probes is always 1. In quadratic probing, the intervals follow a fixed pattern regardless of the key. In double hashing, the intervals depend on the key itself, making collisions between probe sequences rare. More randomness in the probe sequence means less clustering but worse cache locality. Choosing between them depends on whether your bottleneck is probe count or memory latency.
When Linear Probing Makes Sense
Linear probing works best when you can control the load factor and your entries are small enough that several fit in a single cache line. High-performance hash table libraries in C++ (like Google’s SwissTable family and Abseil’s flat_hash_map) use variations of open addressing with linear probing at their core, precisely because the cache benefits dominate real-world benchmarks.
It’s a poor fit when deletions are extremely frequent, since accumulated tombstones degrade performance in a way that’s similar to a high load factor. It also struggles when the hash function is weak, because a bad hash function feeds directly into larger clusters. Pairing linear probing with a high-quality hash function and a load factor cap around 0.7 keeps it fast, simple, and competitive with far more complex designs.