‘Have I seen this before?’ — answered in a few bits, for a set of millions. A Bloom filter hashes each item to several positions in a bit array and sets them. To check membership, look at those bits: if any is 0, the item is DEFINITELY not present; if all are 1, it’s PROBABLY present (a small false-positive chance). It never says no when the answer is yes. Tiny space, one-sided error. Slide to add items and query.
A Bloom filter is a probabilistic set: a bit array of size m plus k independent hash functions. To ADD x, set the k bits hᵢ(x). To TEST x, check those k bits — if ANY is 0, x is DEFINITELY absent (no false negatives); if all are 1, x is PROBABLY present (false positives occur when other items happened to set those bits). It uses far less space than storing the elements, at the cost of a tunable false-positive rate ≈ (1−e^(−kn/m))^k, and it cannot delete or enumerate. Used in databases, caches, and networking to skip expensive lookups. A fail-loud self-check throws unless every added item tests present (no false negatives). ◆ real data structures, node-verified.
One-sided error is exact: NO false negatives, but false positives rise with load (fill the array and everything reads ‘maybe’). Standard Bloom filters can’t delete (counting variants can). Space vs error is a tunable trade.