Bloom Filters — Probabilistic Membership Testing at Scale

A Bloom filter is a probabilistic data structure that can tell you 'definitely not in the set' or 'probably in the set' — with no false negatives and a tunable false positive rate. It uses a fraction of the memory that an exact dict or set would require. This comes up in staff DE interviews when the interviewer asks 'how would you check membership in a 100-billion-entry set without storing all 100 billion entries?'