Bloom filter: a guarantee you can measure

Ask "have I seen this before?" — using a tiny fixed array of bits, and none of the items themselves.

Insert a few words, then query one you never inserted — watch for a false positive.
0
items (n)
0%
bits set
3
optimal k here
0.0%
MEASURED false-positive rate
0.0%
THEORY: (1 − (1 − 1/m)kn)k

A Bloom filter never gives a false negative: "not present" is always the truth. It only ever errs the other way — a confident "present" that's wrong. You trade a little certainty for enormous space savings, and the price is a number you can dial and check, not hope about. The measured rate above should sit close to — and usually a hair above — the formula, because the classic formula is a known slight under-estimate. Even the theory wants verifying.