Bloom filter
Probabilistic data structure for "is the element in the set?" — answers "maybe" or "definitely not". No false negatives, controllable false positive rate.
Burton Bloom, 1970. Bit array + k hash functions. Extremely memory-efficient: 1% false positive rate ⇒ ~10 bits per element, regardless of element size. Used in Bitcoin SPV nodes, BigTable/HBase row-level filters, CDN cache-existence checks, browsers' malicious-URL lists. Cuckoo filters (2014) are a modern alternative that supports deletion.