Bloom Filter Sizing
Enter how many items you expect and the false-positive rate you can tolerate, and get the optimal Bloom filter: bit-array size, memory footprint, number of hash functions, bits per item, and the actual FP rate you’ll hit. See why a Bloom filter needs only ~10 bits per item — no matter how many items — to answer membership at a fraction of a hash set’s memory.
| False-positive rate | Bits / item | Hash functions (k) |
|---|---|---|
| 10.00% | 4.79 | 3 |
| 5.00% | 6.24 | 4 |
| 1.00% | 9.59 | 7 |
| 0.100% | 14.38 | 10 |
| 0.010% | 19.17 | 13 |
| 1.0e-3% | 23.96 | 17 |
Every 10× drop in false-positive rate costs a fixed ~4.8 more bits per item, regardless of how many items you store. That’s why Bloom filters stay tiny even at billions of keys — m = −n · ln(p) / (ln 2)², k = (m ÷ n) · ln 2.
Membership without the memory
Sometimes you only need to answer one question — "have I seen this before?" — over a set far too large to keep in memory. A crawler with a billion seen URLs, a database checking whether a key might exist on disk, a cache deciding whether an item is worth storing. Keeping the actual items costs gigabytes. A Bloom filter answers the same question in a fraction of the space, by giving up a little precision.
The bargain: false positives, never false negatives
A Bloom filter is a bit array plus k hash functions. To insert an item you hash it k ways and set those k bits; to test membership you check whether all k bits are set. If any is unset the item is definitely absent. If all are set the item is probably present — but a collision of other items' bits could fool it. So it can say "yes" wrongly (a false positive) but never "no" wrongly. That one-sided error is the whole trick.
The sizing formulas
For n items and a target false-positive rate p, the optimal bit-array size is m = −n · ln(p) / (ln 2)² and the optimal hash count is k = (m ÷ n) · ln 2. The striking part: bits per item (m ÷ n) depends only on p, not on n. A 1% filter always costs ~9.6 bits per item whether you store a thousand keys or a billion.
Why it scales
Because each 10× cut in false-positive rate adds a flat ~4.8 bits per item, you can dial precision up cheaply, and total memory grows only linearly with the item count. That is why Bloom filters (and their cousins — counting, scalable and cuckoo filters) sit in front of the expensive lookups in Cassandra, RocksDB, HBase, CDNs and crawlers everywhere. Set n and p above and watch the memory stay small as the error rate — not the scale — moves the numbers.
How it works
- m = ⌈−n · ln(p) / (ln 2)²⌉ bits; memory = m ÷ 8 bytes.
- k = (m ÷ n) · ln 2 hash functions, rounded to an integer.
- Bits per item depends only on p — ~9.6 bits buys a 1% error rate.
- False positives are possible; false negatives never are.
Frequently asked questions
What is a Bloom filter?
A Bloom filter is a space-efficient probabilistic data structure that answers "is this item in the set?". It can return false positives (it may say an item is present when it is not) but never false negatives (if it says absent, it is definitely absent). You trade a small, tunable error rate for a huge reduction in memory versus storing the items themselves.
How do you size a Bloom filter?
For n expected items and a target false-positive rate p, the optimal bit-array size is m = ⌈−n · ln(p) / (ln 2)²⌉ bits, and the optimal number of hash functions is k = (m ÷ n) · ln 2, rounded to an integer. Memory is simply m ÷ 8 bytes. This tool computes all of these plus the actual FP rate you get once k is rounded.
How many bits per item does a Bloom filter need?
It depends only on the false-positive rate, not on the number of items: about 9.6 bits per item for a 1% rate, ~14.4 for 0.1%, ~19.2 for 0.01%. Each 10× reduction in false-positive rate costs a fixed ~4.8 additional bits per item, which is why Bloom filters scale so gracefully to billions of entries.
Where are Bloom filters used?
They guard expensive lookups: databases like Cassandra, HBase and RocksDB use them to skip disk reads for keys that are definitely absent; web crawlers use them to remember seen URLs; CDNs and caches use them to avoid caching one-hit items; and they appear in spell-checkers, ad-dedup and network routers.