Zuletzt aktualisiert: 2026-07-13

Bloomfilter-Dimensionierung

Ein Bloomfilter beantwortet kompakt eine einzige Frage: „Habe ich dieses Element wahrscheinlich schon gesehen?" Er speichert keine Schlüssel, sondern nur ein Bitarray und tauscht eine kleine, einstellbare Chance auf ein falsches Positiv gegen eine große Speicherersparnis. Zwei Zahlen bestimmen seine Form – wie viele Elemente Sie erwarten und wie oft Sie einen falschen Treffer tolerieren – und daraus folgen die optimale Länge des Bitarrays und die Hashzahl unmittelbar.

Die Formel

Für $n$ erwartete Elemente und eine Ziel-Falsch-Positiv-Rate $p$ hat das speicherminimale Bitarray die Länge

Die optimale Zahl der Hashfunktionen ist dann

gerundet auf die nächste ganze Zahl. Dabei ist $m$ die Bitzahl, $k$ die Zahl unabhängiger Hashfunktionen je Element und $\ln 2 \approx 0{,}693$. Da $p$ eine Wahrscheinlichkeit unter 1 ist, ist ihr natürlicher Logarithmus negativ, sodass beide Formeln positive Werte liefern.

Rechenbeispiel. Ein Filter für eine Million Elemente ($n = 1{,}000{,}000$) bei einem Ziel von 1 % ($p = 0{,}01$):

Eine Million Elemente bei 1 % kosten also rund 1,14 MiB Speicher und sieben Hashfunktionen – etwa 9,6 Bit pro Element, ein Wert, der bei dieser Genauigkeit für jede Elementzahl gilt.

Bits pro Element und die Genauigkeitsleiter

Da die Größenformel linear in $n$ ist, hängt der Speicherbedarf pro Element, $m / n = -\ln p / (\ln 2)^2$, nur von der Zielrate ab. Das macht ihn zu einem sauberen Maß für den Vergleich von Genauigkeitsbudgets.

Jede Zehnerpotenz weniger bei der Falsch-Positiv-Rate fügt etwa 4,8 Bit pro Element und rund drei Hashfunktionen hinzu. Der Speicher wächst nur linear, während die Fehlerrate geometrisch fällt – genau das macht Bloomfilter attraktiv.

Warum die Hashzahl zählt

Bei fester Arraygröße lassen zu wenige Hashfunktionen die Bits spärlich und leicht zufällig zu treffen, während zu viele das Array so dicht füllen, dass fast jedes Bit gesetzt ist. Der optimale Punkt setzt etwa die Hälfte der Bits und liegt bei $k = (m/n)\ln 2$. Da $k$ ganzzahlig sein muss, rundet der Rechner, und die tatsächliche Falsch-Positiv-Rate wird aus diesem gerundeten Wert neu berechnet:

Im Beispiel oben ergibt das gerundete $k = 7$ etwa 1,004 %, eine Spur über dem Ziel von 1 %, weil das ideale $k$ 6,64 statt einer ganzen Zahl war.

Was ein Bloomfilter kann und was nicht

Ein Bloomfilter erzeugt nie ein falsches Negativ: Sagt er, ein Element fehle, dann fehlt es wirklich. Der einzige Fehler ist ein falsches Positiv, dessen Rate dieser Rechner dimensioniert. Standardfilter unterstützen Einfügen und Abfragen, aber kein Löschen, weil Bits über Elemente geteilt werden – das Löschen der Bits eines Elements könnte andere beschädigen. Ist Löschen nötig, tauscht ein zählender Bloomfilter jedes Bit gegen einen kleinen Zähler zum Preis mehrfachen Speichers, und ein Cuckoo-Filter bietet Löschen bei vergleichbarer Größe.

Ein Vorbehalt: Ein Filter ist für ein festes $n$ dimensioniert. Fügen Sie viel mehr Elemente ein als geplant, sättigt sich das Array und treibt die Falsch-Positiv-Rate über das Ziel. Ist Wachstum wahrscheinlich, dimensionieren Sie von vornherein für die größere Zahl oder nutzen Sie ein skalierbares Design, das mehrere Filter verkettet.

Rundung in der Praxis

Die Bitzahl $m$ aus der Formel ist selten eine runde Zahl. Echte Implementierungen belegen ganze Maschinenwörter oder Speicherseiten und runden $m$ daher auf, was die erreichte Falsch-Positiv-Rate leicht unter das Ziel drückt – ein kleiner Bonus. Die hier gezeigte Größe ist das theoretische Minimum vor dieser Rundung.

Verwandte Berechnungen

Bloomfilter stützen sich auf Hashing, daher unterliegt die Chance, dass zwei Elemente denselben Hash teilen, derselben Geburtstags­mathematik – siehe den Hash-Kollisionswahrscheinlichkeit. Für Kennungen fester Länge wendet der UUID-Kollisionswahrscheinlichkeit-Rechner dieselbe Überlegung auf UUIDs an, und der Shannon-Entropie berechnen misst die Information, die ein Datensatz trägt.