Die hash-Funktionen zu verwenden, die in einem Bloom-filter

Habe ich die folgende Frage über die Wahl von hash-Funktionen für Bloom-Filter:

  • Welche Funktionen zu verwenden?

In fast jedem Dokument/Papier können Sie Lesen, dass die hash-Funktionen verwendet Bloom-filter sollte unabhängig und gleichmäßig verteilt.

Weiß ich, was damit gemeint ist (unabhängig und gleichverteilt), aber ich habe Mühe zu finden, eine argumentation oder Diskussion, die hash-Funktionen erfüllen diese Anforderungen und sind daher geeignet. In vielen der posts die ich gelesen habe, über Vorschläge für die Nutzung der FNV oder Murmur-hash-Funktion, aber nicht warum (oder zumindest ohne Beweis) Sie geeignet sind.

Vielen Dank im Voraus!

InformationsquelleAutor Torsten | 2012-08-14
  1. 15

    Ich fragte mich die gleiche Frage beim Aufbau eines Java-Bloom-filter-Bibliothek. Sehen die Github-readme für eine ausführliche Behandlung meiner Analyse von hash-Funktionen, für die Bloom-Filter.

    Schaute ich auf das problem aus zwei Perspektiven:

    • Wie schnell ist die Berechnung?
    • Wie einheitlich ist die Ausgabe Verteilung?

    Geschwindigkeit kann leicht gemessen werden durch benchmarks, die auf zufälligen Eingaben. Homogenität ist ein bisschen schwieriger und erfordert einige Statistiken. Mittels Chi-Quadrat-goodness-of-fit tests, die ich gemessen, wie ähnlich die Verteilung der hash-Werte ist auf eine gleichmäßige Verteilung.

    Das Ergebnis ist:

    • Verwenden Murmur3 für den besten trade-off zwischen Geschwindigkeit und Homogenität. Tun nicht Verwendung Murmur2, wie es ist, nicht einheitlich für Eingänge, die Veränderung in kleinen Schritten.
    • Verwenden kryptographische hash-Funktion wie SHA-256 für die beste Homogenität.
    • Gelten die Kirsch-Mitzenmacher-Optimierung nur compute-2 statt k hash-Funktionen (hash_i = hash1 + i x hash2).

    Wenn Ihre Implementierung unter Verwendung von Java würde ich empfehlen, mit unsere Bloom-filter hash-Bibliothek. Es ist gut dokumentiert und getestet. Für die details, einschließlich der Ergebnisse von benchmark-Tests für verschiedene hash-Funktion und Ihre unformity laut Chi-Quadrat-test finden Sie in der Github readme des repo.

    • Ich habe nicht gelesen werden Kirsch-Mitzenmacher-Optimierung gründlich, aber in das Papier hash_i = hash1 + i x hash2 % p, wo p eine Primzahl ist, hash1 und hash2 innerhalb des Bereichs von [0, p-1], und das bitset besteht aus k * p-bits.
    • Ist der E-Modul nur auf dem zweiten hash? Auch die Kirsch-Mitzenmacher-Optimierung hat 2 hashes des gleichen bits, sondern in diesem Fall eine 128 bit und das zweite ist 256 bits. Wird, die dazu führen, bias?
    InformationsquelleAutor DivineTraube
  2. 5

    Hash-Funktionen sollten Sie mit grafischen Beweis dafür, warum FNV wäre eine schlechte Wahl und warum Murmur2 oder eine Bob Jenkins' - Hashes wäre eine gute Wahl.

    InformationsquelleAutor Guy Gordon
  3. 0

    Ich denke, eine vernünftige Möglichkeit wäre, mehrere CRC-hashes. Ich gehe davon aus, dass, wenn Sie möchten mehrere n-bit-hash-Werte, dann für Polynome mit Boolean-Feld, Koeffizienten, gibt es mehrere prime Polynome vom Grad n+1. Aber ich weiß nicht, von einem Prozess für die Suche nach diesen Polynomen.

    Andere Möglichkeit wäre die Verwendung mehrerer modulo-hashes. Die Größe des Bloom Filter bit-array sein müsste, die maximale modulo-Wert. Aber ich denke, es funktioniert gut, der E-Modul-Werte werden müsste, Produkt von Primzahlen, die größer als 10, und relativ prim zu einander. Und der Bereich vom minimum zum maximum modulus-Wert müsste möglichst klein sein. Ich weiß nicht, einen Weg zu finden, solche Werte. Ich habe geschrieben einige open-source-C++ - code für die schnelle Berechnung der Reste: https://github.com/wkaras/C-plus-plus-intrusive-container-templates/blob/master/modulus_hash.h

    InformationsquelleAutor WaltK
Schreibe einen Kommentar