Sind Bloom-Filter tatsächlich schneller als Hashes, auch unter Berücksichtigung des Cache?

Bloom-Filter sehen wirklich gut aus, wenn man bedenkt, dass man in konstanter Zeit mit 99% iger Sicherheit feststellen kann, ob sich ein Int in einem Set befindet. Dies gilt jedoch auch für Hashes, mit dem einzigen Unterschied, dass Sie in einem Hash die meiste Zeit nur einmal auf den Speicher zugreifen. Mit Bloom-Filtern müssen Sie an weit entfernten Orten ca. 7-mal pro Anfrage darauf zugreifen , sodass Sie pro Anfrage mehrere Cache-Fehlschläge haben.

Vermisse ich etwas?

Es fehlt, wie die beiden Datenstrukturen mit Hash-Kollisionen umgehen. Die Bloom-Filter speichern nicht die tatsächlichen Werte, daher entspricht der erforderliche Speicherplatz der konstanten Größe des angegebenen Arrays. Wenn Sie stattdessen einen herkömmlichen Hash verwenden, wird versucht, alle von Ihnen angegebenen Werte zu speichern, sodass dieser mit der Zeit wächst.

Betrachten Sie eine vereinfachte Hash-Funktion (nur als Beispiel!) f(x) = x % 2. Nun Sie geben die folgenden Zahlen: 2, 3, 4, 5, 6, 7.

Standard-Hash: Die angegebenen Werte werden gehasht und es kommt zu vielen Kollisionen aufgrund von f(2) = f(4) = f(6) = 0und f(3) = f(5) = f(7) = 1. Der Hash speichert jedoch alle diese Werte und kann Ihnen mitteilen, dass diese 8nicht in ihm gespeichert sind. Wie macht es das? Es verfolgt Kollisionen und speichert alle Werte mit demselben Hash-Wert. Wenn Sie es abfragen, vergleicht es Ihre Abfrage zusätzlich. Lassen Sie uns also die Map nach 8: abfragen f(8) = 0, damit sie in einen Eimer schaut, in den wir bereits eingefügt haben, 2, 4, 6und 3 Vergleiche durchführen muss, um Ihnen mitzuteilen, dass dies 8nicht Teil der Eingabe war.

Bloom-Filter: Normalerweise wird jeder Eingangswert mit kverschiedenen Hash-Funktionen verglichen . Nehmen wir der Einfachheit halber an, wir verwenden nur die einzelne Hash-Funktion f. Wir brauchen dann ein Array mit 2 Werten und wenn wir auf die Eingabe stoßen 2, bedeutet dies, dass f(2) = 0wir den Array-Wert an der Position 0auf den Wert setzen 1. Das gleiche passiert für 4und 6. In ähnlicher Weise setzen die Eingänge 3, 5, 7jeweils die Array-Position 1auf einen Wert 1. Nun fragen wir ab, ob 8ein Teil der Eingabe war: f(8) = 0und das Array an der Position 0ist 1, so dass der Bloom-Filter fälschlicherweise behauptet, dass dies 8tatsächlich ein Teil der Eingabe war.

Um ein bisschen realistischer zu werden, nehmen wir an, dass wir eine zweite Hash-Funktion hinzufügen g(x) = x % 10. Damit wird der Eingangswert 2führt zu zwei Hash - Werten f(2) = 0und g(2) = 2und die beiden entsprechenden Array - Positionen gesetzt werden 1. Natürlich sollte das Array jetzt mindestens so groß sein 10. Aber wenn wir danach fragen 8, überprüfen wir das Array an der Position 8aufgrund von g(8) = 8, und diese Position bleibt bestehen 0. Aus diesem Grund verringern zusätzliche Hash-Funktionen die Anzahl der Fehlalarme.

Vergleich: Der Bloom-Filter verwendet kHash-Funktionen, was bedeutet, dass auf kzufällige Array-Positionen zugegriffen wird. Aber diese Zahl ist genau. Der Hash garantiert Ihnen stattdessen nur eine amortisierte konstante Zugriffszeit, kann jedoch abhängig von der Art Ihrer Hash-Funktion und der eingegebenen Daten aus der Generierung ausbleiben. So ist es in der Regel schneller, mit Ausnahme der de-generierten Fälle.

Sobald Sie jedoch eine Hash-Kollision haben, muss der Standard-Hash die Gleichheit der gespeicherten Werte mit dem Abfragewert vergleichen. Diese Gleichheitsprüfung kann beliebig teuer sein und wird bei einem Bloom-Filter niemals auftreten.

In Bezug auf den Platz ist der Bloom-Filter konstant, da nie mehr Speicher als das angegebene Array benötigt wird. Andererseits wächst der Hash dynamisch und kann viel größer werden, da kollidierte Werte nachverfolgt werden müssen.

Kompromiss: Jetzt, da Sie wissen, was billig ist und was nicht und unter welchen Umständen, sollten Sie in der Lage sein, den Kompromiss zu sehen. Bloom-Filter eignen sich hervorragend, wenn Sie sehr schnell erkennen möchten, dass ein Wert zuvor gesehen wurde, aber mit falsch positiven Ergebnissen leben können. Auf der anderen Seite können Sie die Hash-Map wählen, wenn Sie eine garantierte Korrektheit zu dem Preis wünschen, dass Sie Ihre Laufzeit nicht genau einschätzen können, aber gelegentlich degenerierte Fälle akzeptieren, die möglicherweise viel langsamer als der Durchschnitt sind.

Wenn Sie sich in einer Umgebung mit begrenztem Speicher befinden, möchten Sie möglicherweise Bloom-Filter für die Garantie der Speichernutzung bevorzugen.

Die Anwendungsfälle für Bloom-Filter und Hashes sind unterschiedlich und meist nicht zusammenhängend, sodass ein direkter Vergleich keinen Sinn ergibt. Außerdem hängt es von den technischen Details der Implementierungen ab, da es viele Möglichkeiten gibt, mit Hash-Kollisionen mit unterschiedlichen Kompromissen umzugehen.

Der Bloom-Filter kann mit angemessener Wahrscheinlichkeit, jedoch nicht exakt, mit geringem Speicherbedarf beantworten, ob sich ein Element in einer Menge für große Mengen befindet. Riesige Billionen von Elementen. Aber sie sind niemals genau. Sie können die Anzahl der Fehlalarme nur verringern, indem Sie mehr Speicher oder Hash-Funktionen verwenden.

Andererseits sind Hash-Tabellen genau, aber sie müssen den Satz speichern. Billionen von Elementen würden also Terrabytes an Speicher benötigen (und das sind nur amerikanische Billionen). Sie können auch zusätzliche Daten für jedes Element speichern, die Bloom-Filter nicht können.

Bloom-Filter werden daher verwendet, wenn Sie eine langsame Methode zum Abrufen von Daten für ein Mitglied (das das Abfragen von Servern, Lesen von Datenträgern usw. umfasst) eines großen Satzes (der nicht in den Arbeitsspeicher passt oder nicht auf den Client übertragen werden kann) verwenden oder so) und möchten vermeiden, dass die langsame Operation für Objekte ausgeführt wird, die sich nicht in der Gruppe befinden.