Bloomfilter

Ein Bloomfilter speichert m Bits, anfangs alle null. Das Einfügen einer Zeichenkette setzt ihre k Hashpositionen auf eins. Eine Abfrage prüft dieselben Positionen: Ein Nullbit bedeutet sicher nicht enthalten; lauter Einsen bedeuten nur möglicherweise enthalten. Bei festen Parametern und ohne Löschungen können eingefügte Zeichenketten nicht falsch negativ werden. Der separate Lehrvergleich speichert die exakten Zeichenketten nur, um wirkliche Mitgliedschaft und falsch positive Antworten zu erkennen. Sein zusätzlicher Speicher gehört nicht zu den m Filterbits.

Ganze Zahlen m von 8 bis 1024 und k von 1 bis 12 wählen und den Filter anlegen. Eine Parameteränderung verwirft den aktiven Filter bis zum erneuten Anlegen. Zurücksetzen leert den Filter und behält die Eingabefelder. Zeichenketten umfassen 1–256 UTF-16-Codeeinheiten; höchstens 1024 verschiedene Zeichenketten bleiben gespeichert. Der Vergleich ist exakt und unterscheidet Groß- und Kleinschreibung. Es gibt weder Entfernen von Rand-Leerzeichen noch Unicode-Normalisierung. Leerzeichen zählen, viele Emoji belegen zwei Codeeinheiten, und zusammengesetzte oder zerlegte Akzente sind verschiedene Zeichenketten. Die letzte Zeichenkette erscheint mit JSON-Anführungszeichen und Escapezeichen, damit Leer- und Steuerzeichen erkennbar sind. Erneutes Einfügen desselben Eintrags verändert weder Bits noch Eintragszahl oder Abfragezähler.

Die Implementierung behält ihre FNV-1a-artige 32-Bit-Hashvariante über JavaScript-UTF-16-Codeeinheiten bei. Standard-FNV-1a verarbeitet stattdessen Oktette. Jede Einheit wird per XOR eingebracht, dann mit 16777619 modulo 2³² multipliziert. Die Startwerte sind 2166136261 und 0xdeadbeef; das zweite Ergebnis wird ungerade gemacht. Die tatsächlichen Positionen lauten (h₁ + i h₂) mod m für i = 0…k−1, ohne zusätzlichen 32-Bit-Überlauf vor dem Modulo m. Wiederholte Positionen sind zulässig: Ein ungerader Schritt garantiert bei beliebigem m keinen vollständigen Zyklus. Die Tabelle zeigt jede Position in zeitlicher Reihenfolge, einschließlich Wiederholungen. Ein bereits gesetztes Bit bleibt beim Einfügen gesetzt. Beide Basishashes stehen in den Details. Dies ist eine deterministische, nicht kryptografische Lehrimplementierung; unabhängige gleichverteilte Hashes werden nicht behauptet.

Die beobachtete FP-Quote ist die Zahl falsch positiver Antworten geteilt durch die Zahl der Abfragen tatsächlich nicht enthaltener Zeichenketten. Abfragen eingefügter Zeichenketten gehen in keinen der beiden Zähler ein. Jeder neue verschiedene Eintrag setzt die Zähler zurück, weil sich die Referenzmenge und gegebenenfalls die Bits ändern. Ohne Negativabfragen ist die Quote unbestimmt. Wiederholte Abfragen zählen als wiederholte Anfragen. Manuell gewählte Abfragen sind keine unabhängige Zufallsstichprobe; die Quote garantiert nichts für künftige Zeichenketten.

Die Details zeigen die klassische Näherung f ≈ (1 − exp(−kn/m))ᵏ für n verschiedene Einträge und ideal unabhängige, gleichverteilte Hashes. Sie ist nicht die exakte Quote dieses endlichen deterministischen Filters. Das Beispiel a…h fügt diese acht ASCII-Zeichenketten in den aktuellen Filter ein. Bei m = 8 und k = 1 belegen sie alle Bits; jede neue Zeichenkette liefert dann eine falsch positive Antwort. Für ein kleineres Beispiel nur a einfügen, dann i, a und b abfragen: i ist falsch positiv, a wirklich enthalten und b abwesend. Die beobachtete Quote beträgt 1/2, weil nur zwei Abfragen negativ sind.

Rohe Parameter und Textentwürfe, Einträge, Abfragezähler, letzte Operation und offene Details werden lokal gespeichert, bis zu 100000 Zeichen im serialisierten Zustand. Darüber bleibt die zuvor gespeicherte Kopie erhalten; ein Hinweis fordert zum vollständigen Export vor Neuladen oder Verlassen der Seite auf. App-interne Navigation erhält die laufende Sitzung. Ungültige Importe erhalten den aktuellen Filter. Alte gespeicherte Zustände bleiben lesbar. Zurücksetzen leert den Filter und erhält die Eingabeentwürfe. Löschung, Zählfiltervarianten, kryptografischer Schutz und Benchmarks sind nicht enthalten.

Quellen: Bloom (1970), Methode 2 und Gl. 1, Spiegel des Originalartikels; Kirsch und Mitzenmacher (2008), §§2 und 5.2; RFC 9923, FNV-Grundlagen.

Die letzte Abfrage oder Einfügung steht zuerst. Die markierten Bits zeigen die verwendeten Positionen. Hashpositionen öffnen die geordneten Vorher-/Nachherwerte; Modell und Hashes enthalten Idealnäherung und Basishashes. Die beobachtete Quote zählt nur Abfragen nicht enthaltener Zeichenketten; manuelle Abfragen sind keine Zufallsstichprobe.

Die Bits behalten eine gut lesbare feste Zellengröße. Das Raster passt sich der verfügbaren Breite an, bis zu 64 Spalten; kleine Filter behalten ihre natürliche Breite. Hohe Raster scrollen innerhalb ihres Bereichs. Orange Umrandungen markieren alle Positionen der letzten Operation.

Nur Eingabewerte bleiben in diesem Browser erhalten. Berechnete Ergebnisse und Versuchsverläufe werden nicht gespeichert.