Hong Life CalculatorsUnderstanding the Bloom filter calculator — concept and principle
A Bloom filter is a compact bit array that answers "have I seen this item?" with either "definitely not" or "probably yes". It never gives false negatives, but it can give false positives. This calculator sizes a filter: from the number of items you expect and the false positive rate you can accept, it returns the number of bits, the memory, the optimal number of hash functions and the bits per item.
How it is calculated
- Bits: m = −n · ln p ÷ (ln 2)², rounded up.
- Hash functions: k = (m ÷ n) · ln 2, rounded to the nearest whole number.
- Memory: m ÷ 8 ÷ 1,048,576 MiB.
- Bits per item: m ÷ n.
Here n is the expected item count and p the target false positive rate as a fraction (1% = 0.01).
The principle
Inserting an item sets k bits chosen by k hash functions. A query checks the same k bits; if any is 0 the item was never added. After n insertions, the chance that a given bit is still 0 is about e^(−kn/m), so the false positive rate is p ≈ (1 − e^(−kn/m))ᵏ. This is minimized when about half the bits are set, which happens at k = (m/n) ln 2; substituting gives p = (1/2)ᵏ and the sizing formula above. Each tenfold reduction in p costs about 4.8 extra bits per item.
Worked example
- Inputs: n = 1,000,000 items, p = 1% = 0.01.
- m = −1,000,000 × ln 0.01 ÷ (ln 2)² = 1,000,000 × 4.6052 ÷ 0.48045 ≈ 9,585,058.4, rounded up to 9,585,059 bits.
- Memory: 9,585,059 ÷ 8 ÷ 1,048,576 ≈ 1.142628074 MiB.
- k = 9.585059 × 0.6931 ≈ 6.64, rounded to 7 hash functions.
- Bits per item: 9.585059.
| Expected items n | Bits needed m |
|---|---|
| 250,000 | 2,396,265 |
| 500,000 | 4,792,530 |
| 750,000 | 7,188,794 |
| 1e+06 | 9,585,059 |
| 1.25e+06 | 11,981,323 |
| 1.5e+06 | 14,377,588 |
| 2e+06 | 19,170,117 |
How to read the result
About 9.6 bits per item gives 1%, 14.4 bits gives 0.1% and 19.2 bits gives 0.01%. If you insert more items than planned, the false positive rate rises quickly, so size for your peak count. Databases and storage engines use Bloom filters to skip disk reads for keys that are certainly absent; at 1%, about one read in a hundred misses is wasted.
Common mistakes
- Entering the rate as 0.01 when the field expects a percentage; 1 means 1%.
- Expecting to delete items; a standard Bloom filter cannot remove entries without risking false negatives (counting Bloom filters can).
- Using k independent slow hashes; two good hashes combined as h₁ + i·h₂ are usually enough.
Frequently asked questions
Can a Bloom filter say an item is present when it is not?
Yes, that is the false positive. It can never say an item is absent when it was added.
Does item size affect the memory?
No. Only the bits per item matter, so a filter for long URLs is the same size as one for short IDs.
Why round k to a whole number?
You cannot use a fraction of a hash function, and the error rate is flat near the optimum, so rounding costs very little.
Sources: B. H. Bloom, "Space/time trade-offs in hash coding with allowable errors", Communications of the ACM 13(7), 1970 · A. Broder, M. Mitzenmacher, "Network applications of Bloom filters: a survey", Internet Mathematics 1(4), 2004 · A. Kirsch, M. Mitzenmacher, "Less hashing, same performance: building a better Bloom filter", ESA 2006