Eine platzsparende probabilistische Datenstruktur für approximative Mengenmitgliedschafts-Abfragen, die Falsch-Positive liefern kann, niemals jedoch Falsch-Negative; sie verwendet mehrere Hash-Funktionen, die Bits in einem Bitarray fester Größe setzen.

Prinzip

Mehrere unabhängige Hash-Funktionen werden verwendet, um jedes Element auf mehrere Positionen im Bitarray abzubilden; die Mitgliedschaft wird durch Überprüfung dieser Bits getestet: Kollisionen erzeugen Falsch-Positive, ein gesetztes Null-Bit garantiert Nicht-Mitgliedschaft.

Demonstration

Eine Rechtschreibprüfung speichert ein großes Wörterbuch in einem Bloom-Filter; bei Abfrage eines Wortes werden die zugehörigen Bits geprüft. Ist ein Bit null, ist das Wort definitiv nicht vorhanden; sind alle Bits eins, ist es wahrscheinlich vorhanden und eine langsamere exakte Überprüfung wird durchgeführt.

Fehlanwendung

Einen Standard-Bloom-Filter dort einzusetzen, wo Löschungen erforderlich sind, ohne eine zählende Variante zu verwenden, oder einen Null-Falsch-Positiv-Rate zu erwarten und auf sekundäre Verifikation zu verzichten; beides führt zu falschen Ergebnissen.

Konsequenz

Sehr speichereffiziente Mitgliedschaftstests mit einstellbarer Falsch-Positiv-Wahrscheinlichkeit und minimaler CPU-Belastung pro Abfrage, was Streaming- und verteilte Anwendungen ermöglicht, Kandidaten günstig vorzufiltern, zulasten gelegentlicher weiterer Prüfungen.

Umkehrung

Eine exakte Hashtabelle, die jedes Element explizit speichert, niemals Falsch-Positive liefert, aber deutlich mehr Speicher benötigt und eventuell höhere Kosten pro Operation verursacht.

Abgrenzung

Speichert keine Elemente und erlaubt keine zuverlässige Auflistung; liefert keine exakten Zählungen (außer bei zählenden Erweiterungen); die Falsch-Positiv-Rate steigt mit der Sättigung und wird durch Anzahl der Hashes, Array-Größe und Insert-Anzahl bestimmt.

Semantische Spannung

Probabilistische, approximative Mitgliedschaft (Bloom-Filter) versus exakte Mitgliedschaftsstrukturen (Hash-Sets): Beide beantworten 'Ist x in S?', tauschen jedoch Platz gegen Gewissheit unterschiedlich ein.

Synthese

Ein kompakter probabilistischer Filter, der einen kontrollierten Satz von Falsch-Positiven gegen erhebliche Platzeinsparungen eintauscht, indem er Mitgliedschaft als mehrere gehashte Bitpositionen in einem Bitarray fester Größe repräsentiert; geeignet, wenn gelegentliche Zusatzprüfungen akzeptabel sind.