hash - tabla - ¿Por qué son 5381 y 33 tan importantes en el algoritmo djb2?

resolucion de colisiones hash

Question

El algoritmo djb2 tiene una función hash para cadenas.

unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

¿Por qué son tan importantes 5381 y 33?

Answer 1

33 fue elegido porque:

1) Como se dijo anteriormente, la multiplicación es fácil de calcular usando shift y add.

2) Como puede ver en el cambio y agregar implementación, usar 33 hace dos copias de la mayoría de los bits de entrada en el acumulador de hash, y luego separa esos bits relativamente separados. Esto ayuda a producir buenas avalanchas. Usar un cambio más grande duplicaría menos bits, usar un cambio más pequeño mantendría las interacciones de bits más localizadas y haría que las interacciones tarden más en propagarse.

3) El desplazamiento de 5 es relativamente primo a 32 (el número de bits en el registro), lo que ayuda con el avalanchamiento. Si bien quedan suficientes caracteres en la cadena, cada bit de un byte de entrada eventualmente interactuará con cada bit de entrada precedente.

4) El cambio de 5 es una buena cantidad de cambio cuando se consideran datos de caracteres ASCII. Un carácter ASCII puede considerarse como un selector de tipo de caracteres de 4 bits y un selector de caracteres de tipo de 4 bits. Por ejemplo, todos los dígitos tienen 0x3 en los primeros 4 bits. Entonces un cambio de 8 bits haría que los bits con un cierto significado interactúen principalmente con otros bits que tienen el mismo significado. Un cambio de 4 bits o 2 bits produciría interacciones fuertes entre bits de ideas similares. El cambio de 5 bits hace que muchos de los cuatro bits de bajo orden de un personaje interactúen fuertemente con muchos de los 4 bits superiores en el mismo carácter.

Como se indicó en otra parte, la elección de 5381 no es demasiado importante y muchas otras opciones deberían funcionar también aquí.

Esta no es una función hash rápida, ya que procesa el ingreso de un carácter a la vez y no intenta usar el paralelismo de nivel de instrucción. Sin embargo, es fácil de escribir. La calidad de la salida dividida por la facilidad de escribir el código es probable que llegue a un punto óptimo.

En los procesadores modernos, la multiplicación es mucho más rápida de lo que era cuando se desarrolló este algoritmo y otros factores de multiplicación (p. Ej. 2 ^ 13 + 2 ^ 5 + 1) pueden tener un rendimiento similar, un rendimiento ligeramente mejor y ser ligeramente más fáciles de escribir.

Contrariamente a una respuesta anterior, una buena función hash no criptográfica no quiere producir una salida aleatoria. En cambio, dadas dos entradas que son casi idénticas, quiere producir salidas ampliamente diferentes. Si sus valores de entrada están distribuidos aleatoriamente, no necesita una buena función de hash, solo puede usar un conjunto arbitrario de bits de su entrada. Algunas de las funciones hash modernas (Jenkins 3, Murmur, probablemente CityHash) producen una mejor distribución de los resultados que las entradas aleatorias que son muy similares.

Answer 2

En 5381, Dan Bernstein (djb2) dice en este artículo :

[...] prácticamente cualquier buen multiplicador funciona. Creo que te preocupa el hecho de que 31c + d no cubre ningún rango razonable de valores hash si cyd están entre 0 y 255. Por eso, cuando descubrí la función 33 hash y comencé a usarla en mis compresores , Comencé con un valor hash de 5381. Creo que encontrará que esto funciona tan bien como un multiplicador 261.

Todo el hilo está here si estás interesado.

Ozan Yigit tiene una página sobre funciones hash que dice:

[...] la magia del número 33 (por qué funciona mejor que muchas otras constantes, primarias o no) nunca se ha explicado adecuadamente.

Answer 3

Esta función hash es similar a Linear Congruential Generator (LCG - una clase simple de funciones que generan una serie de números pseudo-aleatorios), que generalmente tiene la forma:

X = (a * X) + c; // "mod M", where M = 2^32 or 2^64 typically

Tenga en cuenta la similitud con la función hash djb2 ... a = 33, M = 2 ^ 32. Para que un LCG tenga un "período completo" (es decir, tan aleatorio como sea posible), debe tener ciertas propiedades:

• a-1 es divisible por todos los factores primos de M (a-1 es 32, lo que es divisible por 2, el único factor principal de 2 ^ 32)
• a-1 es un múltiplo de 4 si M es un múltiplo de 4 (sí y sí)

Además, se supone que c y M son relativamente primos (lo que será cierto para los valores impares de c ).

Como puede ver, esta función hash se asemeja a un buen LCG. Y cuando se trata de funciones hash, desea una que produzca una distribución "aleatoria" de valores hash dada un conjunto realista de cadenas de entrada.

En cuanto a por qué esta función hash es buena para las cadenas, creo que tiene un buen equilibrio entre ser extremadamente rápido, al tiempo que proporciona una distribución razonable de los valores hash. Pero he visto muchas otras funciones hash que afirman tener características de salida mucho mejores, pero que implican muchas más líneas de código. Por ejemplo, vea esta página sobre funciones hash

EDITAR: Esta buena respuesta explica por qué 33 y 5381 fueron elegidos por razones prácticas.

Answer 4

Tal vez porque 33 == 2^5 + 1 y muchos algoritmos de hashing usan 2^n + 1 como su multiplicador?

Gracias a Jerome Berger

Actualizar:

Esto parece estar confirmado por la versión actual del paquete de software djb2 originalmente provenía de: cdb

Las notas que he vinculado describen el corazón del algoritmo de hashing como h = ((h << 5) + h) ^ c para hacer hash ... x << 5 es una forma rápida de hardware para usar 2 ^ 5 como el multiplicador