Bloom-Filter
Probabilistische Datenstruktur für die Frage "ist das Element in der Menge?" — antwortet mit "vielleicht" oder "definitiv nein". Keine False Negatives, kontrollierbare False-Positive-Rate.
Burton Bloom, 1970. Bit-Array plus k Hashfunktionen. Extrem speichereffizient: 1 % False-Positive-Rate ⇒ ~10 Bit pro Element, unabhängig von der Elementgröße. Eingesetzt in Bitcoin-SPV-Knoten, BigTable/HBase-Zeilenfiltern, CDN-Cache-Existenzprüfungen und den Listen bösartiger URLs in Browsern. Cuckoo-Filter (2014) sind eine moderne Alternative, die auch Löschen unterstützt.