Wie bekomme ich eine Familie von unabhängigen universellen Hash-Funktionen?

Ich versuche, den Hyperloglog-Zählalgorithmus mit stochastischer Mittelwertbildung zu implementieren. Um dies zu tun, brauche ich viele unabhängige universelle Hash-Funktionen, um Elemente in verschiedenen Teilströmen zu hashen.Wie bekomme ich eine Familie von unabhängigen universellen Hash-Funktionen?

Ich habe festgestellt, dass es nur ein paar Hash-Funktionen in hashlib gibt und es scheint keine Möglichkeit für mich, einen Samen oder etwas zu bieten? Ich denke mit verschiedenen Salzen für verschiedene Teilströme.

Quelle

2016-04-20 Louis Kuang

Ich bin kein Experte, aber da es geht um Kollisionen sein, trotzdem kann man nicht nur die Post-Hashing salzen, dh zum Hash selbst? Nicht sicher, was Sie mit "unabhängig" meinen, was die eigentliche Anforderung/Erwartung ist. – unwind

@unwind Wenn ich Salz verwenden würde, welche Bibliotheksfunktionen sollte ich verwenden, weil ich keine finden konnte. –

Es tut uns leid, Bibliothek Empfehlungen sind Off-Topic auf Stack Overflow. Aber wie auch immer ... die hashlib-Funktionen sind [kryptografische Hash-Funktionen] (https://en.wikipedia.org/wiki/Cryptographic_hash_function), sie können verwendet werden, um Hash-Tabellen usw. zu erstellen, aber sie sind relativ langsam. Vielleicht könnten Sie etwas mit Pythons eingebauter 'hash()' -Funktion tun, kombiniert mit der 'h (a, b, x) = Formel (a * x + b)% p% m' aus dem Wikipedia-Artikel zu [universal hashing ] (https://en.wikipedia.org/wiki/Universal_hashing#Hashing_integers). –

Wahrscheinlich brauchen Sie keine anderen Hash-Funktionen. Eine gängige Lösung für dieses Problem besteht darin, nur einen Teil des Hashs zum Berechnen der HyperLogLog-Rho-Statistik und den anderen Teil zum Auswählen des Teilstroms zu verwenden. Wenn Sie eine gute Hash-Funktion verwenden (z. B. murmur3), verhält es sich tatsächlich wie mehrere unabhängige.

Siehe „stochastische Lungs“ Abschnitt hier für eine Erklärung dafür: https://research.neustar.biz/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/

Quelle

2016-04-20 11:35:14 OronNavon

Python hat jedoch keine 'murmur3'-Implementierung eingebaut; vielleicht verwenden Sie einfach eine kryptografische Hash-Funktion wie 'md5', die 128 Bits auf einmal liefert. –

Guter Punkt, obwohl, wenn Sie nicht eingeschränkt sind, würde ich fortfahren und eine externe murmur3 Implementierung konsumieren. In jedem Fall müssen Sie sicherstellen, dass Ihre Hash-Funktion Ihren Geschwindigkeitsanforderungen entspricht (beachten Sie, dass kryptografische Hash-Funktionen langsam sind), sowie die Hash-Länge-Anforderungen (mindestens 64 Bit. 128 ist Overkill, aber Sie haben nicht um alle Bits zu benutzen). – OronNavon

Wie bekomme ich eine Familie von unabhängigen universellen Hash-Funktionen?

Antwort

Verwandte Themen