Murmur est une famille de bonnes fonctions de hachage à usage général, adaptées à un usage non cryptographique. Comme l'indique Austin Appleby, MurmurHash offre les avantages suivants :
- simple (en termes de nombre d'instructions d'assemblage générées).
- bonne distribution (tests du chi carré réussis pour pratiquement tous les jeux de clés et toutes les tailles de godets).
- bon avalanche (biais maximal de 0,5 %).
- bonne résistance aux collisions (réussit le test de torture frog.c de Bob Jenkin). Aucune collision possible pour des clés de 4 octets, pas de petites différences (de 1 à 7 bits)).
- excellentes performances sur le matériel Intel/AMD, bon compromis entre la qualité du hachage et la consommation de l'unité centrale.
Vous pouvez certainement l'utiliser pour hacher les UUID (comme toute autre fonction de hachage avancée) : CityHash, Jenkins, Paul Hsieh, etc ...). Or, un jeu de bits Redis est limité à 4 GB bits (512 MB). Vous devez donc réduire 128 bits de données (UUID) à 32 bits (valeur hachée). Quelle que soit la qualité de la fonction de hachage, il y aura des collisions.
L'utilisation d'une fonction de hachage technique comme Murmur maximisera la qualité de la distribution et minimisera le nombre de collisions, mais elle n'offre aucune autre garantie.
Voici quelques liens comparant la qualité des fonctions de hachage à usage général :
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/
