A Bloom filter is one of those data structures that sounds like a magic trick: it tells you whether you've seen something using a fraction of the memory, and it's never wrong when it says no. The catch — it can be wrong when it says yes. I built one you can watch, including a button that hunts down a real false positive.
▶ Live demo: https://dev48v.github.io/bloom-filter/
Source: https://github.com/dev48v/bloom-filter
The mechanism
Start with an array of m bits, all 0, and k hash functions.
- add(key) — hash the key k ways, set those k bits to 1.
-
check(key) — hash it the same k ways and look at those bits:
- any bit is 0 → the key was definitely not added (adding it would have set that bit).
- all bits are 1 → the key is possibly present.
That asymmetry is the whole thing. There are no false negatives: if you added a key, all its bits are 1, so check always says "possibly present." But bits are shared, so as the array fills, some other combination of keys can light up all k bits of a key you never added — a false positive.
Watch a false positive happen
In the demo, add a handful of words, then hit 🎯 find a false positive. It scans for a word you never added whose k bits are all already set by other words, and the filter cheerfully reports possibly present. Seeing "melon — but it was never added" is the moment the trade-off clicks: you're not storing the keys, only the shadows they cast on a bit array, and shadows overlap.
Why anyone accepts wrong answers
Because "definitely not" is often the answer you actually need, and it's free of error. Real uses:
- Databases (Cassandra, HBase, LevelDB/RocksDB) check a Bloom filter before hitting disk. "Definitely not in this file" → skip the read entirely. A false positive just means one wasted read; a false negative would mean missing data, which is why the no-false-negative guarantee matters.
- CDNs / caches — "have we ever cached this?" without storing every key.
- Browsers checking a URL against a huge malware/blocklist without shipping the whole list.
- Distributed systems avoiding expensive cross-node lookups for keys that definitely don't exist.
Tuning it
The estimated false-positive rate after n items is:
p ≈ (1 − e^(−kn/m))^k
Two knobs:
- m (bits) — more bits, fewer collisions, lower error. This is your space budget.
-
k (hash functions) — there's a sweet spot:
k = (m/n)·ln 2. Too few and collisions are likely; too many and you fill the array faster, which raises the rate. The demo shows the live estimate as you slide m and k, so you can watch it bottom out and climb again.
One implementation note: you don't need k truly independent hash functions. Double hashing — h_i = h1 + i·h2 mod m from two base hashes — gives k good-enough indices, and that's what the demo uses.
Add some keys, trigger a false positive, then crank m up and watch the error rate fall. If it made Bloom filters click, a star helps others find it: https://github.com/dev48v/bloom-filter
Top comments (0)