Bloom Filter False Positive Calculator

A Bloom filter is a space-efficient probabilistic structure that answers membership queries with a guarantee of no false negatives but a tunable false positive rate. You insert elements by hashing them k times and setting those k bits. To query, hash again and check all k bits. If any bit is 0, the element is definitely absent. If all bits are 1, the element is probably present.

The false positive probability for m bits, n inserted elements, and k hash functions is:

FPR = (1 - e^(-kn/m))^k

The optimal number of hash functions that minimizes FPR for given m and n is:

k_opt = (m/n) * ln(2) ≈ 0.693 * (m/n)

Plugging k_opt back in gives a minimum FPR of approximately (0.6185)^(m/n).

Choosing m. A common design target is 1% false positives. To hit that, you need roughly 9.6 bits per element (m/n ≈ 9.6, k_opt ≈ 7). For 0.1% FPR, you need about 14.4 bits per element.

Real use cases. Google’s Bigtable uses Bloom filters to avoid disk reads for non-existent rows. Web browsers use them to flag malicious URLs without downloading the full list. Database query planners use them to skip join partners that have no matches.

False negatives never occur. A Bloom filter can say “probably yes” (might be wrong) or “definitely no” (always right). Elements are never forgotten once inserted, and deletion requires a counting Bloom filter variant.