TL;DR
A row of bits, all zero. To store something, hash it a few times and flip the slots those hashes point at. To look something up, hash it again and check the same slots.
Any slot still 0 means it's definitely not there. All slots 1 means probably there, so go check the real database.
It can only be wrong in one direction: false alarms, never misses. Costs about 10 bits per item for a 1% error rate, so 10 million records fit in roughly 12 MB. It can't list what's in it, can't count, and can't delete.
Its whole job is killing 99% of expensive lookups before they happen.
If that already makes sense, you're done. The rest is the same thing slowly, with a worked example.
Start with the annoying problem
You're building a signup page. Someone types a username, and you have to tell them whether it's taken.
Easy. Ask the database.
The trouble is that you're asking it constantly. Every keystroke in that box turns into a network call and a disk lookup, and you've got a few million users and a lot of visitors. So you're burning real resources to discover, over and over, that "xkq_dragon_9981" is available.
And it usually is available. That's the part worth noticing. Almost every name someone tries is free, which means almost every one of those expensive lookups was pointless before you even made it.
What you want is something small and fast sitting in front of the database, catching all the obvious misses so they never reach it.
That's a Bloom filter.
The idea, in one sentence
It tells you "definitely not in the set" or "probably in the set." Very fast. Almost no memory. And it never stores your actual data.
Everything below is just how that works and what it costs you.
Setting one up
You need a row of slots, each holding a 0 or a 1. All zeros to start.
A real one might have millions of slots. We'll use 16, because 16 fits on a screen.
index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
value: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
You also need hash functions. We'll use three.
If "hash function" sounds intimidating, it shouldn't. For our purposes it's just a rule that takes any input and spits out a number. It needs two properties and no others:
- Same input, same output, always. Feed it
"alex"today and next year and you get the same number both times. - Different inputs land in different places, spread reasonably evenly across 0 to 15.
That's it. That's the whole job description.
Adding a name
To add "alex", run it through all three hash functions.
- h1("alex") = 2
- h2("alex") = 7
- h3("alex") = 13
Flip those three slots to 1.
index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
value: 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0
Now add "priya". Her hashes give 4, 7, 11.
Slot 7 is already 1. You just leave it. Nothing anywhere records that two different names are now leaning on that same slot, and that detail is going to matter quite a lot later.
index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
value: 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0
One more. "sam" gives 0, 9, 13.
index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
value: 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0
Three usernames stored.
Look at what isn't in that row, though. The strings "alex", "priya" and "sam" appear nowhere. The filter didn't keep them. It kept the marks they left on the way through, and that's a genuinely different thing.
Looking something up
Same procedure. Hash the input three times, check those three slots.
When some slot is 0
Someone types "maria". Hashes give 1, 6, 12.
Slot 1 is 0.
"maria" is not taken. Skip the database entirely.
And that's a certainty, not a guess. Think about why. If "maria" had ever been added, slot 1 would have been flipped to 1 right then. It's still 0. So she was never added. There's no room in that argument for the filter to be wrong.
When every slot is 1, and the name really is taken
Someone types "alex". Slots 2, 7, 13, all 1.
Probably taken. You go query the database, it confirms, you show the "sorry, try another" message. The filter did its job and routed the check where it belonged.
When every slot is 1, and the name is actually free
Someone types "jordan". Hashes give 0, 4, 13.
All three are 1.
Except nobody ever added "jordan". Slot 0 came from "sam". Slot 4 from "priya". Slot 13 from "alex". Three unrelated names happened to cover exactly the three slots that "jordan" checks, and the filter has no way to tell the difference.
So it says "probably taken," you query the database, the database says no such user, and you tell the person the name is free.
You made one unnecessary lookup. That's it. That's the whole price of being wrong.
The rule everything hangs on
"No" is always right. "Yes" only means "maybe."
A Bloom filter can produce a false positive. It cannot produce a false negative. It will never tell you something is absent when it's actually sitting right there.
That lopsidedness isn't a flaw nobody got around to fixing. It's the trade. You accept a handful of wasted lookups, and you get back a structure small enough to live in memory and fast enough to check in nanoseconds.
One thing follows from this that people miss, so it's worth saying flatly: a Bloom filter is only useful when something trustworthy sits behind it. It screens. It doesn't decide. Every "maybe" has to go somewhere that knows the real answer. Used on its own, with nothing to verify against, it's just a machine that's confidently wrong every so often.
Why anyone accepts occasional wrong answers
The numbers.
Take 10 million usernames. Store them properly at roughly 20 bytes apiece and you're at 200 MB, and that's before you build any kind of index on top to search them quickly.
Put them in a Bloom filter at 10 bits per entry and you get about a 1% false positive rate using 12.5 MB.
So 12.5 MB of memory kills 99% of your database traffic. That's not a tuning improvement. It's a different kind of answer to the question.
The two dials
Slots. More slots, fewer accidental overlaps, fewer false positives, more memory. Nothing surprising.
Hash functions. This one is not "more is better," and it catches people out.
Use only one and a single collision produces a false positive. Too fragile.
Use fifty and every insert flips fifty slots. The array fills with 1s almost instantly, and once nearly everything is a 1, everything looks like a maybe. A saturated filter says "probably yes" to every question you ask it, which makes it precisely as useful as having no filter at all.
The sweet spot is roughly "flip enough bits that the array ends up about half full." In numbers:
| Bits per item | Hash functions | False positive rate |
|---|---|---|
| 5 | 3 | ~9% |
| 8 | 6 | ~2% |
| 10 | 7 | ~0.8% |
| 16 | 11 | ~0.05% |
In practice you won't work this out by hand. You tell the library how many items you expect and what error rate you can live with, and it picks both dials for you. But it's worth knowing the shape of that table, if only so you can tell whether what you're asking for is reasonable before you ask.
What it can't do
Worth being blunt here, because people reach for Bloom filters and then get irritated that they aren't hash tables.
It can't tell you what's in it. You can't ask which usernames it knows about. It holds bits. There is nothing to read back out.
It can't count. Slot 7: flipped once, or ten thousand times? No idea. The filter has no opinion.
It can't delete. Say you want to remove "alex" and you go reset slots 2, 7 and 13. You've just broken "priya", who needs slot 7, and "sam", who needs slot 13. Now the filter starts saying "definitely not present" about names that are present, and the moment "no" stops being trustworthy the entire structure is worthless. If you need removal, look at counting Bloom filters (a small counter in each slot instead of a single bit) or cuckoo filters (a newer alternative that handles deletion and is often smaller anyway). Both cost you something.
It goes bad quietly. Size a filter for 10 million entries, feed it 100 million, and it saturates. Every answer becomes "maybe." It won't throw an error. It won't log a warning. It just stops being useful while continuing to look like it's working fine, which is honestly the failure mode to actually watch for.
Where these show up
Databases skipping disk reads. By a wide margin the most common real use. Cassandra, HBase, RocksDB and friends spread data across many files on disk, and checking every file for a key is slow. So each file carries a Bloom filter of its own keys. "Definitely not in here" means skip the file completely, no disk read at all. Structurally it's the exact same problem as the signup form: cheap check first, expensive check only if you have to.
Browsers checking for dangerous URLs. Shipping the full list of known malicious sites to every browser isn't practical. Ship a compact filter instead. Anything that comes back "definitely safe" resolves locally in an instant, and only the rare maybe goes to a server. Nice side effect: most of your browsing history never leaves your machine.
Caches ignoring one hit wonders. A big chunk of CDN requests are for things nobody will ever ask for twice, and caching those is wasted space. So keep a filter of what you've seen once, and only bother caching something on the second request.
Blockchain clients. Every Ethereum block header carries a 2048 bit Bloom filter summarising the log addresses and topics inside that block. A client hunting for events from one particular contract checks the header filter and skips the entire block on a "no," instead of parsing every transaction since genesis.
So, when should you reach for one?
Three conditions, and you want all three.
You're doing a lot of lookups against a big set. Most of those lookups come back negative. And there's something slow behind the check, a disk, a network call, another service, that you'd like to stop bothering.
Hit all three and a Bloom filter is close to free money. Miss one and it's probably not worth the complexity. If your set is small enough to sit in a hash table, use the hash table. If most lookups are hits anyway, the filter is just extra work in front of a query you were going to make regardless.
The mental model that sticks: it's a bouncer, not a judge. Turns away the obvious no's instantly, waves everything else through to someone who actually knows.
Burton Bloom published this in 1970, in a paper about hyphenation in typesetting software. It now holds up databases, browsers and blockchains. Simple ideas tend to outlast clever ones.
Top comments (0)