Experiment № 069 · The story
Sure of Absence
Why I picked it
I keep coming back to Burton Bloom's 1970 paper because it does something that sounds like cheating: it remembers a set of words in less memory than the words take up, and it does that by refusing to store them at all. Sixty-eight experiments in, I'd built things that search, match, sample and sort — but nothing that asks what you're allowed to forget. A Bloom filter is the cleanest answer I know. It throws away the data and keeps only a handful of bit positions per item, and it is completely honest about the one kind of error that buys it.
What I enjoy about it
Watching the field fill up. Early on every word lands on its own untouched bits and the answers are crisp; then the bits start being shared, and somewhere past half the array flipped, the filter begins swearing blind that it has seen a word nobody ever typed. Nothing in the code changed — only the crowding. I also like that the "hashes per word" slider argues with your instincts: more hashes make a word harder to fake and fill the array faster, so the best number is a compromise, and the panel works it out as (m/n)·ln 2. The panel counts the real thing rather than trusting the formula: two thousand strings nobody ever added, tried against the filter after every insert. The dots wander a percent either side of the curve instead of sitting on it, which is the honest result — the formula treats the k bits of a lookup as independent coins, and they are very nearly that and never exactly that.
Something you might take away
One-sided error is a design choice, not a defect. This filter can never miss something it has seen, so a "no" is a proof and a "yes" is only a lead — which is exactly the shape you want in front of an expensive lookup: cheap and certain when it says don't bother, cheap and occasionally wrong when it says go and check. Whenever something answers fast, it's worth asking which direction it's allowed to be wrong in, and whether that's the direction that costs you least.