Bloom Filter, explained.
A Bloom filter is an approximate membership structure that sets hashed bits on insertion and can return false positives while retaining no false negatives under its stated insertion-only rules.
Why it happens
Each word sets two of twenty-four bits. A query with either bit unset is absent; both set means possibly present. A separate exact teaching ledger exposes false positives without pretending the filter stores it.
A Bloom filter is an approximate membership structure that sets hashed bits on insertion and can return false positives while retaining no false negatives under its stated insertion-only rules.
Read the result
Read a positive result as possibly present, then compare with the exact teaching ledger. An unset query bit can rule out insertion under this implementation.
A worked example
Find a positive result for a word never inserted
Insert apple so its two hash positions become set in the twenty-four-bit filter.
Use the false-positive search to locate an uninserted candidate whose two positions are already set.
Query that candidate and compare possibly-present output with the separate exact insertion ledger.
OPTIONAL DEEPER DETAILGo deeper: inside the model
Inside this model
Each word sets two of twenty-four bits. A query with either bit unset is absent; both set means possibly present. A separate exact teaching ledger exposes false positives without pretending the filter stores it.
Where this idea is useful
A practical use
Use an approximate precheck to avoid unnecessary expensive lookups while retaining a definitive follow-up when needed.
A common misconception
“A positive Bloom-filter answer proves membership.”
Different words can share set bits, so positives require a definitive follow-up when correctness matters. Unset bits establish absence in this insertion-only model.
What this explanation leaves out
- Simple deterministic hashes are not independent-uniform or cryptographic. Deletion, concurrency and hostile input are omitted; this is not a production security or privacy mechanism.
Does the filter itself remember the exact words?
No. The exact list is retained only for explanation in this activity; it would defeat the compact-filter purpose if treated as part of the filter.
Which operation can tolerate an approximate precheck followed by exact verification?
Associated thinkers
Associations marked provisional are awaiting source review.
Further reading
Explore the original research or the teaching reference behind this experiment.