← Learnings

Bloom Filters, Explained Properly

5 min·data structures, algorithms, databases

Most explanations throw a wall of theory at you and leave out the one thing that actually makes it click. This post fixes that.

The one question a bloom filter answers

Is this item definitely not in the set, or possibly in it?

It can tell you "no" with total certainty, but only ever says "maybe" for yes. It never gives a false negative; it can give a false positive. That asymmetry is the whole point — everything falls out of it. In exchange for the fuzziness, you get tiny memory and blazing speed.

What it's made of

Two things: a bit array — a row of light switches, all starting at 0 — and a few hash functions, machines that take an item and spit out a position in the array. No stored words. No list of items. Just switches and hash functions.

How many bits does one item take?

This is the question that trips everyone up. When you add cat, how much room does it take?

Exactly k bits — and k is a number you pick in advance, not something the word decides.

A word has no natural size. You decide up front that every item sets exactly 3 bits. That's k, the same for everything. cat sets 3 bits, dog sets 3 bits, elephant sets 3 bits. Word length is irrelevant — elephant takes no more room than cat. Which bits? That's what the hash functions decide.

Building the array

Tiny array of 10 slots, k = 3. Add cat:

THREE HASHES, ONE WORD hashA("cat") 4 hashB("cat") 4 SAME SLOT — TWO HASHES CAN COLLIDE hashC("cat") 1
FIG 1 · THREE HASHES, AND TWO OF THEM COLLIDE

Flip those bits on.

AFTER ADDING cat 0 1 0 0 1 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 cat cat TWO BITS LIT, NOT THREE — hashA AND hashB BOTH SAID 4
FIG 2 · THE ARRAY AFTER cat

cat lit only 2 distinct bits even though k = 3, because two hashes both said 4. Now add dog, which hashes to 7, 1 and 9.

AFTER ADDING dog (7, 1, 9) 0 1 0 0 1 0 0 1 0 1 0 1 2 3 4 5 6 7 8 9 cat+dog cat dog dog BIT 1 WAS ALREADY LIT — SETTING IT AGAIN DOES NOTHING
FIG 3 · THE ARRAY AFTER cat AND dog

Bit 1 was already lit by cat; dog setting it again does nothing.

The insight: you can't read the array

Here's the part that sticks. Look at that final array with the labels taken away.

THE SAME ARRAY, HANDED TO YOU COLD 0 1 0 0 1 0 0 1 0 1 0 1 2 3 4 5 6 7 8 9 NO NAMES. NO COUNTS. NO RECORD OF WHO LIT ANYTHING.
FIG 4 · THE SAME ARRAY, WITH NOTHING TO GO ON

If I handed you this array cold, you could not tell me what's in it. You couldn't say "cat and dog are here." All you could say is "switches 1, 4, 7 and 9 are on." The array keeps no record of who lit each bit. A lit bit just means somebody hashed there — it doesn't remember who, or how many.

That forgetfulness is the source of everything. It's why the filter is tiny — it isn't storing your words, just their smeared fingerprints — and it's why "maybe" can never become "yes."

THE WHOLE THING IN THREE STEPS 1 · ADD cat HASHES TO 4, 4, 1 — TWO HASHES BOTH SAY 4, SO ONLY 2 DISTINCT BITS GET LIT 0 0 1 1 0 2 0 3 1 4 0 5 0 6 0 7 0 8 0 9 2 · ADD dog HASHES TO 7, 1, 9 — BIT 1 WAS ALREADY LIT BY cat, SO SETTING IT AGAIN DOES NOTHING 0 0 1 1 0 2 0 3 1 4 0 5 0 6 1 7 0 8 1 9 Looking at bits 1, 4, 7 and 9 you cannot tell it was cat and dog — the array forgot who lit them. 3 · QUERY wolf, NEVER ADDED HASHES TO 4 AND 1 — BOTH HAPPEN TO BE LIT ALREADY, SO THE FILTER SAYS MAYBE. IT IS WRONG. wolf wolf 0 0 1 1 0 2 0 3 1 4 0 5 0 6 1 7 0 8 1 9 0 — NEVER TOUCHED, PROOF OF ABSENCE 1 — SOMEONE HASHED HERE COLLISION — THE FALSE POSITIVE
FIG 5 · THE WHOLE MECHANISM, IN THE ORDER IT HAPPENS

Querying: same hashes, then an AND

To check cat, hash it again. Same outputs, 4, 4 and 1, and then check whether those bits are all 1.

QUERYING cat — HASH AGAIN, THEN AND 0 1 0 0 1 0 0 1 0 1 0 1 2 3 4 5 6 7 8 9 cat HASHES TO 4, 4, 1 — ARE BITS 4 AND 1 BOTH 1? yes "possibly present"
FIG 6 · THE QUERY IS AN AND ACROSS THE BITS cat ITSELF NAMES

It's an AND across the item's own target bits. One 0 anywhere is an instant "definitely not" — it doesn't even check the rest.

Why "No" is certain and "Maybe" isn't

It comes from one fact: bits only ever turn on, never off.

WHAT ONE BIT CAN PROVE a 0 bit this slot was never touched CERTAIN — NOTHING EVER ERASES a 1 bit someone touched this slot AMBIGUOUS — THE ARRAY FORGOT WHO
FIG 7 · WHAT A SINGLE BIT IS EVIDENCE OF

A 0 is proof of absence. If a position is still 0, nothing ever hashed there, so any item needing that bit was definitely never added. A 1 is only circumstantial: it could be your item, or other items that happened to share that slot. When all an item's bits are 1 you can't tell those apart, so the only honest answer is "maybe."

This is also why false negatives are impossible — a real member always finds its own bits lit, because it set them and nothing erases.

The false positive

Query wolf, never added, but it happens to hash to bits 4 and 1 — both already lit by cat.

wolf — NEVER ADDED 0 1 0 0 1 0 0 1 0 1 0 1 2 3 4 5 6 7 8 9 wolf HASHES TO 4 AND 1 — BOTH ALREADY LIT BY cat "maybe present" — and it is wrong, and it cannot know that
FIG 8 · A WORD THAT WAS NEVER ADDED, ANSWERED MAYBE

The filter isn't lying. Its real claim is "every bit wolf needs is lit," which is true. It never promised wolf is present, only that it can't rule it out. And it genuinely can't: "wolf was added" and "cat was added and wolf collides" produce the identical pattern. The array forgot who lit those bits, remember? So it cannot distinguish them.

Why it's useful anyway

A trustworthy "no" lets you skip expensive work.

WHAT THE ANSWER BUYS YOU query the filter "definitely not" skip the expensive lookup THE COMMON CASE "maybe" do the real lookup to confirm THE RARE CASE
FIG 9 · THE CHEAP GATE IN FRONT OF THE EXPENSIVE LOOKUP

A false positive costs you one wasted lookup, never a wrong final answer, because you always verify a "maybe" against the real source. Real uses: LSM-tree databases like Cassandra and RocksDB put one in front of each on-disk table to skip reads for keys that definitely aren't there, and browser safe-browsing keeps a local filter of bad URLs and only phones home on a "maybe."

The tradeoff, briefly

More bits and more hash functions lower the false-positive rate, at the cost of memory. You pick how many items you'll store and what error rate you'll tolerate; the array size and number of hash functions fall out of that, and the sweet spot lands when the array is about half-full of 1s. And you can't delete from a basic bloom filter — clearing a bit might break other items sharing it.

Going deeper. The exact sizing math — deriving the false-positive rate (1 − e^(−kn/m))^k, the optimal m = −(n ln p)/(ln 2)², the optimal k = (m/n) ln 2, and why ln 2 keeps appearing — is laid out clearly in Wikipedia's bloom filter article, which carries the full derivations; in Bloom Filters by Example, which is interactive and lets you watch the array fill; and in Burton H. Bloom's original 1970 paper, Space/Time Trade-offs in Hash Coding with Allowable Errors.

The one-paragraph version

A bloom filter is a bit array plus a few hash functions. Adding an item flips the k bits it hashes to; checking looks at those same bits. Any 0 means definitely-not; all 1s mean probably-yes. The key: you can't read the array — a lit bit doesn't remember who lit it, so a 0 proves absence but a 1 is only circumstantial. That one-way guarantee makes it a perfect cheap gate in front of an expensive lookup: trust the "no," verify the "maybe."