MurmurHash - was ist das?

75

Ich habe versucht, ein umfassendes Verständnis dafür zu bekommen, was MurmurHash tut.

Ich habe eine grundlegende Beschreibung gelesen, aber noch keine gute Erklärung gefunden, wann und warum ich sie verwenden soll. Ich weiß, dass es sehr schnell ist, möchte aber ein bisschen mehr wissen.

Ich stellte eine verwandte Frage, wie ich eine UUID in ein Redis-Bitset einpassen könnte, und jemand schlug vor, MurmurHash zu verwenden. Es funktioniert, aber ich möchte die Risiken / Vorteile verstehen.

hash redis murmurhash Samenkopf
quelle

Antworten:

113

Murmur ist eine Familie guter Allzweck-Hashing-Funktionen, die für die nicht kryptografische Verwendung geeignet sind. Wie von Austin Appleby angegeben, bietet MurmurHash die folgenden Vorteile:

  • einfach (in Bezug auf die Anzahl der generierten Montageanweisungen).
  • Gute Verteilung (Bestehen von Chi-Quadrat-Tests für praktisch alle Keysets und Bucket-Größen.
  • gutes Lawinenverhalten (maximale Vorspannung von 0,5%).
  • Gute Kollisionsbeständigkeit (besteht Bob Jenkins frog.c-Foltertest. Keine Kollisionen für 4-Byte-Schlüssel möglich, keine kleinen (1- bis 7-Bit-) Differentiale).
  • Hervorragende Leistung auf Intel / AMD-Hardware, guter Kompromiss zwischen Hash-Qualität und CPU-Verbrauch.

Sie können es sicherlich zum Hashing von UUIDs verwenden (wie alle anderen erweiterten Hashing-Funktionen: CityHash, Jenkins, Paul Hsiehs usw.). Jetzt ist ein Redis-Bitset auf 4 GB Bits (512 MB) begrenzt. Sie müssen also 128 Bit Daten (UUID) auf 32 Bit (Hash-Wert) reduzieren. Unabhängig von der Qualität der Hashing-Funktion kommt es zu Kollisionen.

Die Verwendung einer ausgereiften Hash-Funktion wie Murmur maximiert die Qualität der Verteilung und minimiert die Anzahl der Kollisionen, bietet jedoch keine andere Garantie.

Hier sind einige Links, die die Qualität von Allzweck-Hash-Funktionen vergleichen:

http://www.azillionmonkeys.com/qed/hash.html

http://www.strchr.com/hash_functions

http://blog.aggregateknowledge.com/2011/12/05/choosing-a-good-hash-function-part-1/

http://blog.aggregateknowledge.com/2011/12/29/choosing-a-good-hash-function-part-2/

http://blog.aggregateknowledge.com/2012/02/02/choosing-a-good-hash-function-part-3/

Didier Spezia
quelle
Ich habe versucht, MurmurHash zum Hashing meiner UUIDs zu verwenden, aber die Hash-Funktion gibt für einige UUIDs negative IDs zurück. Weiß jemand, wie man das umgeht?
Seedhead
10
Die Ausgabe der C-Implementierung von MurmurHash ist eine vorzeichenlose Ganzzahl ... sie kann nicht negativ sein. Vielleicht verwenden Sie Java? In Java müssen Sie UND mit 0xffffffffL (siehe stackoverflow.com/questions/9578639/… )
Didier Spezia
Kennen Sie eine Analyse dieses Hashs? Ist es universell? Ist es 2-weise-unabhängig usw.?
Thomas Ahle
@DidierSpezia Warum ist Math.abs () nicht gut genug? Das Ergebnis wäre auch gut verteilt, da die ursprünglichen IDs, ob negativ oder nicht, bereits gleichmäßig verteilt sind.
Flügel
Math.abs () mag zwar gut genug sein ... aber Sie verlieren 1 Bit, sodass die Wahrscheinlichkeit einer Kollision mit 2 multipliziert wird (dh Ihr Hash liegt bei 31 Bit anstelle von 32).
Didier Spezia
-2

MurmurHash kann ein negativer Wert sein ， ursprüngliches Wertbit UND gegen 0x7fffffff。das ist der Wert & 0x7fffffff. Wenn die Eingabe positiv ist, wird der ursprüngliche Wert zurückgegeben. Wenn die Eingangsnummer negativ ist, ist der zurückgegebene positive Wert das ursprüngliche Wertbit UND gegen 0x7fffffff, was nicht der absolute Wert ist. Hinweis: Der Rückgabewert von MurmurHash kann nicht auf die Länge festgelegt werden.

Daemon
quelle