Der Bloom-Filter tauschte einige falsche Antworten gegen einen winzigen Speicherbedarf ein

Wenn eine Menge von Elementen riesig ist, ist das Speichern jedes Schlüssels unmöglich, aber man muss trotzdem wissen, ob etwas darin enthalten ist. Blooms Beispiel war ein Wörterbuch mit 500.000 Wörtern, bei dem nur 10 % der Wörter teure Silbentrennungsregeln verwenden: Die sinnvolle Prüfung bestand darin, einen Festplattenzugriff zu vermeiden, aber das Wörterbuch war zu groß für fehlerfreies Hashing im verfügbaren Speicher.

Ein Bloom-Filter löst dies mit einem Bit-Array und mehreren Hash-Funktionen. Beim Hinzufügen eines Elements werden die Bits an diesen Positionen gesetzt, und beim Testen wird gefragt, ob sie alle gesetzt sind. Ist eines davon null, ist das Element definitiv nicht vorhanden, es gibt also keine falsch-negativen Antworten; sind alle gesetzt, könnte das Element in der Menge sein oder es könnte lediglich mit anderen Elementen kollidiert sein, was zu einem falsch-positiven Ergebnis führt.

Da der Fehler einseitig und abstimmbar ist, bleibt die Struktur klein und eliminiert dennoch die meisten unnötigen Festplattenlesevorgänge. Ein Hash-Bereich von nur 18 % der Größe, die ein fehlerfreier Hash benötigen würde, eliminierte 87 % der Festplattenzugriffe, und weniger als zehn Bits pro Element ergeben eine Falsch-Positiv-Rate von etwa 1 %.

Ein Bit-Array sagt „vielleicht“, niemals versehentlich „nein“

Falsch-positive Ergebnisse sind akzeptabel, wenn die Kosten nur eine zusätzliche Prüfung sind, aber ein falsches „nein“ würde Daten verlieren.

Ein Bit-Array mit einigen Hash-Funktionen speichert die Mitgliedschaft in wenigen Bits pro Element.

Es beseitigt die meisten teuren Festplatten- oder Netzwerkabfragen, ohne die tatsächliche Menge zu speichern.

Wenn eine kleine Wahrscheinlichkeit, „ja“ zu sagen, akzeptabel ist, ein falsches „nein“ jedoch nicht, dann akzeptiere bewusst den einseitigen Fehler; einige falsch-positive Ergebnisse zuzulassen ist oft die einzige Möglichkeit, eine riesige Menge in den Speicher zu bringen.

Bloom-Filter verbreiteten sich in Datenbanken, Caches, Rechtschreibprüfungen und im Netzwerk-Routing, um teure Abfragen zu vermeiden, und erscheinen in Systemen von PostgreSQL und Apache Cassandra bis hin zu Chromium und groß angelegtem Caching; der zugrunde liegende Trick, einseitige Fehler für Speicherplatz zu akzeptieren, ist heute ein Standardprimitive in Computersystemen.