Wie viele Hash-Funktionen benötigt mein Bloom-Filter?

Question

Wikipedia sagt:

Ein leerer Bloom-Filter ist ein Bit-Array von m Bits, die alle auf 0 gesetzt gibt auch verschiedene Hash-Funktionen definiert sein muss, k, von denen jede Karte oder Hashes einige Satzelement nach einem der das M-Array positioniert mit einer gleichmäßigen Zufallsverteilung.

Ich habe den Artikel gelesen, aber was ich nicht verstehe, ist, wie k bestimmt wird. Ist es eine Funktion der Tabellengröße?

Außerdem habe ich in Hashtabellen, die ich geschrieben habe, einen einfachen, aber effektiven Algorithmus verwendet, um automatisch die Hash-Größe zu vergrößern. Grundsätzlich, wenn mehr als 50% der Eimer in der Tabelle gefüllt waren, würde ich die Größe des Tisches verdoppeln. Ich vermute, dass Sie dies vielleicht noch mit einem Bloom-Filter tun möchten, um falsche Positive zu reduzieren. Richtig?

Answer 1

Wenn Sie weiter unten in der Wikipedia article about Bloom filters lesen, dann finden Sie einen Abschnitt Wahrscheinlichkeit von Fehlalarmen. In diesem Abschnitt wird erläutert, wie die Anzahl der Hash-Funktionen die Wahrscheinlichkeiten von Fehlalarmen beeinflusst, und Sie erhalten die Formel, um k aus dem gewünschten erwarteten Prob zu bestimmen. von falsch positiven.

---

Zitat von Wikipedia:

Offensichtlich ist die Wahrscheinlichkeit einer falsch Positiven nimmt ab, wenn M (die Anzahl von Bits in dem Array) zunimmt, und zunimmt, wenn n (die Anzahl von eingefügten Elementen) erhöht. Für eine gegebene m und n, der Wert von k (die Anzahl von Hash- Funktionen), die die Wahrscheinlichkeit minimiert ist

Answer 2

und in einem ordentlichen kleinen Tisch gelegt hat:

http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html

Answer 3

Gegeben:

• n: wie viele Elemente Sie in Ihrem Filter erwarten (z. 216,553)
• p: Ihre akzeptable falsch positive Rate {0..1} (z.B.0.01 → 1%)

wollen wir berechnen:

• m: die Anzahl der Bits in dem Bloom-Filter benötigt
• k: die Anzahl der Hash-Funktionen sollten wir anwenden

Die Formeln:

m = -n*ln(p)/(ln(2)^2)die Anzahl der Bits
k = m/n * ln(2)die Anzahl der Hash-Funktionen

In unserem Fall:

• m = -216553*ln(0.01)/(ln(2)^2) = 997263/0.48045 = 2,075,686 Bits (253 kB)
• k = m/n * ln(2) = 2075686/216553 * 0.693147 = 6.46 Hash-Funktionen (7 Hash-Funktionen)

Hinweis: Jeder in Public Domain freigegeben Code. Keine Zuordnung erforderlich.