Murmur ist eine Familie von guten Allzweck-Hashing-Funktionen, die für nicht-kryptographische Verwendung geeignet sind. Wie von Austin Appleby angegeben, bietet MurmurHash die folgenden Vorteile:
- einfach (in Bezug auf die Anzahl der generierten Montageanleitungen).
- Gute Verteilung (Bestehen von Chi-Quadrat-Tests für praktisch alle Keysets und Bucket-Größen.
- gutes Lawinenverhalten (maximale Abweichung von 0,5 %).
- Gute Kollisionsresistenz (besteht Bob Jenkin's frog.c Torture-Test. Keine Kollisionen möglich für 4-Byte-Schlüssel, keine kleinen (1- bis 7-Bit) Differenzen).
- großartige Leistung auf Intel/AMD-Hardware, guter Kompromiss zwischen Hash-Qualität und CPU-Verbrauch.
Sie können es sicherlich verwenden, um UUIDs zu hashen (wie alle anderen erweiterten Hash-Funktionen:CityHash, Jenkins, Paul Hsieh's usw.). Jetzt ist ein Redis-Bitset auf 4 GB Bits (512 MB) begrenzt. Sie müssen also 128 Datenbits (UUID) auf 32 Bits (gehashter Wert) reduzieren. Ungeachtet der Qualität der Hash-Funktion wird es Kollisionen geben.
Die Verwendung einer konstruierten Hash-Funktion wie Murmur maximiert die Qualität der Verteilung und minimiert die Anzahl der Kollisionen, bietet aber 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/
