Bloom Filters: How to Remember Things You Cannot Afford to Store

Suppose you need to know whether a particular item is in a set. The obvious data structures — hash tables, balanced trees, sorted arrays — all store the items themselves and let you look them up exactly. They are fast and reliable, but they all need enough memory to hold every item.

What if the set has a billion items, each one a long URL or a complicated bytestring, and you cannot afford to store them all? More precisely: what if you only need to know whether the item is possibly in the set, and you can tolerate occasional false alarms? Then a remarkable probabilistic data structure called a Bloom filter, invented by Burton Bloom in 1970, lets you check set membership using just a few bits per item — with a tunable, well-understood error rate. This article is about how Bloom filters work, why their false-positive probability has a beautiful closed-form expression, and where they have ended up in the infrastructure of the modern web.

The basic design

A Bloom filter consists of two ingredients:

1. A bit array of size $m$, initialised to all zeros.
2. A set of $k$ independent hash functions $h_1, h_2, \dots, h_k$, each mapping an item to a position in $\{1, 2, \dots, m\}$.

To insert an item $x$ into the filter: compute $h_1(x), h_2(x), \dots, h_k(x)$, and set the bit at each of those positions to $1$.

To query whether an item $y$ is in the filter: compute the same $k$ hashes, and check the bits at those positions. If any of them is $0$, the item is definitely not in the set — because if it had been inserted, all $k$ positions would have been set. If all of them are $1$, the item might be in the set: it was either inserted, or it had the bad luck of hashing into positions all of which had been set by some other items. The first case is a true positive; the second is a false positive.

The picture shows what happens after two insertions. Inserting "apple" set bits $1$, $4$, $7$ (blue). Inserting "cherry" set bits $6$, $9$, $14$ (green). Now querying "banana" requires looking at its three hash positions, say $\{2, 4, 9\}$. Bit $4$ is set (from "apple"), bit $9$ is set (from "cherry"), but bit $2$ is zero — so the filter immediately knows "banana" was never inserted. A single zero bit anywhere in the query positions is a guaranteed “not in the set” answer.

If, on the other hand, we had queried for some unrelated word whose three hash positions all happened to land on bits already set by "apple" and "cherry", the filter would report “possibly in” — a false positive.

The false-positive probability

The most elegant feature of Bloom filters is that their false-positive probability has a beautiful closed-form expression that can be derived in a few lines.

Suppose the filter has $m$ bits, uses $k$ hash functions, and has had $n$ items inserted. Each insertion sets $k$ bits (with some probability of overlap with previously set bits). The probability that a particular bit is not set by a single hash function operation is $1 - 1/m$. After $kn$ such operations (one for each hash of each insertion), the probability that the bit is still zero is

$\left(1 - \frac{1}{m}\right)^{kn} \approx e^{-kn/m}.$

The probability that a particular bit is set is therefore approximately $1 - e^{-kn/m}$. When you query a new item with $k$ independent hash positions, all $k$ of them have to be set for the filter to report a positive. The probability of this is

$p \;\approx\; \left(1 - e^{-kn/m}\right)^k.$

This is the false-positive rate of the filter (assuming the queried item was not actually inserted). The number $m/n$ — bits per item — and the number of hash functions $k$ together determine $p$.

Optimising $k$

For fixed $m$ and $n$, the false-positive rate $p$ depends on $k$. Differentiating $\ln p$ with respect to $k$ and setting the derivative to zero gives

$k^* \;=\; \frac{m}{n}\,\ln 2 \;\approx\; 0.693 \cdot \frac{m}{n}.$

At this optimal $k$, the false-positive rate simplifies beautifully:

$p \;=\; (1/2)^{k^*} \;=\; (0.6185)^{m/n}.$

So if you use $10$ bits per item — a modest amount of memory — the optimal Bloom filter uses about $7$ hash functions and has a false-positive rate of about $1\%$. With $20$ bits per item, the false-positive rate drops to about $0.005\%$. The relationship is exponential: every additional $0.693$ bits per item halves the false-positive rate. This is one of the cleanest engineering tradeoff curves in computer science.

What Bloom filters cannot do

Bloom filters have some sharp limitations.

No false negatives. A Bloom filter never says “not in the set” when the item was actually inserted. False positives are the only error mode.

No deletions. You cannot simply “unset” the bits when removing an item, because those bits may also be storing the membership of other items. Removing an item by clearing its bits would create false negatives for other items. Counting Bloom filters — which replace each bit with a small counter — are a variant that supports deletion, at the cost of more memory per slot.

No exact membership listing. A Bloom filter cannot tell you what items are in the set; it can only test membership of items you propose. The data structure is a one-way representation of the set: easy to query, impossible to enumerate.

Fixed size. Standard Bloom filters have a fixed $m$ chosen in advance. If you insert too many items, the false-positive rate degrades. Scalable Bloom filters — a chain of fixed-size filters with increasing capacity — extend the basic structure to handle dynamic sizing.

Where they live

Bloom filters are everywhere in modern systems:

Storage and databases. Google’s Bigtable, Apache HBase, Cassandra, and many other distributed databases use Bloom filters at every storage layer to avoid expensive disk seeks. When a database receives a query for key $k$, it consults the Bloom filter for each underlying file; only files whose Bloom filter reports “possibly contains $k$” need to be opened. This eliminates the vast majority of unnecessary disk I/O.

Networking. Routers use Bloom filters to detect cycles in packet forwarding paths and to maintain compact summaries of routing tables. Web cache hierarchies use them to avoid forwarding requests to neighbouring caches that definitely don’t have the requested resource.

Cryptocurrency. Bitcoin SPV (Simplified Payment Verification) wallets use Bloom filters to subscribe to transactions of interest without revealing exactly which addresses they care about. The recipient sends a filter representing the addresses of interest; transactions matching the filter are forwarded, but full privacy is preserved within the Bloom filter’s false-positive noise.

Web security. Browsers use Bloom filters to check URLs against blacklists of phishing or malware sites, before consulting a slower authoritative source. The false-positive rate is acceptable because a positive triggers a more expensive secondary check.

Spell-checking and search. Spell-checkers use Bloom filters to test whether words are in a dictionary; the filter is much smaller than the dictionary itself. Search-engine systems use them to skip expensive index lookups on terms that definitely do not appear in particular shards.

A pure-math jewel in applied form

Bloom filters are a striking example of how a small amount of clever probabilistic thinking can produce a data structure with dramatic practical advantages. The mathematics — counting bits set, computing collision probabilities, optimising a closed-form expression in one variable — is elementary, but the consequences are far-reaching. A modest amount of memory ($10$ bits per item) buys a $1\%$ false-positive rate, and that is enough to eliminate disk seeks at industrial scale.

What Bloom’s 1970 paper contains is one of the cleanest engineering trade-off analyses in the history of computer science. The same idea has been refined, extended, and re-deployed in dozens of variants — counting Bloom filters, partitioned Bloom filters, blocked Bloom filters, cuckoo filters, quotient filters, and more — each tuned to a specific operational profile. But the foundation, the central trick of asking “is this bit set?” instead of “is this item present?”, has not changed. Storage that does not store everything; certainty about absences; tunable uncertainty about presences. A small clever idea, doing enormous practical work, every second of every day, on every large server in the world.

Frequently asked

Who invented Bloom filters and why?

Burton Howard Bloom invented them in 1970, while working at Computer Usage Company. His original problem was hyphenation: a typesetting system needed to decide whether each word in a document was an 'exception' to standard hyphenation rules. The exception dictionary was too large to keep in memory in its entirety, but most words were not exceptions, so a fast probabilistic 'definitely-not' test would let the rare exception cases be looked up in slower disk storage. Bloom's filter was the elegant solution, and it remained relatively obscure until the rise of the modern web made the same problem ubiquitous.

What is a 'false positive' in a Bloom filter?

A false positive is the case where the filter reports 'this item might be in the set' but in fact it is not. False positives happen when an item's hash positions all happen to be bits set by other items; from the filter's perspective, the item is indistinguishable from one that was inserted. The probability of false positives can be tuned: more memory and more hash functions reduce the rate. By design, however, Bloom filters never produce false negatives — if the filter says 'not in the set', the item is definitely not in the set. This asymmetry is what makes them so useful in caching: a false positive only costs you a slow lookup that turns out to be unnecessary.

What is the optimal number of hash functions?

For a Bloom filter with m bits of storage holding n items, the false positive probability is minimised when the number of hash functions is k = (m/n) · ln 2 ≈ 0.693 · m/n. At this optimal k, the expected false-positive rate is approximately (1/2)^k, which for typical filter sizes (m/n ≈ 10) gives k ≈ 7 and a false-positive rate around 1%. The math here is unusually clean: a careful calculation of the probability that all k hash positions of a random query collide with bits already set produces a closed-form expression that can be optimised in closed form.

Where are Bloom filters used in practice?

Almost everywhere a 'definitely-not-here' fast check would be useful. Google's Bigtable and Apache HBase use Bloom filters to avoid expensive disk seeks for keys that are not present. Web browsers use them in URL safe-browsing checks. The Bitcoin protocol uses them in SPV (simplified payment verification) wallets to test whether transactions concern a particular wallet without revealing exactly which addresses are being watched. Network routers use them to detect cycles. Spell-checkers use them to test whether words are in a dictionary. Modern variants — counting Bloom filters, scalable Bloom filters, cuckoo filters — extend the basic idea to handle deletions, dynamic sizing, and tighter false-positive bounds.

Continue reading

Blog

The Fast Fourier Transform: How a Clever Trick Made an Old Algorithm Run the World

A naive Fourier transform of N samples needs N² multiplications. In 1965 Cooley and Tukey halved the problem recursively and got N log N — and the modern era of digital signal processing began.

Read →Blog

Dynamic Programming: Solving Hard Problems by Remembering Easy Ones

Many problems repeat the same subproblems over and over. Storing each answer the first time you compute it can turn an exponential algorithm into a polynomial one — sometimes a stunning speedup.

Read →Blog

Principal Component Analysis: Finding the Best Few Dimensions in a Cloud of Data

High-dimensional data has hidden low-dimensional structure. PCA finds it: the few orthogonal directions along which the data varies most. From genomics to image compression, it is everywhere.

Read →