Why can different starting positions still create one cluster?

A key starting inside an existing occupied run must continue through it, potentially extending the run.

Why does search continue past a deleted marker?

The target may have been displaced beyond that position before the deletion.

Does linear probing require checking every slot?

Not for every operation, but long runs or a nearly full table can require many probes. A correct implementation must handle the full-table case.

AI Glossary / Graphs and symbolic AI / Intermediate

Linear probing

Definition

Linear probing is a collision-resolution method for a hash table stored in an array. When a key's initial position is occupied by a different key, the algorithm checks subsequent positions in order, wrapping around at the end, until it finds the key or an appropriate available position.

What it means

A hash function provides a starting address, not a promise that every key has its own address. Two keys can collide by producing the same starting position. Linear probing keeps entries in the table array and resolves the collision by looking farther along that array.
The positions examined form a probe sequence. Search must follow the same sequence used by insertion. In particular, an item stored several positions beyond its starting address must remain reachable after other items are deleted. This makes the distinction between an ordinary empty slot and a deleted slot important.

How it works

For an array with m positions, a simple probe sequence is h(k), h(k) + 1, h(k) + 2, and so on, with addresses taken modulo m. Insertion checks occupied entries and continues until placement is possible. Lookup checks for the target key along the corresponding sequence.
An empty slot can establish that the key is absent when the table's invariants are maintained. A deleted-marker slot usually cannot: search continues past it. Implementations must also detect a full traversal rather than loop forever. Growing occupied runs, called primary clustering, can increase the number of positions examined.

Three practical examples

A compact in-memory lookup table can store identifiers and associated values using an array rather than separate collision chains.
A programming lesson can demonstrate why two different keys sharing one hash address are not an error in themselves.
A storage benchmark can compare how lookup and insertion behave as occupancy and deletion history change.

Think of it this way

Think of numbered parking spaces where a driver starts at an assigned space and proceeds to the next available one. Finding the car later requires following the same route. The analogy is limited because a hash table compares exact keys, records deletion state, and follows explicit rules for absence and full capacity.

Worked example

Use an invented seven-slot table, numbered 0 through 6, with h(k) = k mod 7. Insert keys 10, 17, 24, and 11 in that order, treating each key as distinct.
Key 10 starts at 3 and occupies slot 3. Key 17 also starts at 3, finds 10 there, and occupies slot 4. Key 24 starts at 3, passes occupied slots 3 and 4, and occupies slot 5. Key 11 starts at 4, passes slots 4 and 5, and occupies slot 6. The occupied run is now slots 3 through 6, even though not every key had the same starting address.
Looking up 24 examines slots 3, 4, and 5: three probes. Looking up absent key 31 starts at 3, passes 3, 4, 5, and 6, wraps to empty slot 0, and stops: five probes. These counts include both occupied comparisons and the final empty-slot check.
Now delete 17 from slot 4. If that slot is incorrectly treated as an ordinary empty slot, a later search for 24 stops there and falsely reports absence. A deleted marker allows the search to continue to slot 5.
An insertion may reuse the deleted position, but a dictionary implementation updating existing keys must still establish whether that key already appears later in the probe sequence. Otherwise, inserting 24 again could create a duplicate entry instead of updating the existing one. This example explains correctness and clustering; it is not a timing benchmark.

Illustrative case study

In a fictional tool, Juniper Catalog stores short product identifiers in a small lookup table. Basic insertion tests pass, but a lookup fails after deleting an unrelated identifier. The missing item remains physically present later in the occupied run.
The team traces the probe sequence and discovers that deletion created a premature stopping point. It adopts a consistent deletion strategy and checks lookup after deletions at the beginning, middle, and end of collision runs. This invented case shows why correct individual insertions do not establish correct behavior across a sequence of table operations.

Common misconceptions and mistakes

Linear probing is not linear hashing. The former resolves collisions through a sequence of array positions; the latter is a dynamic-growth method based on scheduled bucket splits.
Do not assume every operation requires one probe merely because a hash function is used. Occupancy, clustering, key distribution, and deleted markers can all influence the work required. Also, clearing an entry is not always a valid deletion procedure. Some implementations use tombstones, while others repair the affected cluster. These strategies must preserve lookup behavior rather than merely make a cell appear unused.

Business use

The business relevance is usually indirect: hash tables support software components that need frequent exact-key lookups. Performance claims should be evaluated under realistic insertion, lookup, and deletion patterns, not only on a newly populated table with convenient keys.
Measure successful and unsuccessful lookups separately. The example shows that absence can require more probes than finding a nearby item. Include capacity growth and maintenance in the evaluation, and verify that dictionary operations preserve one logical value per key. For application teams, a mature library implementation is often the practical choice; understanding probing helps interpret performance and correctness issues.

Check your understanding

After deleting 17 in the example, why is stopping at slot 4 incorrect when searching for 24?

Answer: Key 24 was displaced from its starting address 3 to slot 5. Deletion must preserve the ability to search past slot 4, or a stored key becomes unreachable.

Related terms

Quadratic probing
Double hashing
Linear hashing
Hash table
collision resolution
open addressing
primary clustering
load factor
tombstone

Learn next

Add key 18 to a fresh copy of the example table and trace the wraparound placement. Then compare a deleted marker with a truly empty slot during an unsuccessful lookup. Finally, study how resizing or rebuilding a table can change probe sequences and remove obsolete deletion markers.

Sources

NIST Dictionary of Algorithms and Data Structures, linear probing, including the deletion caveat: https://xlinux.nist.gov/dads/HTML/linearprobng.html

Previous: Linear predictor function Next: Linear programming