Bloom Filter
Ein Bloom-Filter approximiert die Zugehörigkeit zu einer Menge mit k Hashfunktionen und einem Bit-Array und bietet Platzeffizienz zum Preis einer False-Positive-Rate.
Zweck
Platzsparende approximative Zugehörigkeitsabfragen für Caches und Datenbanken bereitstellen.
Mechanismus
Einfügen: Das Element wird mit k Funktionen gehasht und die entsprechenden Bits gesetzt. Abfrage: Sind alle k Bits 1, ist das Element wahrscheinlich vorhanden (False-Positive-Rate p≈(1-e^(-kn/m))^k). Falsch negative gibt es nie. Löschen unterstützt die Standardversion nicht.
Anwendungsfälle
- Cache-Filterung
- Optimierung von Datenbankabfragen
- Deduplizierung