Número mágico en boost :: hash_combine

94

La boost::hash_combinefunción de plantilla toma una referencia a un hash (llamado seed) y un objeto v. Según los documentos , se combina seedcon el hash de vby

seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);

Puedo ver que esto es determinista. Veo por qué se usa un XOR.

Apuesto a que la adición ayuda a mapear valores similares ampliamente separados para que las tablas hash de prueba no se rompan, pero ¿alguien puede explicar cuál es la constante mágica?

c++ algorithm boost hash magic-numbers Fred Foo
fuente
Dado que en muchas computadoras un costo de rotación de enteros aproximadamente lo mismo que un cambio, habría algún beneficio al convertir la expresión a: <code> seed ^ = hash_value (v) + 0x9e3779b9 + rotl (seed, 6) + rotr (seed, 2); </code>
John Yates

Respuestas:

141

Se supone que el número mágico es de 32 bits aleatorios, donde es igualmente probable que cada uno sea 0 o 1, y sin una correlación simple entre los bits. Una forma común de encontrar una cadena de tales bits es usar la expansión binaria de un número irracional; en este caso, ese número es el recíproco de la proporción áurea:

phi = (1 + sqrt(5)) / 2
2^32 / phi = 0x9e3779b9

Entonces, incluir este número "aleatoriamente" cambia cada bit de la semilla; como dices, esto significa que los valores consecutivos estarán muy separados. La inclusión de las versiones modificadas de la semilla anterior asegura que, incluso si hash_value()tiene un rango de valores bastante pequeño, las diferencias pronto se extenderán entre todos los bits.

Mike Seymour
fuente
14
¡Frio! Me gusta cuando la teoría de números de repente se vuelve útil :)
Fred Foo
8
@larsmans Me encanta tu uso de 'de repente', ¡es muy apropiado! La teoría de números es como "sí, está bien ... pero tengo mucho trabajo que hacer, lo siento" en el 99% de los casos. Y luego, como dices, 'de repente', la teoría de números es súper súper útil. No es como un martillo donde es bastante útil para una gran cantidad de cosas. En cambio, es como un bisturí siendo extremadamente útil para una pequeña cantidad de cosas.
corsiKa
5
@SamKellett Funcionaría aún mejor si usara el número correcto de paréntesis y obtuviera0x9e3779b97f4a7800
Barry
5
Debido a que el número de punto flotante de Python no tiene suficiente precisión, las proporciones áureas de 64 bits anteriores no son correctas. El resultado real debería ser 0x9e3779b97f4a7c15.
kennytm
1
@kennytm ¿No te refieres 0x9e3779b97f4a7c16? Quiero decir, es solo 1 de descuento.
bit2shift
25

Eche un vistazo al artículo de DDJ de Bob Jenkins de 1997 . La constante mágica ("proporción áurea") se explica de la siguiente manera:

La proporción áurea realmente es un valor arbitrario. Su propósito es evitar la asignación de todos los ceros a todos los ceros.

NPE
fuente