Symptom
Every request to your service checks whether a user ID exists before doing anything else. The check hits the database. Ninety-eight percent of the time the answer is no, because most of the traffic is bots probing for accounts that were never created.
So you cache the negative results. Now you are caching a hundred million non-existent IDs, and the cache is larger than the data it protects.
The general shape: you need a membership test, the set is enormous, the answer is usually no, and confirming no is exactly as expensive as confirming yes. A hash set solves it at the cost of storing every element — 100 million 16-byte IDs is 1.6 GB before overhead, and Python or Java object headers can triple that.
The observation that breaks the deadlock: you do not need to store the elements. You need to answer a question about them, and you are willing to be wrong in one direction.
Statement
A Bloom filter is $m$ bits, initially zero, and $k$ independent hash functions. To insert $x$, set the bits at positions $h_1(x), \dots, h_k(x)$. To query $x$, check whether all $k$ of those bits are set.
No false negatives. If $x$ was inserted, every one of its bits is set, so the query returns yes. Always.
False positives at a known rate. With $n$ elements in $m$ bits and $k$ hashes, the probability that a query for an absent element returns yes is
$$p \approx \left(1 - e^{-kn/m}\right)^k$$
Minimizing $p$ over $k$ gives $k^* = \frac{m}{n} \ln 2 \approx 0.693,\frac{m}{n}$, at which the filter is exactly half full of ones and $p = 2^{-k^*} = (0.6185)^{m/n}$. Inverting, achieving false-positive rate $p$ requires
$$\frac{m}{n} = -\frac{\log_2 p}{\ln 2} \approx -1.44 \log_2 p$$bits per element, independent of the size of the elements. The information-theoretic lower bound for any such structure is $\log_2(1/p)$ bits per element, so a Bloom filter is within a factor of $\ln 2 \approx 1.44$ of optimal.
The last sentence is the one worth holding: the space cost depends only on the error rate you accept, never on how large the elements are. A filter over 100-byte URLs and a filter over 4-byte integers cost the same per element.
Argument
Deriving the false-positive rate. One insertion sets $k$ bits. After inserting $n$ elements, a given bit was left alone by each of the $kn$ settings with probability $(1 - 1/m)$ each, so
$$\Pr[\text{bit still } 0] = \left(1 - \frac{1}{m}\right)^{kn} \approx e^{-kn/m}$$A false positive needs all $k$ queried bits to be set, and treating them as independent — which is slightly wrong and standard, and the correction is negligible for realistic $m$ — gives $(1 - e^{-kn/m})^k$.
Why the optimum is a half-full filter. Differentiating and solving gives $k^* = (m/n)\ln 2$, at which $e^{-k^*n/m} = 1/2$. Exactly half the bits are ones. This is the intuition: too few hashes and each element leaves too small a fingerprint to distinguish it; too many and the filter saturates so everything looks present. The balance point is maximum entropy per bit, which is where a bit array carries the most information.
Concrete sizing, computed rather than quoted. For $n = 10^6$ elements:
| Target $p$ | bits/elt | $k^*$ | total size |
|---|---|---|---|
| 10% | 4.79 | 3 | 0.60 MB |
| 1% | 9.59 | 7 | 1.20 MB |
| 0.1% | 14.38 | 10 | 1.80 MB |
| 0.01% | 19.17 | 13 | 2.40 MB |
Compare: a hash set of a million 16-byte IDs holds at least 16 MB of keys, and in practice 40 to 100 MB once pointers, load factor, and object overhead are counted. The 1% filter is roughly 13× smaller than the raw keys alone and one to two orders of magnitude smaller than a real hash set, and each additional factor of ten in accuracy costs a flat 4.79 bits per element. Accuracy is logarithmically cheap, which is why people generally over-provision it.
How the asymmetry is exploited. The structure is only useful when no is the common answer and no is cheap to act on. The pattern is: filter says no, skip the expensive lookup entirely; filter says yes, do the lookup, which either confirms or reveals the false positive. Correctness is never at risk because the authoritative store is still consulted on every yes. The filter is a cheap rejection stage, not a source of truth.
Expected cost with hit rate $h$ and false-positive rate $p$: a fraction $h + (1-h)p$ of queries reach the store. At $h = 0.02$ and $p = 0.01$, that is $0.02 + 0.98 \times 0.01 = 0.0298$, so 97% of the database lookups disappear. That is the calculation that justifies the structure, and it collapses if $h$ is large: at $h = 0.9$ the filter removes only about 9.9% of lookups and is probably not worth the memory.
Where it runs in production. Every LSM-tree storage engine — RocksDB, LevelDB, Cassandra, HBase — puts a Bloom filter on each SSTable so a read can skip files that cannot contain the key, which turns a read from $O(\text{levels})$ disk seeks into typically one. Chrome’s Safe Browsing shipped a filter of malicious URLs so the browser could check locally and only contact Google on a hit. Bitcoin’s BIP 37 used them for lightweight clients, and CDNs use them to decide whether an object is worth caching on first request rather than caching one-hit wonders.
Variants, each fixing one limitation. Counting Bloom filters replace bits with small counters to support deletion, at 3 to 4× the space. Cuckoo filters support deletion and beat Bloom’s space at $p < 3%$ while providing better cache locality, since a lookup touches two buckets rather than $k$ scattered bits. Blocked Bloom filters confine all $k$ bits of an element to one cache line, trading a little accuracy for a large speed gain. Quotient filters are mergeable and resizable. XOR filters and ribbon filters get within about 1.08 of the information-theoretic bound for static sets, which is where RocksDB’s newer filter formats went.
Forbids
Deleting from a standard Bloom filter. Clearing an element’s bits may clear bits shared with another element, creating a false negative and destroying the one guarantee that matters. You must use a counting or cuckoo variant.
Enumerating the contents. The filter answers membership and nothing else. There is no way to recover what was inserted.
Beating $\log_2(1/p)$ bits per element. That is an information-theoretic bound, and Bloom’s $1.44\times$ overhead is the price of its simplicity.
A useful filter that is over-full. Once $n$ exceeds the design point, $p$ rises fast. At twice the intended $n$ with the tuned $k$, the 1% filter degrades to 15.7%, and at three times to 43.6%. Filters must be sized for the maximum, not the expected, element count, and this is the most common production failure mode.
Does not forbid
It does not mean false positives cause incorrect results, and this is the misreading that scares people off the structure. In every standard use, a positive triggers an authoritative check. RocksDB does a real SSTable lookup on a filter hit; Chrome contacted the server on a hit. The filter changes performance, never correctness, and a false positive costs one wasted lookup.
It does not require knowing $n$ in advance. Scalable Bloom filters chain progressively larger filters with tightening error rates so the aggregate rate stays bounded, which handles an unbounded stream at some cost in query time.
It does not require $k$ independent hash functions. Kirsch and Mitzenmacher showed $h_i(x) = h_1(x) + i \cdot h_2(x) \bmod m$ is asymptotically as good as $k$ independent hashes. Every serious implementation uses this, computing one 128-bit hash and splitting it, so the cost is one hash regardless of $k$.
It does not forbid union. Two filters of identical $m$ and $k$ can be combined with bitwise OR to represent the union exactly. Intersection via AND is not exact and over-approximates, which is a real trap.
It does not mean cache locality is bad in practice. Naively, $k$ random bit probes are $k$ cache misses. Blocked Bloom filters confine them to one 64-byte line, so a lookup is one miss, and this is why the variant dominates in performance-sensitive engines.
Boundary
- Sized for a maximum. Exceeding the design $n$ degrades $p$ sharply.
- No deletion, no enumeration, no counting. Different structures for each: counting or cuckoo filters, and Count-Min sketch or HyperLogLog for frequency and cardinality.
- Hash quality matters. The analysis assumes uniform, independent hashing (T104). A weak hash inflates the error rate, and an adversary who can choose keys can drive it arbitrarily high unless the hash is keyed. This is a real attack against filters exposed to user input.
- The independence approximation. The standard formula slightly under-estimates $p$; Bose et al. give the exact expression, and the difference is irrelevant except at very small $m$.
- Useless when the answer is usually yes. The economics need a low hit rate.
The trade to carry: give up one direction of correctness, buy a structure whose size depends only on your error tolerance and not at all on your data. That is a strikingly good deal whenever a maybe can be resolved cheaply by someone else.