Pregunta Número mágico en impulso :: hash_combine


los boost::hash_combine la función de plantilla toma una referencia a un hash (llamado seed) y un objeto v. De acuerdo con la documentos, combina seed con el hash de v por

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 los valores similares ampliamente para que las tablas de prueba no se rompan, pero ¿alguien puede explicar qué es la constante mágica?


76
2018-02-09 18:14


origen


Respuestas:


Se supone que el número mágico es de 32 bits aleatorios, donde cada uno tiene la misma probabilidad de ser 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 bastante pequeño de valores, las diferencias pronto se distribuirán en todos los bits.


118
2018-02-09 18:32



Eche un vistazo a la DDJ artículo 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 asignar todos los ceros a todos los ceros.


20
2018-02-09 18:47