hash redis murmurhash

MurmurHash: ¿qué es eso?



redis (2)

He estado tratando de obtener un alto nivel de comprensión de lo que hace MurmurHash .

He leído una descripción básica pero todavía no he encontrado una buena explicación de cuándo usarla y por qué. Sé que es muy rápido, pero quiero saber un poco más.

Hice una question relacionada acerca de cómo podría encajar un UUID en un conjunto de bits de Redis, y alguien sugirió usar MurmurHash. Funciona, pero me gustaría entender los riesgos / beneficios.

Murmur es una familia de buenas funciones hash de propósito general, adecuadas para uso no criptográfico. Como declaró Austin Appleby, MurmurHash brinda los siguientes beneficios:

  • simple (en términos del número de instrucciones de ensamblaje generadas).
  • buena distribución (pasando pruebas chi-cuadrado para prácticamente todos los conjuntos de teclas y tamaños de cubo).
  • buen comportamiento de avalanche (sesgo máximo de 0.5%).
  • buena resistencia a la colisión (pasa la prueba de tortura frog.c de Bob Jenkin. No es posible colisionar con las teclas de 4 bytes, no hay diferenciales pequeños (de 1 a 7 bits)).
  • gran rendimiento en hardware Intel / AMD, buena compensación entre calidad de hash y consumo de CPU.

Ciertamente puedes usarlo para hash UUID (como cualquier otra función de hash avanzada: CityHash, Jenkins, Paul Hsieh''s, etc ...). Ahora, un conjunto de bits de Redis está limitado a 4 GB de bits (512 MB). Por lo tanto, debe reducir 128 bits de datos (UUID) a 32 bits (valor hash). Cualquiera que sea la calidad de la función hashing, habrá colisiones.

El uso de una función hash diseñada como Murmur maximizará la calidad de la distribución y minimizará el número de colisiones, pero no ofrece ninguna otra garantía.

Aquí hay algunos enlaces que comparan la calidad de las funciones hash de propósito general:

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/