DE 
EnglishStandard
Українська
Polski🌸 Bloom-Filter — Probabilistische Mengenzugehörigkeit
Fügen Sie Elemente über k Hashfunktionen zu einem Bit-Array hinzu und testen Sie die Zugehörigkeit. Bloom-Filter liefern nie falsch-negative, aber falsch-positive Ergebnisse — passen Sie Array-Größe und Hash-Anzahl an und beobachten Sie die Falsch-Positiv-Rate.
Über diese Simulation
Ein Bloom-Filter ist eine probabilistische Datenstruktur, die Zugehörigkeitsabfragen in O(1)-Zeit und O(m)-Speicherplatz beantwortet, wobei m die Bit-Array-Größe ist — weit kleiner, als die Elemente selbst zu speichern. Beim Einfügen eines Elements bilden k unabhängige Hashfunktionen es auf k Positionen in einem m-Bit-Array ab und setzen diese Bits auf 1. Zum Testen der Zugehörigkeit werden dieselben k Positionen geprüft: Ist eine 0, ist das Element definitiv nicht vorhanden; sind alle 1, ist es wahrscheinlich vorhanden. Bits werden nie gelöscht, sodass falsch-negative Ergebnisse unmöglich sind, aber Hash-Kollisionen können falsch-positive Ergebnisse erzeugen, deren Wahrscheinlichkeit durch (1 − e^(−kn/m))^k angenähert wird, wobei n die Anzahl der eingefügten Elemente ist.
Dieser Simulator lässt Sie Wörter eingeben und zu einer Live-Bit-Array-Visualisierung hinzufügen, die Zugehörigkeit abfragen, um falsch-positive Ergebnisse beim Füllen des Arrays zu beobachten, und die Array-Größe m sowie die Hash-Anzahl k über Schieberegler anpassen. Die theoretische Falsch-Positiv-Rate und die gemessene Rate über 2.000 zufällige Testabfragen werden in Echtzeit aktualisiert, sodass der Kompromiss zwischen Speicherplatz und Genauigkeit sofort sichtbar wird.
Häufig gestellte Fragen
Warum kann ein Bloom-Filter nie ein falsch-negatives Ergebnis liefern?
Beim Einfügen eines Elements werden alle k gehashten Bit-Positionen auf 1 gesetzt und nie wieder gelöscht. Testet man daher ein Element, das tatsächlich eingefügt wurde, sind alle k Bits gesetzt, und der Filter meldet korrekt „möglicherweise in der Menge“. Ein falsch-negatives Ergebnis würde erfordern, dass ein Bit wieder auf 0 zurückfällt — das geschieht nie.
Wie lautet die Formel für die Falsch-Positiv-Wahrscheinlichkeit?
Nach dem Einfügen von n Elementen in ein m-Bit-Array mit k Hashfunktionen ist der Anteil noch auf 0 stehender Bits ungefähr e^(-kn/m), sodass die Wahrscheinlichkeit, dass alle k Positionen für ein Nicht-Element auf 1 stehen, (1 - e^(-kn/m))^k beträgt. Zum Beispiel liegt bei m = 64, k = 3 und n = 10 Elementen die Falsch-Positiv-Rate bei etwa 5 %.
Wie wählt man die optimale Anzahl von Hashfunktionen k?
Der Wert k = (m/n) × ln 2 minimiert die Falsch-Positiv-Rate für gegebenes m und n. Zu wenige Hashfunktionen lassen viele Bits ungesetzt und verringern die Trennschärfe; zu viele füllen das Array schnell und erhöhen Kollisionen. Für eine angestrebte Fehlerrate von 1 % beträgt die optimale Array-Größe etwa 9,6 Bit pro eingefügtem Element.
Warum kann man Elemente nicht aus einem Standard-Bloom-Filter löschen?
Das Löschen eines Elements würde erfordern, seine k Bit-Positionen zurückzusetzen, aber diese Bits könnten auch von anderen eingefügten Elementen gesetzt worden sein, sodass das Löschen stillschweigend falsch-negative Ergebnisse für diese Elemente einführen würde. Ein Counting-Bloom-Filter ersetzt jedes Bit durch einen kleinen Zähler, der beim Einfügen erhöht und beim Löschen verringert wird, um sicheres Löschen auf Kosten von mehr Speicher zu ermöglichen.