Developer tools · Capacity
Bloom filter calculator.
Bits, bytes and hash functions for a target false positive rate, or the rate you get from a fixed memory budget.
Inputs
Filter size
Enter the values.
How big should a Bloom filter be?
For n items and a target false positive probability p, the bit array needs m = -n ln(p) / (ln 2)^2 bits, and the number of hash functions that minimises false positives is k = (m / n) ln 2, rounded to a whole number. Size grows with the number of items, not with their length: a 1% filter needs about 9.6 bits per item whatever the items are.
Worked example. 1,000,000 items at 1% need 9,585,059 bits (1.14 MiB), 9.59 bits per item, with k = 7. Giving the same items a fixed 1,250,000 bytes (10,000,000 bits) gives k = 7 and a false positive rate of about 0.82%.
The formulas assume independent, uniform hash functions, so real filters land slightly above the target. A Bloom filter never gives a false negative for items that were added, and cannot delete items unless you use a counting variant.
Frequently asked questions
What is the Bloom filter size formula?
m = -n ln(p) / (ln 2)^2 bits for n items and false positive probability p, with k = (m / n) ln 2 hash functions.
How many bits per element does a Bloom filter need?
About 9.6 bits per element for a 1% false positive rate with the optimal number of hash functions, regardless of element size.
How many hash functions should I use?
The optimal k is (m / n) ln 2 rounded to an integer: 7 for a 1% target. More hashes than that raise the false positive rate again.
Can a Bloom filter have false negatives?
No. A standard Bloom filter can return a false positive but never a false negative for items that were inserted.
Sources
Checked
Formulas are the standard ones from Bloom (1970) as presented on the linked Wikipedia article, which also states the 9.6 bits per element figure for 1%. Runs entirely in your browser. Nothing you type is sent or stored.
Scope
Planning estimates, not guarantees. Real systems add overhead this model leaves out and behave differently under load. Measure on your own data and load-test before committing to a design or a bill.