Why Bloom filters exist

A data structure that answers "have I seen this?" with "definitely no" or "maybe" — and saves enormous amounts of work by being wrong on purpose.

The picture version

Five pictures for a reader who has never heard of a Bloom filter, following one question: is the word you just typed in the dictionary?

Why it exists

Type a word into any text box and a red squiggle appears under it before you’ve hit the next key. Behind that squiggle is a question asked once per word you type: is this string in the dictionary? The honest way to answer is to keep the dictionary and look. The problem is that “keep the dictionary” is exactly what you can’t afford when the check has to be instant and the dictionary lives somewhere slow — on disk, in another datacenter, behind an API. That’s the running example for this post: a membership check you have to answer without holding the set.

Burton Howard Bloom’s 1970 paper (Space/Time Trade-offs in Hash Coding with Allowable Errors, CACM 13(7)) works through almost exactly this shape of problem. Its running application is automatic hyphenation: most words can be hyphenated by simple rules, a minority need a dictionary lookup, and that lookup — a disk access, in 1970 — is what you’re trying to avoid paying.

His move was to notice an asymmetry. If the structure could quickly say “don’t bother, this is definitely not in the set,” and were allowed to occasionally say “maybe” when the truth is “no,” nothing breaks. A “maybe” just means you fall through to the slow path you were going to take anyway. A wrong “no” would be a correctness bug; a wrong “maybe” is a missed optimization. Being willing to be wrong in one direction only turns out to be a currency you can spend for enormous amounts of memory.

Why it matters now

Memory is cheaper than it was in 1970, but the gaps between RAM, local SSD, the network, and cold object storage are still orders of magnitude each. Anywhere there’s a steep cliff between two storage tiers, a Bloom filter wants to sit at the top of it. Three concrete places: LSM-tree storage engines (RocksDB, Cassandra, LevelDB, HBase) commonly attach a filter to each on-disk sorted file — an SSTable — so a read can skip files that definitely don’t hold the key; it’s configurable rather than always on (see lsm-trees). Google’s 2006 Bigtable paper describes exactly this refinement, motivated by cutting disk seeks for reads of rows that don’t exist.

And Bitcoin’s SPV wallets used them via BIP 37 to ask full nodes for transactions matching data derived from the wallet’s own keys and addresses, without sending that data in the clear.

That last one is also the cautionary tale. In practice the parameters wallets chose leaked substantially more than intended — published analysis of BIP 37 found that wallets holding only a small number of addresses risked exposing nearly all of them to the node they queried. Bloom filters leak sideways, and the leak is not visible in the false-positive formula.

The short answer

Bloom filter = bit array + k hash functions

Picture to keep: a long row of light switches, all off. Every word you add flips four switches determined by its spelling. To check a word, look at its four switches — if any is off, that word was definitely never added; if all four are on, someone was here, though maybe not the word you’re asking about. Like a row of switches, except you can never flip one back off: switches are shared between words, so turning one off would erase evidence of some other word too. That one restriction is where “no deletes” comes from.

To insert x, you hash it k different ways, take each hash mod the array length, and flip those k bits to 1. To query x, you hash it the same k ways and check those bits. If any is 0, x is definitely not in the set. If all are 1, x is probably in the set — or other insertions collectively flipped exactly those bits. There’s no remove (in the basic version), and no enumerate. You traded both for size.

How it works

Build it from the constraint, one failure at a time. The set is an English dictionary; the queries are words a person just typed.

Naive attempt: store the words. A hash set of a few hundred thousand words is fine. A hash set of a billion keys — which is the case people actually build these for — can run into many tens of gigabytes once you count string bytes, pointers, and load-factor slack. Why it breaks: you wanted this to be small enough to put one in front of every shard, every file, every cache. It isn’t.

Fix: stop storing the keys; set one bit per key instead. Hash each word, set the bit at hash(word) mod m. Now the structure costs m bits total, regardless of key length. A “0” at your word’s bit is a rock-solid “definitely not present.” Why it breaks: with one hash into a bit array, collisions are brutal. Once the array is even modestly occupied, a huge fraction of absent words land on a bit some other word already set, and the filter degenerates into answering “maybe” to everything — which is the same as having no filter.

Fix: use k bits per key instead of one. Require all k bits to be set before you’ll say “maybe.” A false positive now needs k independent coincidences instead of one, so the error rate falls roughly geometrically while the space cost grows only linearly. Concretely, with k = 4:

• Insert "banana" — hashes to indices [3, 17, 42, 88]; set those bits to 1.
• Insert "orange" — hashes to [3, 22, 71, 99]; set those. Index 3 was already 1 — fine, it stays 1.
• Query "melon" — hashes to [3, 22, 42, 88]. All four are 1, so the filter says “maybe.” Nobody inserted "melon"; banana and orange between them happened to flip every bit melon needed. That’s a false positive, and you pay for it by taking the slow path for nothing.
• Query "bananna" (the typo) — hashes to [3, 17, 50, 99]. Bit 50 is 0. “Definitely no”, squiggle it. This can never be wrong: if a word were inserted, every one of its k bits would be 1.

Why it breaks: k independent hash functions is k times the hashing work on the hot path. Fix: derive them from two. Take two good base hashes h1, h2 — often by splitting a single fast 128-bit non-cryptographic hash (MurmurHash3’s 128-bit variant, or XXH3) in half — and compute index i as (h1(x) + i · h2(x)) mod m for i = 0..k−1. That’s Kirsch & Mitzenmacher’s “less hashing, same performance” result; the split-one-128-bit-hash trick is the practitioner’s shortcut on top of it.

Why it breaks: you still have to choose m and k, and guessing wrong is how these fail in production. Fix: derive them. After inserting n items into m bits with k hashes, the probability a random query returns a false positive is approximately (1 − e^(−kn/m))^k. Two consequences worth remembering:

• For a fixed target false-positive rate p, the optimal bit count is m ≈ −n · ln(p) / (ln 2)² — about 9.6 bits per key for 1% false positives, 14.4 bits per key for 0.1%. That’s the headline number: a Bloom filter for 1B keys at 1% false-positive rate is ~1.2 GB (≈ 1.12 GiB), versus a real hash set of those same keys typically running into many tens of GB once you account for key length, pointers, and runtime overhead. Easily an order of magnitude smaller in practice.
• The optimal k at that sizing is k = (m/n) · ln 2 — about 7 hashes for 1%, 10 for 0.1%.

Those constants aren’t magic numbers to memorize — they fall straight out of minimizing the equation above, and Mitzenmacher & Upfal’s Probability and Computing (linked below) walks the derivation if you want to watch 9.6 appear.

The seams — places the abstraction leaks:

• No deletion. Clearing the k bits on remove would also clear bits other keys depend on. Counting Bloom filters fix this by storing a small counter per slot instead of a single bit, so the space cost multiplies by the counter width — 4-bit counters, for example, cost 4x. There are also cuckoo filters (Fan et al., 2014), whose paper puts the crossover at a 3% false-positive rate — below that, they use less space than a space-optimized Bloom filter — and which support deletion outright. Bloom is still everywhere because it’s older, simpler, and good enough.
• You have to know n ahead of time. This is the failure mode that actually bites: the dictionary you sized for 200,000 words now holds 2 million, and the filter has quietly stopped filtering. When kn/m ≈ 1, the expected fraction of bits set to 1 is 1 − 1/e ≈ 63% — a majority of the array is lit, so absent words find all k of their bits already on far more often, and the filter stops being worth querying. Scalable Bloom filters sidestep this by layering filters of growing size to handle unknown n, at the cost of more lookups.
• Cache behavior matters more than you’d guess. A naive Bloom filter for billions of keys touches k scattered cache lines per query, and a cache miss costs far more than the handful of instructions doing the hashing. Blocked Bloom filters (Putze, Sanders, Singler) confine all k probes to one cache-line-sized block, trading a slightly worse false-positive rate for a large reduction in memory stalls. If you’re using Bloom filters on a hot path, this is where the real performance lives.
• They leak set-membership in adversarial settings. Responses to repeated membership queries can leak information about what’s in the set. The Bitcoin SPV BIP 37 story is the canonical cautionary tale: in practice, the filter parameters wallets chose were often loose enough that observers could recover much or nearly all of a wallet’s address set, especially for wallets holding only a modest number of addresses.

Back to the red squiggle. It appears because the filter said “definitely not in the dictionary” — the one answer a Bloom filter is never wrong about — and it fails to appear on a rare typo that happened to light up all four of its bits. You started with Bloom filter = bit array + k hash functions. What did this post add? — + a sizing rule tied to how many keys you'll insert. The array and the hashes give you the shape; m ≈ −n·ln(p)/(ln 2)² is what makes it actually work, and it’s the ingredient people forget. A Bloom filter nobody sized is a Bloom filter that will quietly start answering “maybe” far too often to be worth asking.

Famous related terms

• Hash table — hash table = array + hash function — the exact-answer cousin; trades memory for never being wrong. See hash-table.
• Cuckoo filter — cuckoo filter ≈ Bloom filter + deletion + better space at low false-positive rates — newer (2014) alternative; a strong default when deletions matter.
• HyperLogLog — HyperLogLog = hash + count leading zeros + harmonic mean — answers a different probabilistic question (how many distinct items?) in a few KB. Same spirit: be wrong on purpose, save orders of magnitude.
• Counting Bloom filter — counting Bloom = Bloom filter + small counters instead of bits — supports remove, costs more space.
• Scalable Bloom filter — scalable Bloom = sequence of Bloom filters of growing size — handles unknown n without blowing up the false-positive rate.

Going deeper

• Burton H. Bloom — Space/Time Trade-offs in Hash Coding with Allowable Errors, CACM 13(7):422–426, July 1970. Read this for the original framing of the trade: what exactly you buy by permitting errors in one direction.
• Mitzenmacher & Upfal, Probability and Computing — the reference to open when you want the false-positive formula derived rather than quoted, so the 9.6 bits per key number stops being magic.
• Fan, Andersen, Kaminsky, Mitzenmacher — Cuckoo Filter: Practically Better Than Bloom, CoNEXT 2014. The rabbit hole: what changes when you demand deletions, and why that costs less than you’d expect.