it-swarm-es.com

¿De dónde vienen las constantes hash "mágicas" como 0x9e3779b9 y 0x9e3779b1?

En el código que trata con tablas hash, a menudo encuentro la constante 0x9e3779b9 o, a veces, 0x9e3779b1. Por ejemplo

hash = n * 0x9e3779b1 >>> 24

¿Por qué se usa este valor particular?

137
bkgs

0x9e3779b9 es la parte integral de la parte fraccional de la proporción áurea 0.61803398875 ... (sqrt (5) -1)/2, multiplicado por 2 ^ 32.

Por lo tanto, si φ = (sqrt (5) +1)/2 = 1.61803398875 es la proporción áurea, la función hash calcula la parte fraccional de n * φ, que tiene propiedades de dispersión de Niza. Para convencerse, solo cree un diagrama de dispersión de (n, n*c-FLOOR(n*c)) en su hoja de cálculo favorita, reemplazando c con φ, e, π, etc. Algunos problemas interesantes de la vida real al equivocarse se describen en https://lkml.org/lkml/ 2016/4/29/838 .

Este método a menudo se conoce como "Golden Ratio Hashing" o "Fibonacci Hashing" y fue popularizado por Donald Knuth (The Art of Computer Programming: Volume 3: Sorting and Searching). En términos teóricos numéricos, se reduce principalmente a la Conjetura de Steinhaus ( https://en.wikipedia.org/wiki/Three-gap_theorem ) y la simetría recursiva de las partes fraccionales de los múltiplos de Proporción Dorada φ.

Ocasionalmente, también puede ver 0x9e3779b1, que es el primo más cercano a 0x9e3779b9 (y parece ser un poco de "culto a la carga" ya que este no es un hash modular). Similar, 0x9e3779b97f4a7c15 y 0x9e3779b97f4a7c55 son los equivalentes de 64 bits de estos números.

220
32f

Las otras respuestas explican la intención detrás de esos números mágicos, que probablemente es lo que querías saber. Sin embargo, se podría decir que "de dónde vienen" es de malas prácticas de programación. Los números mágicos son malos y nunca deberían usarse. Las constantes como las mencionadas deben recibir nombres de variables descriptivas adecuadas, y tal vez incluso se deben agregar comentarios donde se definen. Entonces, cada aparición de los valores en el código debe estar en la forma de la variable nombrada. Cuando este sea el caso en los códigos en los que cumplió con esos valores, en primer lugar, su intención no le habría desconcertado.

ejemplo:

Mal ejemplo: utiliza números mágicos

hash = n * 0x9e3779b1

Mejor ejemplo: con comentarios y variables significativas

# Golden Ratio constant used for better hash scattering
# See https://softwareengineering.stackexchange.com/a/402543 
GOLDEN_RATIO = 0x9e3779b1
hash = n * GOLDEN_RATIO
30
isilanes
En el código que trata con tablas hash, a menudo encuentro la constante 0x9e3779b9 o, a veces, 0x9e3779b1

La otra respuesta explicaba correctamente por qué se usa este valor. Sin embargo, si a menudo encuentra esta constante, es posible que no se dé cuenta de que a menudo encuentra que el código es vulnerable a los ataques de inundación de hash.

Hay dos estrategias contra los ataques de inundación de hash:

  1. Use una función hash segura que tenga una semilla aleatoria secreta. Su función hash no tiene una semilla aleatoria secreta. Murmurhash3_32 tiene una semilla aleatoria secreta, pero tiene multicolisiones independientes de la semilla debido al pequeño estado interno. La mejor función hash que tiene una seguridad criptográfica cercana y un rendimiento casi aceptable es probablemente SipHash. Desafortunadamente, es lento, aunque no tan lento como SHA512, etc.

  2. Use una función hash que sea rápida de calcular (como la función hash que encontró o Murmurhash3_32), y convierta cada hash en la raíz de un árbol de búsqueda binario equilibrado. Por lo tanto, una tabla hash ordinaria encadenada por separado tiene cada depósito como una lista vinculada, que es lenta si muchos valores se combinan en el mismo depósito. Al convertirlo en un árbol de búsqueda binario equilibrado, como el árbol AVL o el árbol rojo-negro, aún tiene garantizado el peor rendimiento.

Mi opinión es que (2) es mejor porque SipHash es muy lento. Además, en el espacio del kernel del sistema operativo puede no haber suficiente entropía para crear una semilla aleatoria secreta al principio de la etapa de arranque, por lo que en el espacio del kernel es posible que no tenga la capacidad de crear números aleatorios al inicio.

Las tablas hash son ampliamente mal utilizadas. Es fácil detener muchos sistemas mediante el simple envío de muchos valores que se combinan en el mismo depósito.

5
juhist