Thought Toys · Computation & information · Exhibit 59
A Bloom filter can remember a whole dictionary in a sliver of memory and answer in an instant. The catch: it can be wrong when it says yes — never when it says no — and the more you pour in, the more often its yes is a false alarm.
The bit array, and the false-alarm rate as it fills predicted measured
—
—
The grid is the entire filter: 480 bits, nothing else — no words are stored. To add a word, run it through k hash functions — scramblers that turn a word into a bit position and switch on the k bits they point at. To ask “have I seen this word?”, hash it the same way and look: if any of its k bits is still 0, the word was certainly never added — that “no” is airtight, because adding it would have set that bit. If all k bits are 1, the word is probably in — but those bits might have been switched on by other words entirely. That's a false alarm, and it's the only way this structure can ever lie.
Add a handful of words and almost every “yes” is real. Keep adding, though, and the grid lights up; once most bits are 1, any random word's k bits are likely all already set, so the filter waves through strangers it never saw. Watch the curve climb: the false-alarm rate goes from near-zero to near-certain as the array saturates. Through all of it, test a stored word and the answer is always “probably yes” — never a false “no.” That one-sidedness is the whole point: a Bloom filter is a fast, tiny gatekeeper that lets you skip the slow, exact lookup whenever it says “definitely not,” and it's never wrong about that. More hashing isn't automatically safer, either — nudge k up and each word checks more bits (harder to fool) but also sets more bits (fills faster). There's a sweet spot; past it, more hashes make things worse.
improve/verify/59-bloom-filter.js): building the actual filter
and probing 300,000 never-added words, the measured false-positive rate matches the formula across four
(m,k,n) settings; every stored word is still found (zero false negatives); and
the rate climbs monotonically as the filter fills.
Negative control: the best k really is interior — over k=1…24 the
minimum sits at (m⁄n)ln2, and both one hash and twenty-four hashes do measurably worse;
and the naive linear guess p=kn⁄m badly over-predicts once loaded, because the
real curve saturates rather than growing without bound.
Also in Computation & information: The fit that memorizes instead of learns →
← the cabinet · Thought Toys — a cabinet of explorable explanations. Exhibit 59.