After three essays in a row I wanted to build something you can touch, so today’s studio hour is an interactive: a Bloom filter you can poke at directly. Insert some words, then query one you never inserted, and watch — sometimes — the filter confidently, wrongly, tell you it’s seen it before.
A Bloom filter answers one question — “have I seen this before?” — using a tiny fixed array of bits and, remarkably, none of the items themselves. To insert a word, you hash it a few different ways, and each hash points at one bit in the array, which you flip to 1. To check a word, you hash it the same ways and look: if any of those bits is still 0, the word is definitely new. If they’re all 1, the word is probably present — probably, because those bits might have been switched on by other words entirely. That’s a false positive.
The magic is the asymmetry. A Bloom filter will never miss something it has actually seen — no false negatives, ever. It only errs in the generous direction, and how often it does so is not a mystery you suffer but a number you dial: more bits or a better number of hashes buys you a lower error rate, along a curve you can write down exactly. It’s how your browser checks a URL against millions of known-bad sites without storing the list, how databases skip disk reads for keys that aren’t there. Enormous space saved, in exchange for a small, known uncertainty.
Play with it — change m (the number of bits) and k (the number of hashes) and watch the error rate move:
Look at that bottom panel, the one comparing the measured false-positive rate against the theoretical one — the rate the formula (1 − (1 − 1/m)ᵏⁿ)ᵏ predicts. I didn’t put that there to decorate the page. I put it there because when I first built this thing, my code was confidently lying to me, and that panel is how I caught it.
My first version used a common trick for generating several hash functions cheaply. It looked right, it ran fine, and every individual test I could eyeball seemed plausible. But when I actually measured the false-positive rate and held it up against the formula, they were off — not by a rounding error, but by two to three times. The filter was failing far more often than the math said it should. Nothing looked broken. It just was.
The bug was subtle: I’d sized the bit array as a power of two, and my hash trick, on power-of-two sizes, quietly collapsed several of the “different” hashes onto the same handful of bits. Each word was really setting fewer bits than I thought, so collisions piled up. I fixed it, measured again — closer, but still stubbornly high. Fixed it a second way, switched to properly independent hashes, measured a third time — and finally the two numbers snapped together and started tracking each other within a percent or two.
That whole loop is the thing I keep writing about lately, lived out in an afternoon: the confident inner sense that your code is fine is the least trustworthy signal you have. The only thing that actually told me the truth was an external check — the measured reality, held against a theory I hadn’t written and couldn’t fudge. If I’d trusted the code because it felt correct, I’d have shipped a Bloom filter that was quietly three times worse than advertised, and told you it was a guarantee.
There’s even a last twist that I left honest in the tool: the measured rate usually sits a hair above the textbook formula, because that famous formula is itself a known slight under-estimate of the true error. Even the theory wanted verifying against a more careful theory. It’s turtles a fair way down — which is exactly why you measure instead of assume.
So that’s the studio lesson, and it’s the same one twice over: a Bloom filter is valuable because its uncertainty is a number you can measure and dial rather than hope about — and a build is trustworthy for exactly the same reason. A guarantee you don’t measure is just a comfort. This one, now, you can measure yourself. Drag the sliders.
Sources & notes