↩ back to Hash-Based

Double Hashing

This site's own Linear Probing page names this scheme and defers it — its "Where linear probing shows up" section calls out "double hashing's staggered probe sequence" as the standard textbook fix for the clustering that plain linear probing's fixed one-slot step produces, without ever building it. Double hashing is that fix: instead of always moving forward one slot on a collision, each key gets its own step size, computed from a second hash function. The probe sequence for a key becomes (h1(key) + j·h2(key)) % size for j = 0, 1, 2, … instead of linear probing's (h1(key) + j) % size — same one table, same no-eviction contract, just a per-key stride instead of a shared one.

That per-key stride buys real spread: two keys that collide at the same home slot no longer walk the identical path one step apart the way linear probing forces them to, so they stop merging into the same run. But it introduces a correctness requirement linear probing never had to worry about — h2(key) must never return 0 (a zero step never moves at all) and must be coprime with the table size (an even step against this site's power-of-two table sizes only ever reaches half the slots, or fewer). Both of this page's Pitfalls are real, checked failures of a plausible-looking h2 that skips one of those two guarantees — not a theoretical warning.

Try it

Put a key/value pair, get one back, or delete it. Reload sample loads the exact same three colliding keys as Linear Probing's own demo — ram, pig, cat — into an 8-slot table, and all three still hash to the same home, slot 6. But instead of linear probing's one-slot walk (6→7→0), each key's step here is 5 slots at a time: pig jumps straight to slot 3, and cat — which shares both ram's home and its step, since h2 depends only on the key — retraces pig's exact path and lands at slot 0 by way of slot 3.

The well-formed step checkbox controls which h2 the table uses. Checked (the default), h2 is forced odd via | 1, guaranteeing it's never zero and always coprime with this site's always-power-of-two table sizes. Unchecked, it's the raw second hash mod the table size — plausible-looking, and broken in two different ways. Uncheck it and click Run zero-step demo: it loads one key at its home slot, then tries to insert a second key whose raw h2 happens to be exactly 0 — the probe never leaves the first key's slot, walks it eight times, and reports "table full" on a table with seven empty slots. Click Run even-step demo: it loads four keys at four different homes, then tries to insert a fifth whose raw h2 is an even number — its probe only ever reaches the four slots that share its own home's parity, all four already taken, so it reports "table full" with the table only half full. Check the box and re-run either demo: both succeed within one extra probe.

Core operations

• hash1(key) — the same multiply-by-31 fold-and-reduce every other Hash-Based entry on this site uses. O(k) for a key of length k.
• hash2(key) — a second, independent fold: multiply-by-37 with a +7 offset, the same second hash function Cuckoo Hashing's own reference implementation uses, for the same reason its own page gives — a different multiplier keeps the two hashes from moving in lockstep on similar keys. O(k).
• step(key) — hash2(key) % size, forced odd with | 1. Since this site's table sizes are always a power of two (the same doubling-on-resize policy every Hash-Based entry shares), "odd" and "coprime with the table size" mean exactly the same thing here — forcing the low bit on is the entire fix, not a simplification of it.
• get(key) — walk hash1(key), hash1(key) + step, hash1(key) + 2·step, … (mod size), skipping tombstones, comparing keys. Stop and return the value on a match; stop and report "not found" at the first truly empty slot. O(1) average.
• put(key, value) — the same walk. A slot already holding the key: overwrite in place. A truly empty slot: place there, or at the first tombstone the walk already passed if one exists — the identical tombstone-reuse rule Linear Probing uses, for the identical reason. O(1) average; resizing (doubling past 0.75 load factor on live entries) amortizes to O(1) per put.
• delete(key) — find the slot via the same walk, mark it with a tombstone rather than clearing it to empty. Skipping this, exactly as on Linear Probing, strands every key further along the same probe run — that page's own Pitfalls section already proves it in detail, so this page's demo always tombstones and doesn't re-litigate it.

Reference implementation

class DoubleHashingHashTable {
  static TOMBSTONE = Symbol('tombstone');
  #size;
  #table;
  #count = 0;

  constructor(size = 8) {
    this.#size = size;
    this.#table = new Array(size).fill(null);
  }

  #hash1(key, size = this.#size) {
    let h = 0;
    for (const ch of String(key)) h = (h * 31 + ch.charCodeAt(0)) >>> 0;
    return h % size;
  }

  #hash2(key, size = this.#size) {
    let h = 0;
    for (const ch of String(key)) h = (h * 37 + ch.charCodeAt(0) + 7) >>> 0;
    return h % size;
  }

  #step(key, size, safe) {
    const raw = this.#hash2(key, size);
    return safe ? (raw | 1) : raw;
  }

  get(key, safe = true) {
    const size = this.#size;
    let i = this.#hash1(key, size);
    const step = this.#step(key, size, safe);
    for (let n = 0; n < size; n++) {
      const slot = this.#table[i];
      if (slot === null) return undefined;
      if (slot !== DoubleHashingHashTable.TOMBSTONE && slot.key === key) return slot.value;
      i = (i + step) % size;
    }
    return undefined;
  }

  put(key, value, safe = true) {
    const size = this.#size;
    let i = this.#hash1(key, size);
    const step = this.#step(key, size, safe);
    let firstTombstone = -1;
    for (let n = 0; n < size; n++) {
      const slot = this.#table[i];
      if (slot === null) {
        const target = firstTombstone !== -1 ? firstTombstone : i;
        this.#table[target] = { key, value };
        this.#count++;
        this.#maybeResize(safe);
        return;
      }
      if (slot === DoubleHashingHashTable.TOMBSTONE) {
        if (firstTombstone === -1) firstTombstone = i;
      } else if (slot.key === key) {
        slot.value = value;
        return;
      }
      i = (i + step) % size;
    }
    if (firstTombstone !== -1) {
      this.#table[firstTombstone] = { key, value };
      this.#count++;
      this.#maybeResize(safe);
      return;
    }
    throw new Error('table full');
  }

  delete(key, safe = true) {
    const size = this.#size;
    let i = this.#hash1(key, size);
    const step = this.#step(key, size, safe);
    for (let n = 0; n < size; n++) {
      const slot = this.#table[i];
      if (slot === null) return false;
      if (slot !== DoubleHashingHashTable.TOMBSTONE && slot.key === key) {
        this.#table[i] = DoubleHashingHashTable.TOMBSTONE;
        this.#count--;
        return true;
      }
      i = (i + step) % size;
    }
    return false;
  }

  #maybeResize(safe) {
    if (this.#count / this.#size <= 0.75) return;
    const old = this.#table.filter(s => s && s !== DoubleHashingHashTable.TOMBSTONE);
    this.#size *= 2;
    this.#table = new Array(this.#size).fill(null);
    this.#count = 0;
    for (const slot of old) this.put(slot.key, slot.value, safe);
  }
}

Verified against a plain-Map reference model over 5,000 randomized trials (150-400 interleaved put/get/delete calls each, 6-20 key pools, forcing repeated collisions and resizes), checking every get/delete result against the model after every call, plus a full final sweep — 0 mismatches, scratch script, not committed. That stress test is also what caught a real bug in an earlier draft of put: the tombstone-reuse branch after the main loop (reached when the whole table gets scanned with no truly empty slot found) was missing its own #maybeResize call, the same call the in-loop empty-slot branch above it makes. With enough tombstone-reuse inserts slipping through unresized in a row, the live count could climb straight past the 0.75 threshold to a genuinely saturated table with no resize ever having fired — a real, reproducible "table full" on a table that should have doubled several inserts earlier, caught only because the stress harness's oracle disagreed with the table on a later put, not because anything looked wrong up front.

Pitfalls

A step of zero degenerates the whole probe sequence to one slot. Load a key whose home is slot 5 into an empty 8-slot table — it lands there directly. Now insert a second key whose raw hash2 happens to be exactly 0 mod 8: its probe sequence is 5, 5+0, 5+0+0, … — the same index, slot 5, on every single attempt, because adding zero never moves anywhere. The loop still runs all 8 iterations (nothing tells it to stop early), checking slot 5 eight times, and finding it occupied every time — it reports "table full" with exactly one live entry and seven genuinely empty slots. Confirmed against the exact shipped put: with safe forced to false, the second insert throws every time this pair runs; forcing safe back to true turns the broken step into 0 | 1 = 1, and the same insert succeeds at the very next slot instead.

An even step only ever reaches half the table, silently. Four keys, chosen so their own homes are slots 1, 3, 5, and 7, load into an empty 8-slot table with no collisions at all. A fifth key whose home is slot 7 too and whose raw hash2 is 2 — even — collides with the key already at slot 7 and starts probing: 7, 7+2=1, 1+2=3, 3+2=5, then wraps back to 7 and repeats the identical four slots a second time to fill out the loop's 8 iterations. Every one of those four slots is occupied by one of the first four keys — but slots 0, 2, 4, and 6 are completely empty, and an even step against an 8-slot table can never reach them, because gcd(2, 8) = 2 splits the table into two disjoint 4-slot cycles by parity. The table is 50% full and the insert still throws "table full." Confirmed against the exact shipped put the same way: safe = false fails this sequence every time; safe = true turns the broken step (2) into 2 | 1 = 3 — coprime with 8 — and the fifth key lands two probes later, at slot 2, one of the four "unreachable" slots the broken step could never have found.

Where double hashing shows up

• It closes the forward reference this category's own newest page left open. Linear Probing's "Where linear probing shows up" section named this scheme as the textbook alternative to Robin Hood hashing's swap rule for fixing primary clustering, without building it — this page is that build.
• It still clusters, just differently. Plain linear probing suffers primary clustering — long runs of occupied slots merging into longer ones, because every key takes the same one-slot step. Double hashing avoids that, but this page's own sample table shows the failure mode it trades in for it: ram, pig, and cat don't just share a home slot, they share the exact same step too (h2 depends only on the key, so same key, same step, always), so pig and cat retrace each other's entire probe path one link apart instead of spreading across the table — textbooks call this secondary clustering, and it's a real, checkable property of this exact reference implementation, not a hypothetical edge case.
• The tradeoff against Robin Hood Hashing isn't close. Robin Hood's swap rule fixes the same clustering problem while keeping linear probing's sequential, cache-friendly scan — double hashing's per-key jumps scatter across the array instead. And Robin Hood never needs a second hash function to be coprime with the table size in the first place, so it structurally cannot have either of this page's two Pitfalls. See Complexity below for why that makes this page's place in Choosing a Hash Table Collision Strategy the same "set aside, not a real branch" one Linear Probing already occupies.

Complexity

Time: get, put, and delete are all O(1) average, the same headline every Hash-Based entry on this site shares. Worst case is O(n), same as linear probing and chaining — but a badly-formed step function doesn't just degrade double hashing's worst case the way an unlucky key does for those two, it can make slots that are provably empty unreachable for a specific key no matter how few entries the table holds, exactly as both Pitfalls above measure directly. Space: O(n), one table, the same 0.75-live-load-factor-then-double policy as the site's other single-table entries.

There is no scenario, for the exact put/get/delete contract this page and Robin Hood Hashing both implement, where double hashing is the safer choice. Robin Hood hashing's own Pitfalls section already showed its swap rule never raises the total probe-step cost across a batch of inserts, only redistributes it — the same argument Linear Probing's own Complexity section uses to set that page aside from Choosing a Hash Table Collision Strategy's three-way comparison. Double hashing adds a second argument on top of that one: it introduces an entirely new correctness-critical parameter — the step function — that has to satisfy a global property (coprime with the table size) no individual test case makes obvious, and gets it wrong in the exact two ways this page's Pitfalls demonstrate. Robin Hood hashing needs no such parameter at all. Double hashing's real value is in being the standard textbook answer to "how do you reduce clustering without adding a second table," not in being a better choice than Robin Hood hashing for this site's own put/get/delete contract.