Bloom filter
Set membership in a few bits per item.
Main article: Bloom filter simulator
Bloom's paper "Space/Time Trade-offs in Hash Coding with Allowable Errors" proposed a tiny structure that says, with certainty, "definitely not in the set" or "probably in the set". The trick: use a few hash functions to set bits in an array; check by checking if all those bits are set. False positives are tunable; false negatives are impossible.
Bit array of size m; k hash functions. Insert: set the k bits given by hashing the key. Lookup: check if all k bits are set. False-positive rate ≈ (1 − e^(−kn/m))^k. Optimal k = (m/n) ln 2.
The per-file filters of LSM-tree stores such as Bigtable, LevelDB, RocksDB, Cassandra and HBase, which check whether a key might be in a sorted file before reading it. Akamai's caches, which use one to skip caching objects requested only once. PostgreSQL's bloom index extension.
Bloom filters live in front of expensive lookups. The 1% false-positive cost is paid in vain disk reads; the 99% true-negative saves them. The structure exists because disk is slow.