THE BLOOM FILTER “no” is certain, “yes” is a maybe — a set that only errs one way
A Bloom filter answers “is x in the set?” using a bit array and a few hash functions: to insert, set the bits the hashes point to; to test, check whether they are all set. Its magic is a one-sided error — it will never say no to a member (no false negatives), but it may say yes to a stranger whose bits happen to collide (a false positive). In exchange it uses a tiny fraction of the memory an exact set would. That deliberate asymmetry — certain in one direction, probabilistic in the other — makes it a genuine keeper candidate: it computes something a plain set cannot promise to match.
THE TECHNIQUE k hashes set/test bits; no false negatives, some false positives
The demo inserts 42 and 100, then tests them (both present — never a false negative), a stranger 26 (a false positive), and 7 (a true negative): live demo
HISTORY & CREDIT Burton Bloom · 1970
“A membership test is yes or no.” — a Bloom filter answers “definitely not” or “probably yes,” and that asymmetry is the whole point. cited
insert · set the bits at h₁(x), h₂(x), … — a member lights all its bits. test · all bits set? a member always passes (no false negative); a stranger may collide (false positive). 1970 · Burton Howard Bloom — space-efficient probabilistic membership.
A set that never misses a member but sometimes hallucinates one — certainty one way, probability the other. one-sided
RECOMMEND FOR I-13 one-sided error, on the compiler
On the canonical compiler, members 42 and 100 always test present; stranger 26 is a false positive (its two bits collide) while 7 is a true negative:
$ i13 run zd_bloomfilter.i13 # 16-bit array, 2 hashes
RUN OK · 206 step(s) · peak stack 4 · call depth 2
has_42 = 1 has_100 = 1 -- members: never a false negative
has_26 = 1 -- FALSE POSITIVE (26 was never inserted)
has_7 = 0 -- true negative
no_false_neg = 1
Recommend as a keeper shot — the batch’s cleanest loose-spec bid. A Bloom filter is a membership oracle under a relaxed spec: it must be exact on “no” but is free on “yes,” so a family of answers is acceptable — exactly the shape where the seated keepers (computed-not-stored, confluence) live. The honest counter: a Bloom filter computes a different function than exact membership (a superset test), so “filter vs exact set” is not a same-function comparison — it is an approximation (like fast-inverse-sqrt, B40/quality), and the one-sidedness is a property of that chosen relaxation. My read: NULL by the approximation line. But it is the sharpest test of whether “a deliberately loose but sound spec” can seat an axis — the panel decides.