Hash für Bloom-Filter < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Ich möchte einen Bloom-Filter implementieren. Dazu benötigt man k unabhängige und gleichverteilte Hashfunktionen, welche jeweils ein Eingangselement auf einen Bereich 0...m-1 gleichverteilt abbilden.
Angenommen m ist 2048 und mein erster Hash produziert 256-Bit Werte (also Werte von 0 bis 2^256-1).
Frage 1:
Da das Resultat des Hashs gleichverteilt ist, kann ich für eine Abbildung des Hashergebnisses auf 0...2047 einfach das Resultat des Hashs mod 2048 nehmen (also aus Implementierungssicht die unteren 11 Bit des 256-Bit Hashs), da diese auch gleichverteilt sein sollten?
Frage 2:
Da das Hashresultat gleichverteilt ist, könnte ich mehrere disjunkte Bereiche desselben Hashresultats nehmen (z.B. die schon angesprochenen unteren 11 Bit und dann noch z.B. die oberen 11 Bit des 256-Bit Hashs), um mehrere unabhängige Hashergebnisse für den Bloom-Filter zu haben? Sind also sich nicht überschneidende Teile desselben Hashswertes unabhängig und gleichverteilt, wenn das Hashresultat als Ganzes gleichverteilt ist?
Vielleicht hat ja jemand ein paar Gedanken dazu. Auch über Anregungen für konkrete, möglichst wenig komplexe Hashalgorithmen, welche den Anforderungen für Bloom-Filter genügen, würde ich mich freuen.
Danke!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:22 Fr 04.05.2018 | | Autor: | felixf |
Moin
> Ich möchte einen Bloom-Filter implementieren. Dazu
> benötigt man k unabhängige und gleichverteilte
> Hashfunktionen, welche jeweils ein Eingangselement auf
> einen Bereich 0...m-1 gleichverteilt abbilden.
>
> Angenommen m ist 2048 und mein erster Hash produziert
> 256-Bit Werte (also Werte von 0 bis 2^256-1).
>
> Frage 1:
> Da das Resultat des Hashs gleichverteilt ist, kann ich
> für eine Abbildung des Hashergebnisses auf 0...2047
> einfach das Resultat des Hashs mod 2048 nehmen (also aus
> Implementierungssicht die unteren 11 Bit des 256-Bit
> Hashs), da diese auch gleichverteilt sein sollten?
Genau.
(Das geht allerdings nur, wenn $m$ ein Teiler von [mm] $2^{256}$ [/mm] ist. Ansonsten ist der Rest nicht wirklich gleichverteilt.)
> Frage 2:
> Da das Hashresultat gleichverteilt ist, könnte ich
> mehrere disjunkte Bereiche desselben Hashresultats nehmen
> (z.B. die schon angesprochenen unteren 11 Bit und dann noch
> z.B. die oberen 11 Bit des 256-Bit Hashs), um mehrere
> unabhängige Hashergebnisse für den Bloom-Filter zu haben?
Ja. Also zumindest dann, wenn die Hash-Funktion gut genug ist 
Bei kryptographischen Hash-Funktionen ist das (eigentlich) kein Problem. Die sind allerdings im Allgemeinen recht langsam, im Vergleich zu anderen (effizienten) Hash-Funktionen (etwa murmur, fnv, HashMix; siehe auch https://llimllib.github.io/bloomfilter-tutorial/).
> Sind also sich nicht überschneidende Teile desselben
> Hashswertes unabhängig und gleichverteilt, wenn das
> Hashresultat als Ganzes gleichverteilt ist?
Wenn das Hashresultat gleichverteilt ist, ist das immer so.
> Vielleicht hat ja jemand ein paar Gedanken dazu. Auch über
> Anregungen für konkrete, möglichst wenig komplexe
> Hashalgorithmen, welche den Anforderungen für Bloom-Filter
> genügen, würde ich mich freuen.
Siehe oben bzw. https://llimllib.github.io/bloomfilter-tutorial/. Ansonsten siehe auch hier: https://www.jasondavies.com/bloomfilter/ und hier: https://willwhim.wpengine.com/2011/09/03/producing-n-hash-functions-by-hashing-only-once/
LG Felix
|
|
|
| |
|
Hallo Felix,
danke für deine Antwort. Irgendwie ahnt man im Bereich der Stochastik meist schon, dass es so sein könnte, wie man denkt, aber manchmal gibt es da doch Überraschungen, daher danke für die Bestätigung und die zusätzlichen Links.
Einen kryptographischen Hash will ich nicht verwenden, da meine Implementierung möglichst schnell sein soll. In der Praxis wird es wohl auch mit einer nicht perfekten Gleichverteilung ausreichend gut funktionieren.
Viele Grüße.
|
|
|
|
