Imagine a doorman at a very exclusive party.

There are two million names on the guest list. Every time somebody walks up, he has to decide: are you on it? If he keeps the actual list, he's flipping through two million names while a queue forms down the street. Too slow.

So he does something strange. He throws the guest list away.

And somehow, he still catches almost everyone who wasn't invited — instantly, from memory, without a single name written down. He's not magic. He just has a clever system, and he's willing to be wrong in one specific direction.

That system is called a Bloom filter, and once you see how it works you'll notice it everywhere — in your browser, in your bank's fraud checks, in the databases behind almost every app on your phone.

Let's build it.

The trick: don't remember names, remember switches

Picture a wall of light switches, all off. Say sixteen of them, numbered 0 to 15.

Our doorman has three "recipes." A recipe is just a fixed set of steps that turns a name into a number between 0 and 15. It doesn't matter what the steps are — count the letters, add them up, whatever — as long as two rules hold:

  1. The same name always gives the same number. Every single time.
  2. Different names scatter unpredictably across all sixteen switches.

Now, when a guest is added to the list, he runs her name through all three recipes, gets three numbers, and flips those three switches on.

Then he forgets her name entirely.

Adding a name to a Bloom filter: the name is fed through three recipes producing the numbers 2, 7 and 11, and those three switches light up while the name itself is discarded

That's genuinely the whole idea. Maya walks up to the list, three switches flip on, and Maya's name is gone forever. The wall doesn't know who flipped what. It only knows which switches are on.

Checking someone at the door

Someone arrives. The doorman runs their name through the same three recipes and looks at those three switches.

Two lookups: dave finds one switch off, proving he was never added; maya finds all three on, meaning she was probably added

Here's where it gets interesting, because there are exactly two possible outcomes — and they are not equally trustworthy.

If even one switch is off: definitely not on the list

This one is airtight, and it's worth pausing on, because it's the whole reason the trick works.

Think about it backwards. If Dave had been added, all three of his switches would have been flipped on at that moment. Switches never turn back off. So if switch 9 is off right now, there is simply no way Dave was ever added.

Not "probably not." Not possible. The doorman can turn him away with total confidence, having never known his name.

If all three are on: probably on the list

This is the weaker answer, and the honest one.

All three of Maya's switches are on. That's consistent with Maya having been added. But it's also consistent with something more awkward: three other guests, between them, happening to flip those same three switches.

The doorman genuinely cannot tell the difference. Nobody owns a switch.

The part that surprises people

Let's watch that go wrong, because it's the thing most explanations rush past.

Suppose Maya lit switches 2 and 7. Arun lit 7 and 11. Priya lit 11 and 2. Between the three of them, switches 2, 7 and 11 are all on.

Now Zoe shows up. She was never invited, never added, never anywhere near this party. Her three recipes happen to point at 2, 7 and 11.

Three different people lit switches 2, 7 and 11 between them; zoe was never added but her recipes point at those same switches, so the filter answers probably here

All three on. The doorman waves her in.

This is called a false positive, and it is not a bug you can fix — it's the price of admission. The filter is allowed to say "probably" when the answer is actually "no." What it is never allowed to do is the opposite: it will never say "definitely not" about someone who really is on the list. That direction is impossible, and that asymmetry is the entire point.

More switches and more recipes make false positives rarer. Nothing makes them impossible.

So why would anyone accept that?

Because of what you get in exchange. Some rough numbers:

Keeping the real list The switch wall
10 million email addresses around 250 MB about 12 MB
Time to check one search the whole list look at 3 switches
Wrong answers never roughly 1 in 100

Twenty times smaller, and instant. And critically, that speed doesn't degrade: checking against ten million names costs exactly the same as checking against ten — three switches either way.

That's a trade worth making surprisingly often, and here's the pattern that makes it safe:

Use the filter as a bouncer, not as a judge. When it says "definitely not," trust it completely and stop. When it says "probably," go do the slow, real check.

Because most questions are "no," the fast, certain "no" handles the overwhelming majority of traffic, and the slow path only runs on the rare maybes.

Where you've already relied on one today

Your browser. Chrome checks every page you visit against a list of millions of known dangerous sites. It cannot download that list, and it really shouldn't phone home about every page you open. So it carries a filter. Almost every page you visit gets a definite "not dangerous" instantly and privately. The rare maybe triggers a real check.

Databases. When an app asks for a record, the database would otherwise dig through files on disk to discover it doesn't exist. A filter answers "definitely not here" in microseconds and skips the dig. Every major database does this.

Your bank. Before the expensive fraud analysis runs, a filter rules out the vast majority of ordinary transactions.

Content networks. Before fetching something from a distant server, a filter can answer "we've definitely never cached that" without a round trip.

In all four, the same shape: a cheap, certain "no" protecting an expensive "maybe."

One catch worth knowing

You can't remove anyone.

It seems like you should be able to — just flip Maya's three switches back off. But switch 7 is also holding up Arun, and switch 2 is holding up Priya. Turning them off to erase Maya would quietly erase them too, and now the filter tells lies in the dangerous direction: "definitely not" about people who are on the list.

So a plain Bloom filter is add-only. When it fills up too much and starts saying "probably" too often, you throw the whole wall away and rebuild it. There are fancier variants that handle deletion, and they all pay for it somewhere else.

The one thing to remember

A Bloom filter answers a question that sounds impossible: is this thing on a list I'm not keeping?

It gets there by giving up something most systems refuse to give up — the ability to always be right. In return it gets to be tiny and instant. And it's very careful about which direction it's allowed to be wrong in:

"No" means no. "Yes" means maybe.

Once that clicks, you start seeing the same bargain everywhere in computing. It's rarely about finding the perfect answer. It's about knowing exactly which mistakes you can afford, and then making the cheapest thing that only makes those.

Got a concept you'd like pulled apart like this? Tell me on LinkedIn — I'm always looking for the next one.