Ein Bloom Filter ist eine probabilistische Datenstruktur, die verwendet wird, um festzustellen, ob ein Element zu einer Menge gehört oder nicht. Die Hauptmerkmale eines Bloom Filters sind seine Effizienz in Bezug auf Speicherplatz und Geschwindigkeit, jedoch mit einer gewissen Wahrscheinlichkeit für Falsch-Positiv-Ergebnisse. Das bedeutet, dass der Filter manchmal anzeigt, dass ein Element in der Menge ist, obwohl es tatsächlich nicht vorhanden ist.
Der Bloom Filter funktioniert, indem er mehrere Hash-Funktionen auf das Element anwendet und die resultierenden Hash-Werte verwendet, um Bits in einem Bit-Array zu setzen. Wenn man später überprüft, ob ein Element vorhanden ist, werden die gleichen Hash-Funktionen angewendet, und die entsprechenden Bits im Array werden überprüft. Wenn alle Bits auf 1 gesetzt sind, könnte das Element in der Menge sein; wenn eines oder mehrere Bits auf 0 sind, kann man sicher sagen, dass das Element nicht in der Menge ist. Die mathematische Notation zur Berechnung der Wahrscheinlichkeit eines Falsch-Positivs kann durch die Formel
ausgedrückt werden, wobei die Anzahl der Hash-Funktionen, die Anzahl der eingefügten Elemente und die Größe des Bit-Arrays ist.
Starte dein personalisiertes Lernelebnis mit acemate. Melde dich kostenlos an und finde Zusammenfassungen und Altklausuren für deine Universität.