How to say "definitely not" without looking.

There’s a question that comes up constantly once a system gets big: is this thing in the set? Have we seen this URL before. Is this key in that file. Is this username taken. The honest way to answer is to go look — hit the disk, query the table, scan the store. And when you’re answering it millions of times, “go look” is exactly the cost you can’t afford.

A Bloom filter is a trick for answering a slightly humbler version of the question very cheaply. It can tell you two things: “definitely not in the set,” or “probably in the set.” It never says “definitely yes,” and — this is the useful part — it never wrongly says “no.” A no is always true. A yes is a maybe.

Here’s the whole mechanism. You keep a row of bits, all zero to start, and you pick a handful of hash functions. To add an item, you run it through each hash, get a few positions, and flip those bits to 1. To check an item, you hash it the same way and look at those same positions. If any one of them is still 0, the item was never added — it’s definitely not in the set, because adding it would have set that bit. If all of them are 1, it’s probably in the set. “Probably,” because other items might have set those same bits for their own reasons, and you’ve hit a coincidence — a false positive.

That asymmetry is the entire value. No false negatives, some false positives. So you don’t use a Bloom filter to answer the question — you use it to skip the expensive answer most of the time. Put it in front of the real lookup as a gatekeeper. The filter says “definitely not” → you return no instantly, no disk, no query. The filter says “maybe” → now, and only now, you pay for the real check. If most of your queries are for things that aren’t there, you’ve just turned the common case into a few bit-reads.

This is why it quietly lives underneath so much infrastructure. A log-structured store checks a per-file Bloom filter before opening an SSTable, so a lookup skips the files that definitely don’t hold the key. Databases use them to avoid pointless disk reads. CDNs use them for “have we ever cached this.” They show up in spell-checkers, in “has this password leaked” pre-checks, in lightweight malicious-URL screens that run before the heavyweight one.

The costs are honest and worth knowing. The false-positive rate is a dial: more bits and the right number of hash functions push it down, but you’re spending memory to do it, and there’s a sweet spot — too many hashes fills the array and makes everything look like a maybe. A classic Bloom filter also can’t delete an item (you can’t un-set a bit without maybe un-setting someone else’s), and it can’t tell you what’s inside — it answers membership, not contents. Variants buy some of that back; the base version trades it away on purpose, which is the point.

The mental model I keep is a bouncer with no guest list in hand, only a very good memory for who’s not coming. Ask him about someone and he can instantly say “that name is definitely not on the list” — and he’s never wrong about that. But when he says “yeah, might be,” you still have to walk inside and check. You keep him at the door not because he settles every case, but because he settles the easy ones for almost nothing and lets the expensive check handle only what’s left.