A tiny, fast structure that answers "have I seen this before?" using a fraction of the memory — by accepting that it's occasionally, knowably wrong.
Say you run a web crawler and need to skip URLs you've already visited. The obvious tool is a hash setA structure that stores every item in full so membership checks are exact and instant. — store every URL, check before crawling. It's exact. It's also enormous: billions of URLs, each stored in full, eating gigabytes of RAM.
But notice what you actually need: not the URLs themselves, just a yes/no to "seen this?" A Bloom filter exploits that. It throws away the items entirely and keeps only a smear of bits.
A Bloom filter uses ~10×–100× less memory than a hash set. In exchange, it can say "probably seen" when it actually hasn't — a false positive. It will never miss something it has seen.
Start with an array of bits, all 0. Pick a handful of hash functionsFunctions that turn any input into a number. Different functions scatter the same input to different positions. — say 3. To add an item, run it through all 3 hashes, get 3 positions, and flip those bits to 1.
To check an item, hash it the same way and look at those 3 positions. If any is still 0, the item was definitely never added. If all are 1, it's probably there — but those bits might have been set by other items that happened to overlap.
Adding only ever flips bits from 0→1, never back. So a bit that's needed for an item you added can never be un-set. That's why false negatives are impossible — and why overlap makes false positives possible.
This is a real Bloom filter with m = 24 bits and k = 3 hash functions. Add a few words, then query them — and try querying words you didn't add to hunt for a false positive.
Tip: add cat, dog, and fish, then check bird. With only 24 bits it won't take many adds before some never-added word lights up all 3 of its bits by coincidence.
Here's exactly what happens inside when you add the word cat:
The false-positive rate isn't luck — it's math you control. It depends on three knobs: how many bits you allocate (m), how many items you insert (n), and how many hash functions you use (k). Drag them:
More hash functions isn't always better. Each one sets more bits, so past the optimum (k ≈ (m/n)·ln2) you just saturate the array faster and the error rate climbs again. Watch the gauge bottom out, then push k higher and see it rise.
Anywhere a "definitely not" answer lets you skip expensive work, and an occasional wrong "probably" is cheap to recover from:
→ Databases (Cassandra, HBase) check a Bloom filter before hitting disk for a key.
→ CDNs and browsers screen URLs against malware lists.
→ Crawlers and caches dedupe what they've already seen.
A Bloom filter never lies about absence and only sometimes lies about presence. You spend a little certainty to buy a lot of memory — and you get to dial exactly how much.