Número mágico en boost :: hash_combine

La función de plantilla boost::hash_combine toma como referencia un hash (llamado seed) y un objeto v. De acuerdo con la docs, combina seed con el hash de v porNúmero mágico en boost :: hash_combine

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 de prueba no se rompan, pero ¿alguien puede explicar qué es la constante mágica?

Fuente

2011-02-09 Fred Foo

Teniendo en cuenta que en muchos equipos con un costo entero de girar alrededor de la misma como un cambio podría haber algún beneficio en convertir la expresión a: seed ^= hash_value(v) + 0x9e3779b9 + rotl(seed, 6) + rotr(seed, 2); –

117

El número mágico se supone que es 32 bits aleatorios, en los que cada uno es igualmente probable que sea 0 o 1, y con ninguna 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

por lo que incluir este número "al azar" 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 bastante pequeño de valores, las diferencias pronto se distribuirán en todos los bits.

Fuente

2011-02-09 18:32:39

Niza, que había leído que habían notado que funcionó bastante bien, pero didn' Sabía que venía de la proporción áurea :) –

¡Genial! Me gusta cuando la teoría de números de repente se vuelve útil :) –

@larsmans Me encanta el uso que le damos a 'repentinamente', ¡es muy apropiado! La teoría de los números es como "sí, eso 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 un pequeño número de cosas. – corsiKa

Tome un vistazo a la DDJ article by Bob Jenkins from 1997. La constante mágica ("proporción áurea") se explica de la siguiente manera:

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

Fuente

2011-02-09 18:47:34 NPE

Número mágico en boost :: hash_combine

Respuesta

Cuestiones relacionadas