The formula everybody sizes filters with

The formula is

$$\varepsilon = \left(1 - e^{-kn/m}\right)^k$$

and it is on every page that explains Bloom filters, in every library’s documentation, and behind every sizing calculator. It is the number people build systems against. This site’s habit is to check a formula rather than quote it, and this one has two approximations buried in it that are worth separating, because exactly one of them matters and it is not the one that looks suspicious.

The two approximations #

The first is the exponential. Inserting $n$ keys with $k$ hashes writes $kn$ bits, and the chance a given bit escapes all of them is $(1 - 1/m)^{kn}$. The formula replaces that with $e^{-kn/m}$. The replacement is a limit — $(1-1/m)^m \to e^{-1}$ as $m$ grows — so it is an approximation that improves with $m$ and is worst for small tables.

The second is the independence. The formula treats the $k$ bits a query checks as $k$ independent Bernoulli trials, each set with probability $f$. They are not independent: they are drawn from one shared table whose total number of set bits is itself a random variable, and two of a query’s own $k$ hashes can land on the same bit. Both effects push the true rate away from $f^k$.

The natural guess is that the exponential is the harmless one and the independence is the dangerous one. The measurement says the opposite of the natural guess in both cases, and the two answers are separate.

The exponential is negligible, and it is measurable anyway #

At any $m$ worth building, the two expressions for the fill are indistinguishable. At $m = 4{,}096$ with $k = 4$ and $n = 700$, the exact expectation is 2,028.51 bits set and the exponential says 2,028.34 — a difference of 0.17 bits out of two thousand, which no single filter could reveal because a single filter’s count varies by several bits from seed to seed.

So the honest test has to go where the gap is largest, which is small $m$, and it has to average. At $m = 64$, $k = 4$, $n = 16$, over three thousand builds:

The measurement lands on the exact expression to three decimal places and is 4.1 standard errors away from the exponential one. So the exact expression is right, the approximation is wrong by a measurable amount, and the amount is 0.19 bits out of 64 — about 0.3%, at the size chosen to make it as large as possible.

The first version of this test compared one filter against both expressions and asked which was nearer. That test was worthless and passed: a single build’s bit count varies by several bits, so which expression it lands nearer to is decided by noise, and a broken formula would have passed half the time. Requiring the two predictions to be separated by several standard errors before asking which is nearer is what turns it into a test. It is the same discipline as choosing a tolerance between the noise floor and the smallest real failure, applied to a comparison rather than to a threshold.

The practical conclusion is the boring one: use the exponential, it is fine, and the reason it is fine is now a number rather than a feeling.

The independence is fine too, when the keys are random #

The second approximation is the one with a real mechanism behind it and it also survives, on random keys. The check that isolates it is to compare the measured rate not against the formula but against $(X/m)^k$, where $X$ is the number of bits the filter actually has set. That removes the fill question entirely and leaves only the independence question.

Under 3% throughout, and the departures at the bottom of the table are within the counting error of a measurement that returned only a few hundred positives. The $k$ probes are dependent and the dependence does not show up at these sizes.

That is a real result and it is also the point at which a reader should ask what “random keys” is doing in the heading, because it is doing all the work.

There is one more reason to trust the independence here rather than merely to observe it, and it is a counting argument that costs nothing. The dependence between a query’s $k$ probes has two sources. The first is that two of the query’s own hashes can collide with each other, which happens with probability about $\binom{k}{2}/m$ — at $k=4$ and $m = 40{,}000$ that is $1.5 \times 10^{-4}$, far below anything measured here. The second is that the fill $X$ is a random variable, so the true rate is $E[(X/m)^k]$ rather than $(E[X]/m)^k$, and Jensen’s inequality says the first is the larger. The gap is governed by the variance of $X$, which for $m$ in the tens of thousands is a few tenths of a per cent of $m$. Both corrections are small for the same reason: $m$ is large. Both would matter for a filter of a few hundred bits, and the essay’s measurements do not cover that case.

The keys are part of the experiment #

Fill the same filters with the integers 1, 2, 3, … instead of with random keys and everything above changes.

The measured rate is 30 to 36% above the formula at every size. Not a few per cent — a third.

Why, and why the direction is the surprise #

The hash is multiply-add-shift: $h(x) = \lfloor((a x + b) \bmod 2^{32}) \cdot m / 2^{32}\rfloor$ for a random odd $a$. Feed it consecutive integers and the products $ax + b$ form an arithmetic progression modulo $2^{32}$, stepping by $a$ each time. Scaled into $[0, m)$, an arithmetic progression is a low-discrepancy sequence: it covers the range far more evenly than random points do.

So the writes collide less than random writes would. Fewer of the $kn$ bit-writes land on a bit that is already set, so more distinct bits end up set, so the filter is fuller than the analysis expects — 0.683 against 0.632 at four bits per element, eight per cent more bits set — and a fuller filter says yes more often.

The direction is the part worth dwelling on, because the intuition runs the other way. “The hash spreads this input better than random” sounds like good news, and for a hash table it is: the probe formula essay found exactly this phenomenon in the other direction, where an identity hash on consecutive keys gives 1.00 probes at every load factor, which is perfect. Same cause, opposite consequence, because a hash table wants its keys spread out and a Bloom filter wants its writes to overlap. Overlapping writes are what keeps the filter empty, and an empty filter is an accurate one.

That is a genuinely counter-intuitive result and it is why it is worth measuring rather than reasoning about. Nobody’s first guess is that making the hash more uniform makes the filter worse.

What the structured input does to the optimum #

If the input distribution moves the rate, it is worth asking whether it also moves the choice of parameters — because the whole use of the formula is to pick $k$, and a formula that is 30% wrong about the rate might be wrong about where the minimum is.

It is not. The minimum’s position depends on the fill as a function of $k$, and consecutive keys shift the fill up by a roughly constant multiplicative factor at every $k$ rather than changing its shape. So the curve is lifted rather than tilted, and $(m/n)\ln 2$ still lands on the bottom of it.

That distinction is worth generalising, because it applies to most engineering formulas: a formula can be wrong about a value and right about an argument that minimises it. The sizing formula’s job is the second, and it does it. Its error in the first is what has to be measured rather than assumed, and 30% is the kind of error that turns a 1% design target into a 1.3% delivered one — noticeable in a latency budget, invisible in a correctness test.

How far this could go, and where the measured case sits on that scale #

The 30% is one point, and a single point invites the question of whether it is near the edge of the effect or barely inside it. That has an answer, because the effect is bounded above by something computable: perfect equidistribution.

A hash that spread the $kn$ writes as evenly as the table allows would collide only when it had to, so it would set $\min(kn, m)$ bits and the fill would be $kn/m$ rather than $1 - e^{-kn/m}$. That is the extreme a too-good hash approaches, and putting the three fills side by side says how much of the interval the arithmetic progression actually crossed.

At eight bits per element the random fill is 0.3935, the perfect fill is 0.5, and consecutive keys measured 0.4147 — twenty per cent of the way from one to the other. At twelve bits it is 0.2835, 0.3333 and 0.2941, which is twenty-one per cent. At four bits, 0.6321, 1.0 and 0.6831, which is fourteen. So the progression is genuinely low-discrepancy and it is nothing like perfect: it recovers about a fifth of the available room, consistently, across the sweep.

The other end of that interval is worth stating plainly, because it is where the assumption stops being a convenience.

At four bits per element with four hashes, $kn = m$ exactly. A perfectly equidistributing hash would therefore set every bit in the table, and the filter would answer yes to every query — a false-positive rate of 100% against a textbook 15.97%. At eight bits per element the same hash gives a fill of 0.5 and a rate of 6.25% against 2.40%, and at twelve, 1.23% against 0.65%. Two and a half times, and nearly two.

That is the sentence the sizing formula’s derivation never says out loud. The randomness assumption is not an idealisation the analysis would be happy to see improved on. It is load-bearing in the direction nobody checks: the formula is an approximation that a worse hash pushes one way and a better hash pushes the other, and the better direction has no floor short of the structure ceasing to work. A hash table’s analysis is not like this — there, approaching perfect spreading approaches one probe, which is the best case rather than a catastrophe — and the asymmetry is the whole reason the same input on the same hash helps one structure and hurts the other.

It also sharpens what “use a good hash” should mean here. The requirement is not uniformity, which the multiply-add-shift family already has in the sense that matters for a table; it is uniformity that does not correlate with the input’s own structure, which is a property of the family-plus-input rather than of the function. That distinction is the subject of a hash is a family, not a function, and this is the measurement where the difference between the two readings costs a third of a design target.

What this means for benchmarking #

The general lesson is not about Bloom filters. It is this:

Benchmarking a hashed structure on consecutive integers does not measure the structure. It measures the interaction between the input’s arithmetic structure and the hash’s arithmetic structure, and that interaction can go either way by tens of per cent. Consecutive integers are the default benchmark input in every quick test anybody writes, precisely because they are the easiest thing to generate.

Three things follow that are cheap to do.

1. Say what the keys were. Every figure on this site that fills a hashed structure names its key distribution in the caption strip, for this reason. A rate quoted without its key distribution is not reproducible.
2. Use keys that look like the real ones. If the application hashes URLs, hash URLs. If it hashes sequential identifiers — and many do — then the consecutive case is the real case, and it is the random-key benchmark that is misleading. Neither input is more correct in general; the mismatch is what causes trouble.
3. Compare against the bits, not against the formula. The $(X/m)^k$ check separates “is the fill what the analysis predicted” from “are the probes independent”, and the first of those is the question the key distribution affects. Two questions, two measurements.

A fourth point is worth adding because it is the one that costs real money. The rate is used to size hardware — how many disk seeks, how many network round trips, how many cache lines — and it is used linearly: the extra work is the rate times the query volume. So a 30% error in the rate is a 30% error in the provisioned capacity of whatever sits behind the filter, which at scale is a line item. There is no compounding and no subtlety to it; the number is simply a third too small, and everything downstream is sized from it.

The same comparison at three settings #

The gap between the printed formula and the measurement is the finding, and a gap measured at one setting of three parameters is a gap nobody should size a filter from.

The third variation changes neither parameter, only the draw, which is the control the other two are read against. If the circles move under a new seed by about what sixty thousand queries can resolve, and the two lines do not move at all, then the distance between them is the finding rather than the noise — and that is the only way this page has of telling those apart.

Where the formula still earns its place #

None of this is an argument against the formula, and it would be an easy misreading. Across random keys the formula is accurate to a few per cent over a rate range of twenty-six-fold, and it is a closed form that can be evaluated before anything exists. That is exactly what a sizing formula is for.

What it is not is a measurement, and the difference shows up in a specific way: the formula’s error is systematic rather than random, so it does not average out and it does not shrink with more queries. On consecutive keys it is 30% high at every size — running the benchmark longer makes the wrong number more precise.

The right use is the one every engineering formula gets: use it to choose the parameters, then measure the built thing on the real keys, and treat a disagreement of more than a few per cent as information about the input rather than about the formula. In the case above the disagreement was 30% and the information was “these keys are not random”, which is a fact about the system worth knowing for reasons far beyond filter sizing.

The check that found it #

It is worth recording how the 30% came to light, because it was not by looking for it.

The filter’s own gate asserts that the measured rate agrees with $(X/m)^k$ — the estimate from the bits actually set. That assertion was written to catch a bad hash, and it did: an early version reduced into the table with the low bits of the product instead of the high ones, and the four hashes came out correlated enough to measure 12.96% against a predicted 2.72%. The fix was one line.

With the hash corrected the assertion passed on random keys and the consecutive-key case was only kept as a second branch of the figure, on the general principle that a generator’s options should all be exercised. It failed. The rate was 30% above the formula, the fill was 8% above its prediction, and neither number had anything to do with a defect.

So the same assertion caught a real bug and a real property of the input, one after the other, and it could not distinguish them — which is why the figure now asserts both directions: agreement on random keys, and disagreement on consecutive ones. A check that only knows how to demand agreement would have had to be weakened to accommodate the second case, and weakening it would have let the first case back through.

What is not claimed #

Two limits, both worth stating.

Sixty thousand queries is sixty thousand queries. At twelve bits per element the filter returned 372 positives, and the relative standard error on a count of 372 is about 5%. So the 2.8% departure in the independence table is inside the noise and the essay does not claim the probes are measurably dependent — it claims they are not measurably independent, which is a weaker and honest statement. The figure marks which points had enough positives to assert on.

One hash family, one key structure. The 30% is the size of the effect for multiply-add-shift on consecutive integers at these parameters. A different hash — a cryptographic one, say — would show a different number and quite possibly none at all, since a cryptographic hash’s whole job is to destroy the input’s arithmetic structure. The claim is that the input distribution can move the rate by tens of per cent, demonstrated once; it is not a claim about how much, for every hash.