Murmur est une famille de bonnes fonctions de hachage à usage général, adaptées à une utilisation non cryptographique. Comme l'a déclaré Austin Appleby, MurmurHash offre les avantages suivants :
- simple (en termes de nombre d'instructions d'assemblage générées).
- bonne distribution (réussite des tests du khi-carré pour pratiquement tous les jeux de clés et toutes les tailles de buckets.
- bon comportement en avalanche (biais max de 0,5 %).
- bonne résistance aux collisions (passe le test de torture frog.c de Bob Jenkin. Aucune collision possible pour les clés de 4 octets, pas de petits différentiels (1 à 7 bits)).
- excellentes performances sur le matériel Intel/AMD, bon compromis entre la qualité de hachage et la consommation du processeur.
Vous pouvez certainement l'utiliser pour hacher des UUID (comme toutes les autres fonctions de hachage avancées :CityHash, Jenkins, Paul Hsieh's, etc...). Désormais, un bitset Redis est limité à 4 Go de bits (512 Mo). 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 telle que Murmur maximisera la qualité de la distribution et minimisera le nombre de collisions, mais cela 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/
