Murmur è una famiglia di buone funzioni di hashing per uso generale, adatte per l'uso non crittografico. Come affermato da Austin Appleby, MurmurHash offre i seguenti vantaggi:
- semplice (in termini di numero di istruzioni di montaggio generate).
- buona distribuzione (superamento dei test del chi quadrato per praticamente tutti i keyset e le dimensioni dei bucket.
- buon comportamento in valanga (inclinazione massima dello 0,5%).
- buona resistenza alle collisioni (supera il test di tortura frog.c di Bob Jenkin. Nessuna collisione possibile per chiavi a 4 byte, nessun piccolo differenziale (da 1 a 7 bit).
- ottime prestazioni su hardware Intel/AMD, buon compromesso tra qualità hash e consumo di CPU.
Puoi sicuramente usarlo per eseguire l'hashing degli UUID (come qualsiasi altra funzione di hashing avanzata:CityHash, Jenkins, Paul Hsieh's, ecc ...). Ora, un bitset Redis è limitato a 4 GB di bit (512 MB). Quindi è necessario ridurre 128 bit di dati (UUID) a 32 bit (valore hash). Qualunque sia la qualità della funzione di hashing, ci saranno delle collisioni.
L'utilizzo di una funzione hash ingegnerizzata come Murmur massimizzerà la qualità della distribuzione e minimizzerà il numero di collisioni, ma non offre altre garanzie.
Ecco alcuni link che confrontano la qualità delle funzioni hash generiche:
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/
