Bloom Filter False-Positive Rate

The engineering

A Bloom filter answers "have I seen this key?" in constant time and a handful of bits per element, at the cost of occasional false positives (never false negatives). Given the bit-array size m, the number of inserted keys n, and the hash count k, this card evaluates the standard false-positive approximation. Leave k blank and it uses the optimal count k = (m/n)·ln 2 rounded to an integer — the value that leaves the bit array roughly half full, which is where the filter is information-theoretically most efficient.

Rules of thumb: about 9.6 bits per element with k = 7 buys you a 1% false-positive rate; every additional ~4.8 bits per element cuts the rate by another factor of 10. Watch the fill fraction — if it drifts well past 50%, you've inserted more keys than the filter was sized for and the FPR climbs fast. Also remember p is per query: a service doing a million lookups a day at p = 10⁻³ still eats a thousand false hits daily.

The formula here is the classic approximation from Bloom's original analysis, which treats each bit as independently set. It is slightly optimistic for small m, but for any filter big enough to matter in practice the error is negligible.

Where this math comes from

Burton H. Bloom was working at Computer Usage Company in 1970 when he published "Space/Time Trade-offs in Hash Coding with Allowable Errors" in Communications of the ACM. His motivating example was gloriously mundane: a hyphenation program where 90% of words followed simple rules and only 10% needed a dictionary lookup from slow disk. By accepting a small, tunable error rate, his "method 2" could keep a compact in-core summary and skip most disk accesses — the first time a data structure deliberately traded correctness for space.

The structure sat quietly in databases and spell checkers for decades before the internet made it famous. Squid web caches used Bloom filters to summarize each other's contents in the 1990s, Broder and Mitzenmacher's 2004 survey catalogued an explosion of network applications, and Kirsch and Mitzenmacher showed in 2006 that two hash functions can simulate all k — the trick most production implementations (Chrome's Safe Browsing, Bigtable, Cassandra) use today.

1. 1970Burton H. BloomPublishes the filter and its false-positive analysis in CACM.
2. 1979Carter & WegmanUniversal hashing gives the independent hash functions the analysis assumes.
3. 2004Broder & MitzenmacherSurvey of network applications cements the filter as core internet infrastructure.
4. 2006Kirsch & MitzenmacherShow gᵢ(x) = h₁(x) + i·h₂(x) matches full k-hash performance — the standard implementation trick.
5. 2008Bose et al.Publish the exact (non-asymptotic) false-positive analysis, confirming the classic formula as a tight approximation.

See the full timeline of the math behind every calculator →

Runs entirely in your browser — nothing you enter leaves this page. Your recent runs are stored only on your device.