Why not always move one slot at a time?

That is linear probing, a different method with different clustering and locality characteristics.

Must the table size be prime?

No. Other sizes can work if the step rule ensures the required coverage, such as an odd step with a power-of-two size.

Can lookup stop at a deleted slot?

Usually not under tombstone-based deletion, because the desired key may occur later in its probe sequence.

AI Glossary / Graphs and symbolic AI / Intermediate

Double hashing

Definition

Double hashing is an open-addressing method for resolving collisions in a hash table. One hash function selects a key's initial slot, and a second determines the step between later slots checked for that key. It stores entries inside the table itself, using a reproducible probe sequence to locate an available slot or an existing entry.

What it means

A hash function can send different keys to the same table position. The table therefore needs a rule for what to do when the first position is occupied. Double hashing lets different keys use different probing steps, reducing the tendency for all colliding keys to follow one identical path.
This is a data-structure technique. It does not mean hashing a password twice, applying two cryptographic security layers, or keeping a duplicate copy of a database. The second hash controls movement through table slots; it does not by itself provide confidentiality or collision-free storage.

How it works

For a table of size m, a common probe rule is position(i) = (h1(key) + i x h2(key)) modulo m, starting with i = 0. An insertion or lookup follows that sequence, comparing actual keys at occupied positions.
The step must be nonzero modulo m and relatively prime to m if the sequence is to visit every slot before repeating. For a prime-sized table, any step from 1 to m-1 has this coverage property. Search and insertion must use compatible rules. Deletion also needs care: a removed slot usually cannot be treated exactly like a slot that has never been used, because other keys may lie farther along the same probe path.

Three practical examples

A custom symbol table uses double hashing to store identifiers whose first hash values sometimes collide.
A search program experiments with an open-addressed table for recording previously encountered states, while still comparing keys to distinguish collisions.
A data-structures benchmark measures how probe counts change as a double-hashed table becomes more full.

Think of it this way

Think of numbered lockers arranged in a circle. A key tells you both where to start and how many lockers to skip each time. Different keys can follow different routes. The analogy is limited because correct lookup depends on exact key comparison and slot-state rules, and a badly chosen skip can trap the search in only part of the circle.

Worked example

Use a table with seven slots numbered 0 through 6. Let h1(k) = k modulo 7 and h2(k) = 1 + (k modulo 6). For key 10, the starting position is 3 and the step is 5. Its probes are 3,1,6,4,2,0,5 before returning to 3.
For key 17, the starting position is also 3, but the step is 6. Its probes begin 3,2,1,0,6,5,4. If key 10 already occupies slot 3 and slot 2 is empty, key 17 is inserted at slot 2. The initial collision does not force the same later path.
Contrast this with a table of size eight and step two. Starting at zero visits 0,2,4,6, then zero again. The four odd-numbered slots are never checked, even if empty. Since two and eight share a factor, the step fails the full-coverage condition. These small arithmetic functions illustrate mechanics; they are not a recommendation for production hash quality.

Illustrative case study

At fictional Pine Index, developers delete an entry by marking its slot never used. A later lookup stops at that slot and incorrectly reports another key missing, although the key was displaced farther along its probe sequence. The team introduces distinct deleted-slot handling and tests insertion, lookup, and deletion together.
This fictional case illustrates a correctness risk specific to open addressing. It does not claim that double hashing caused a real outage or that one deletion strategy is universally best for every table design.

Common misconceptions and mistakes

Two hash functions do not eliminate collisions. Keys can share a starting point, a step, or even the whole probe sequence. The table still needs key comparison and a termination condition.
A step being nonzero is not sufficient for arbitrary table sizes; the relative-primality condition matters. Nor does good coverage guarantee short searches. As the table fills, finding empty slots can require many probes. Resizing requires reinserting entries under the new table size and probe rules, rather than merely copying them to the same indices. Finally, expected fast operations under suitable assumptions should not be described as a guaranteed constant-time bound for every possible key set.

Business use

Businesses usually encounter this technique inside infrastructure rather than as a product feature. Teams implementing custom tables should measure load factor, successful and unsuccessful lookup costs, and deletion behavior using representative workloads. Use well-tested implementations where appropriate. If stored keys influence important records, preserve full identity checks rather than treating a hash value as proof of equality. Benchmark memory use and cache behavior alongside arithmetic probe counts before choosing a collision-resolution method.

Check your understanding

A size-ten table uses step four from slot one. Will it visit every slot?

Answer: No. It cycles through 1,5,9,3,7 and back to 1. The common factor of four and ten limits the sequence to five slots.

Related terms

Linear probing
Quadratic probing
Hash table
open addressing
hash collision
load factor
tombstone
rehashing

Learn next

Trace insertion and lookup for three keys sharing an initial position but using different steps in a seven-slot table. Mark one occupied slot deleted, then show why continuing past it preserves access to later entries.

Sources

Virginia Tech, original hashing tutorial, Double Hashing: https://research.cs.vt.edu/AVresearch/hashing/double.php Cornell University, original hash-table lecture: https://www.cs.cornell.edu/courses/cs2112/2020fa/lectures/lecture.html?id=hashtables

Previous: Double delta feature Next: Double machine learning