c++ - Número mágico en impulso:: hash_combine

algorithm boost

Question

La función boost::hash_combine template toma una referencia a un hash (llamado seed ) y un objeto v . De acuerdo con los docs , combina la 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?

Answer 1

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

Answer 2

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. Incluir las versiones hash_value() 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.