Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path
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.
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 be on disk, a cache deciding whether an item is worth storing. A Bloom filter answers it in a fraction of the space by giving up a little precision in one direction only.
What it computes
A Bloom filter is an array of m bits plus k hash functions. Inserting an item sets the k bits its hashes point to; a lookup checks those same bits. Any unset bit means the item is definitely absent. All set means probably present, because other items may have set those bits. For n items and a target false-positive rate p, the calculator uses the standard optimal sizing:
m = ⌈ −n × ln(p) / (ln 2)² ⌉ bits in the array
k = round( (m / n) × ln 2 ) hash functions, at least 1
memory = m / 8 bytes
actual = (1 − e^(−k × n / m))^k false-positive rate with integer k
The comparison figure assumes a plain in-memory hash set costs about 32 bytes per item, and divides that by the filter’s size. The reference table shows bits per item, −ln(p) / (ln 2)², for six common targets.
A worked example
The defaults are one million items at a 1% false-positive rate.
ln(0.01) = −4.6052and(ln 2)² = 0.48045, som = 1,000,000 × 4.6052 / 0.48045 = 9,585,058.4, rounded up to 9,585,059 bits, shown as 9.6M.- Bits per item:
9.585, shown as 9.6. - Hash functions:
9.585 × 0.6931 = 6.64, rounded to k = 7. - Memory:
9,585,059 / 8 = 1,198,132 bytes, which is 1.1 MB in the 1,024-based units the tool uses. - Actual rate:
e^(−7 / 9.585) = 0.4818, so(1 − 0.4818)^7 = 0.01004, shown as 1.00%. - A hash set at 32 bytes per item would need 32,000,000 bytes, about 30.5 MB, so the filter is 27× smaller.
| Target p | Bits per item | k | Memory for 1M items |
|---|---|---|---|
| 10% | 4.79 | 3 | 585 KB |
| 1% | 9.59 | 7 | 1.1 MB |
| 0.1% | 14.38 | 10 | 1.7 MB |
| 0.01% | 19.17 | 13 | 2.3 MB |
Every tenfold cut in p adds the same 4.79 bits per item, whether you store a thousand keys or a billion.
Assumptions and limits
- Good, independent hashes. The formulas assume each hash spreads items uniformly and independently. In practice two base hashes combined as
h1 + i × h2are enough, but a weak hash raises the real error rate. - n is a ceiling, not an estimate. The rate is only met at or below
n. This filter reaches 2.8% at 1.25 million items and 15.7% at two million. - No deletes. A standard filter cannot remove items. Counting Bloom filters and cuckoo filters can, at a memory cost.
- The 32-byte baseline is a rough figure. A real hash set of long strings can cost far more per item, so the savings multiple is conservative for large keys.
- The slider spans 1,000 to 1 billion items. Larger sets follow the same arithmetic.
How to use the result
Choose p from the cost of a false positive, not from habit. A false positive in front of a disk read costs one wasted read, so 1% means about one unnecessary read per hundred lookups of absent keys. If that read is cheap, 1% to 5% is fine; if a false positive skips a real piece of work, for example a crawler wrongly treating a new URL as seen, go to 0.1% or lower. Then:
- Budget about 10 bits per item at 1% and add roughly 5 bits for every extra nine of accuracy.
- Size n for the end of the filter’s life, plus headroom, and rebuild before you cross it.
- Keep k near the optimum. Too few hashes raises the error rate; too many costs lookup time and also raises it.
When to use it, and when not
Use it when most lookups are for keys that are not there and checking for real is slow: a disk read, a network call, a remote cache. The filter only saves work on absent keys. A present key passes the filter and still pays the real lookup, so if 90% of your lookups hit, the filter can remove at most the other 10% of reads.
Skip it when the set is small. A thousand keys at 32 bytes each is 32,000 bytes, so an exact set costs almost nothing and never lies. Skip it too when you must list the members, delete them one at a time, or count them, since a standard filter can do none of these. And skip it when any false positive is unacceptable, such as a security allow-list: a “probably present” must never grant access.
Trade-offs and limits
The hash count is a trade between lookup cost and accuracy, and the optimum is shallow. At the defaults, 9,585,059 bits for one million items, the false-positive rate for each k is:
| k | False-positive rate | Bit reads per lookup |
|---|---|---|
| 1 | 9.91% | 1 |
| 3 | 1.94% | 3 |
| 5 | 1.11% | 5 |
| 7 | 1.00% | 7 |
| 10 | 1.30% | 10 |
| 14 | 2.48% | 14 |
Five hashes cost only 0.11 points of accuracy and save two reads per lookup. At the optimum, about half the bits are set at full load (51.8% here); a filter far from half full is mis-sized.
- Memory access is ignored. In a filter larger than the CPU cache, each of the
kbits is usually a separate cache miss. Blocked Bloom filters keep all of an item’s bits in one cache line, trading a slightly higher error rate for one memory access. - The formula is an approximation.
(1 − e^(−kn/m))^kslightly understates the true rate for small filters. At the sizes this tool targets the gap is negligible. - The error is per absent lookup. The expected number of wasted reads is absent lookups ×
p, so a 1% filter in front of 10,000 absent lookups a second still sends 100 a second to disk.
Common mistakes
- Sizing for today’s count. A filter built for one million items and filled to two million runs at 15.7%, not 1%. Size
nfor the day you plan to rebuild. - Hard-coding k. A library default of three hashes on a 9.6-bit-per-item array gives 1.94%, nearly double the target. Derive
kfromm / n. - Deleting by clearing bits. The cleared bits may belong to other items, which then read as absent. That is a false negative, the one error a Bloom filter promises never to make.
- Merging unlike filters. Two filters can be combined with a bitwise OR only if they share
m,kand the same hash functions. Otherwise the result is meaningless. - Hashing with weak or correlated functions. Taking low bits of a sequential ID, or seeding one weak hash
kways, clusters the bits and pushes the real rate above the formula.
Check yourself
Size a filter for 10 million items at 0.1%. How many bits, hashes and how much memory?
m = 10,000,000 × 6.9078 / 0.48045 = 143,775,876 bits, 14.38 per item. k = 14.38 × 0.6931 = 9.97, so 10 hashes. Memory is 143,775,876 / 8 = 17,971,985 bytes, about 17.1 MB.
A filter sized for one million items at 1% holds only 500,000. What is its false-positive rate?
With k = 7 and m = 9,585,059: (1 − e^(−7 × 500,000 / 9,585,059))^7 ≈ 0.025%. An under-filled filter beats its target by a wide margin; the danger is only on the other side.
Moving one million items from 1% to 0.1% costs how much memory, and what does it buy?
It adds 4.79 bits per item, 599,066 bytes or about 585 KB. At 10,000 absent lookups a second it cuts wasted reads from 100 a second to 10.
k bits; a lookup checks the same k. D hits an unset bit, so it is definitely absent. C lands only on bits that A and B set, so the filter says “maybe”: a false positive.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: about 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 whether an item is in a set. It can return false positives, saying an item is present when it is not, but never false negatives: if it says absent, the item is definitely absent. You trade a small, tunable error rate for a large reduction in memory compared with storing the items themselves, which makes it a cheap guard in front of slow lookups.
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)², rounded up to a whole bit, and the optimal number of hash functions is k = (m ÷ n) × ln 2, rounded to an integer. Memory is m ÷ 8 bytes. For one million items at 1%, that is 9,585,059 bits, 7 hash functions and about 1.1 MB. The tool also reports the false-positive rate you actually 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 4.8 bits per item for 10%, 9.6 for 1%, 14.4 for 0.1% and 19.2 for 0.01%. Each tenfold cut in the false-positive rate costs a fixed extra 4.79 bits per item, which is ln(10) divided by (ln 2) squared. That is why Bloom filters scale so gracefully: a billion keys at 1% fits in about 1.1 GB.
What happens if I insert more items than planned?
The false-positive rate climbs quickly, because the bit array fills up while the number of hash functions stays fixed. A filter sized for one million items at 1% reaches about 2.8% at 1.25 million items, 5.8% at 1.5 million and 15.7% at two million. Size for the largest count you expect to reach before rebuilding, or use a scalable Bloom filter that adds new layers as it grows.
Can you delete items from a Bloom filter?
Not from a standard one. Clearing an item’s bits could clear bits that other items share, which would create false negatives and break the filter’s one guarantee. A counting Bloom filter replaces each bit with a small counter so deletions are safe, at several times the memory. Cuckoo filters also support deletion and are often smaller at low error rates. If items expire in bulk, rebuilding the filter periodically is the simplest approach.
Where are Bloom filters used?
They guard expensive lookups. Databases and storage engines such as Cassandra, HBase and RocksDB use them to skip disk reads for keys that are definitely absent. Web crawlers use them to remember which URLs they have already seen. Caches and CDNs use them to avoid storing items requested only once. They also appear in spell-checkers, deduplication pipelines and network routers, anywhere a fast and mostly correct answer to a membership question saves real work.