Deriving k Bloom Filter Probes from Two Hash Words

A Bloom filter sized for a 0.8% error rate uses seven probes per key. Computing seven independent cryptographic hashes of every key, on every lookup, costs more than the memory accesses the probes were supposed to dominate. The standard implementation instead computes two hash words and derives the remaining positions arithmetically. That substitution is not a heuristic: it preserves the asymptotic false-positive rate, and the proof of that fact also shows precisely which property of the derived sequence matters and which does not.

The construction

Given a key, compute two values $h_1$ and $h_2$ over the range $[0, m)$, then set

$$ g_i = (h_1 + i \cdot h_2) \bmod m, \qquad i = 0, 1, \dots, k-1 $$

All $k$ probes cost one hash evaluation plus $k$ multiply-add operations. The pattern is an arithmetic progression with a fixed stride, which is exactly what a Bloom filter needs: $k$ positions that are uniformly distributed and, as far as the error analysis is concerned, independent.

The claim to examine is the last word. Two positions in an arithmetic progression over a finite ring are not independent in any strict sense. If $h_2$ is even and $m$ is even, every $g_i$ shares the parity of $h_1$, so the probes occupy only half the array — a structural failure that no amount of hash quality fixes. If $\gcd(h_2, m) = d > 1$, the probes visit a coset of size $m/d$ and the effective array is smaller by that factor, which raises the error rate accordingly. For $m$ a power of two the condition is simply that $h_2$ be odd; for $m$ prime, any nonzero $h_2$ works.

What the bound actually requires

Kirsch and Mitzenmacher’s argument does not claim the $g_i$ are independent. It shows that the false-positive probability of the $k$-probe filter built from $h_1 + i h_2$ is, to leading order, the same as that of a filter using $k$ fully independent hash functions, when $h_1$ and $h_2$ are drawn independently and uniformly. The mechanism is that the pair $(h_1, h_2)$ determines the whole probe set, and conditioning on a probe set of size $k$ leaves the marginal distribution of each individual position uniform.

Two consequences follow for implementation. First, the derivation is safe for the aggregate error rate, which is the quantity the sizing formula uses; it is not safe for claims about any particular subset of positions. Second, the failure modes are arithmetic rather than statistical: a stride that shares a factor with $m$ shrinks the reachable set deterministically, and no distributional argument covers that.

There is a boundary case worth knowing. When $h_2 = 0$ the $k$ probes collapse onto the single position $h_1$. The filter degenerates to a one-probe structure with a $k$-times higher error rate and a $k$-times higher insertion density at that position. A uniform $h_2$ over $[0, m)$ produces zero with probability $1/m$, which is negligible for a large $m$ but not for a small one — a 64-bit filter sees it once in 64 keys. Forcing $h_2$ odd, or adding one when it is zero, costs a branch and removes the case entirely.

Enhanced double hashing and the cubic term

The plain progression has a subtler defect that appears at larger $k$. Consecutive differences are all equal to $h_2$, so the sequence is maximally regular: knowing two probes determines the rest. An adversary who can observe which positions a key probes — from timing, from a memory access pattern, or by controlling the key — can construct collisions that the independence assumption rules out.

Enhanced double hashing perturbs the stride as the sequence advances:

$$ g_i = \left(h_1 + i h_2 + \frac{i^3 - i}{6}\right) \bmod m $$

The added term is the sum $\sum_{j=1}^{i-1} j^2$ reduced, which makes the differences grow quadratically rather than staying constant. Dillinger and Manolios introduced it for explicit-state model checking, where the filter is probed billions of times and the regularity of the plain progression produced measurably worse behaviour at high $k$. The cost is one extra multiply and add per probe, or an incremental update that carries a running difference.

Whether the cubic term matters depends on $k$. At $k \leq 4$ the difference is negligible; at $k \geq 8$ it is worth the arithmetic. The practical rule is to use the plain progression for small filters where $k$ is small and the enhanced form when the sizing formula pushes $k$ into double digits.

Two hash words from one digest

The construction needs two values that are uniform and independent over $[0, m)$. A single 128-bit digest supplies both by splitting: the low and high halves, or two disjoint 64-bit fields. Splitting is cheap and, for a cryptographic digest, sound — the halves of a secure hash are independent to the extent the primitive is.

Splitting a non-cryptographic 64-bit hash is the mistake to avoid. Many fast hashes return a value whose low bits are correlated with its high bits, because the finalisation step is weaker than the avalanche property requires. Taking the low 32 bits as $h_1$ and the high 32 as $h_2$ then produces two values that are nearly a function of one another, and the probes cluster. The remedy is either a hash with a documented avalanche step or an explicit mixing of the digest before splitting, such as multiplying by an odd constant and xoring the halves.

def probes(digest: bytes, m: int, k: int):
    """Yield k positions from a 128-bit digest; m need not be prime."""
    h1 = int.from_bytes(digest[:8], 'little')
    h2 = int.from_bytes(digest[8:], 'little')
    h2 |= 1                      # odd: coprime with any power-of-two m
    x = h1 % m
    for i in range(k):
        yield x
        # enhanced double hashing: stride grows by i each step
        x = (x + h2 + i * i) % m

The incremental form computes the same sequence as the closed formula when the accumulated square sum is tracked correctly; the version above advances the stride by $i^2$ at step $i$, which is the standard incremental formulation. Both avoid recomputing $i^3$ per probe.

Cost accounting

The arithmetic saving is real but smaller than it looks. A 128-bit digest over a short key costs on the order of tens of nanoseconds for a cryptographic function and a few nanoseconds for a fast non-seeded one; the derived probes cost a handful of cycles each. The dominant cost remains the $k$ memory references, each of which is likely to miss cache. Reducing hash work from $k$ evaluations to one therefore helps mainly for long keys — paths, URLs, serialised records — where the hash itself is proportional to input length and would otherwise be paid $k$ times.

For short keys the trade shifts the other way: computing one digest and deriving seven positions is cheaper than seven independent fast hashes, but not by the factor the probe count suggests, because the derivation arithmetic is not free. The saving is largest when the hash cost is proportional to key length — long keys, where $k$ independent evaluations would each scan the input — and smallest when the hash is a single multiply-shift over eight bytes, where the derivation arithmetic is comparable to the hashing it replaces.

Serialisation and the trap of a different m

A filter built with $m$ a power of two and probed with the odd-stride rule is not portable to an implementation that chooses $m$ prime and takes the plain modulus. The positions differ, so a filter written by one and read by the other returns negatives for keys it holds. This is not a theoretical hazard: the structure has no self-describing header, and the two parameters $m$ and $k$ are the only things that must be agreed on. Any serialised filter should carry both explicitly.

The same applies to the choice between plain and enhanced double hashing. A reader using the plain formula against a filter written with the cubic term will test the wrong positions for every probe after the first. The on-disk or on-wire format must pin the probe derivation as firmly as it pins the hash function. The blocked layouts discussed in blocked and partitioned filters face the same requirement, with the added complication that the block size is a third parameter.