Bloom filter
Probabilistisk datastruktur för "finns elementet i mängden?" — kan svara "kanske" eller "definitivt nej". Inga false negatives, kontrollerbar false positive-rate.
Burton Bloom, 1970. Bitarray + k hash-funktioner. Extremt minneskaffe: 1% false positive-rate ⇒ ~10 bitar per element, oavsett elementstorlek. Används i Bitcoin SPV-noder, BigTable/HBase row-level filter, CDN cache-existence checks, webbläsares malicious-URL-listor. Cuckoo filters (2014) är moderna alternativ som stöder borttagning.