How a Bloom filter works
A Bloom filter is a compact way to test set membership when you can tolerate occasional false positives but never false negatives. It is a bit array of size m, all zeros to start, plus k independent hash functions. To add an element you hash it k ways and set those k bits. To query one, you hash it the same k ways and check those bits: if any is zero the element is definitely not in the set; if all are one it is probably in the set. The "probably" is the false-positive rate — the chance that k bits set by other elements happen to collide with the query.
The two formulas
For n elements and a target false-positive rate p, the optimal array size and hash count are:
m = −n·ln(p) / (ln 2)² k = (m/n)·ln 2
Two facts fall out of this. First, the cost is about 1.44·log₂(1/p) bits per element — every tenfold reduction in false positives adds roughly 4.8 bits each. Second, the optimal k makes the finished array almost exactly half full of ones, which is the point of maximum information per bit.
Worked example
To hold one million elements at a 1% false-positive rate: m = −10⁶·ln(0.01) / (ln 2)² ≈ 9,585,059 bits, which is about 1.14 MiB, and k = round(9.585 × 0.693) = 7 hash functions. That is roughly 9.6 bits per element — striking, given that storing the elements themselves would cost far more.
Common configurations (n = 1 million)
| Target FPR | Bits/element | Hash functions | Size |
|---|---|---|---|
| 10% | 4.79 | 3 | ~0.57 MiB |
| 1% | 9.59 | 7 | ~1.14 MiB |
| 0.1% | 14.38 | 10 | ~1.71 MiB |
| 0.01% | 19.17 | 13 | ~2.29 MiB |
What Bloom filters cannot do
A standard Bloom filter cannot remove an element (clearing bits would risk false negatives) and cannot list its contents. If you need deletion, a counting Bloom filter replaces each bit with a small counter at several times the space. And in practice the k hashes are almost never k separate hash functions — double hashing derives all k from two base hashes, which is why one good hash primitive is enough.
Related tools: the hash generator covers the hash functions a Bloom filter is built on, and the data transfer time calculator helps when the filter is shipped across a network.