Double Hashing: k Positions from Two Hashes

In one line

Computing k independent hashes is slow. Kirsch and Mitzenmacher showed that positions g_i(x) = h1(x) + i·h2(x) mod m, from just two hash values, give the same asymptotic false-positive rate. Most production filters take h1 and h2 from one 128-bit MurmurHash3 call.

0/3 · 0%

Think of it like this

Choosing seats in a stadium row. Instead of rolling a die seven times, you roll twice: once for a starting seat and once for a step size, then take every step-th seat. Different people get different start-and-step pairs, so their seats spread out almost as well as seven independent rolls.

Key ideas

01
Formula: for i = 0..k−1, index_i = (h1(x) + i × h2(x)) mod m. Enhanced double hashing adds a small term (for example + i² or i³/6) to avoid rare patterns when h2 shares factors with m.
02
Why it's enough (Kirsch–Mitzenmacher, 2006): the false-positive probability of double hashing converges to that of fully independent hashes as m grows, so there's no practical accuracy loss.
03
One call, two values: a 128-bit MurmurHash3 gives two 64-bit halves, used as h1 and h2. Guava's BloomFilter does exactly this (strategy MURMUR128_MITZ_64).
04
Details that matter: make h2 odd or non-zero so the step never stays on the same bit; use 64-bit arithmetic and take the positive value before % m; handle negative numbers correctly in Java.
05
CPU win: one hash computation instead of k, which matters when k is 7–13 and you do millions of lookups per second.

Code & diagrams

DoubleHashing.javajava

// h1, h2 from one 128-bit MurmurHash3 (Guava's Hashing.murmur3_128())
long[] positions(byte[] key, int k, long m) {
    HashCode hc = Hashing.murmur3_128().hashBytes(key);
    byte[] b = hc.asBytes();
    long h1 = Longs.fromBytes(b[7], b[6], b[5], b[4], b[3], b[2], b[1], b[0]);
    long h2 = Longs.fromBytes(b[15], b[14], b[13], b[12], b[11], b[10], b[9], b[8]);
    long[] out = new long[k];
    long combined = h1;
    for (int i = 0; i < k; i++) {
        out[i] = (combined & Long.MAX_VALUE) % m;   // non-negative index
        combined += h2;                              // h1 + i*h2
    }
    return out;
}

Explain it without notes

Why can two hash values replace k independent hash functions?

Practice

Implement both k-independent-hashes (seeded Murmur k times) and double hashing, and compare FPR and throughput for 1M items at 1%.

Trade-offs

↔
Double hashing is nearly free accuracy-wise; enhanced variants guard against rare degenerate steps.

Done when you can

I can implement double hashing from a 128-bit hash and explain why it's sound.