Nombre magique dans boost::hash_combine

Question

El boost::hash_combine La fonction modèle prend une référence à un hachage (appelé seed ) et un objet v . Selon le docs il combine seed avec le hachage de v par

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

Je peux voir que c'est déterministe. Je vois pourquoi on utilise un XOR.

Je parie que l'addition aide à mettre en correspondance des valeurs similaires très éloignées les unes des autres, de sorte que le sondage des tables de hachage ne tombe pas en panne, mais quelqu'un peut-il expliquer ce qu'est la constante magique ?

Answer 1

Le nombre magique est censé être constitué de 32 bits aléatoires, où chacun d'entre eux a une probabilité égale d'être 0 ou 1, et sans corrélation simple entre les bits. Une façon courante de trouver une chaîne de tels bits consiste à utiliser l'expansion binaire d'un nombre irrationnel ; dans ce cas, ce nombre est l'inverse du nombre d'or :

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

L'inclusion de ce nombre modifie donc "aléatoirement" chaque bit de la graine ; comme vous le dites, cela signifie que les valeurs consécutives seront très éloignées les unes des autres. L'inclusion des versions décalées de l'ancienne graine permet de s'assurer que, même si hash_value() a une gamme de valeurs assez réduite, les différences seront rapidement réparties sur tous les bits.

Answer 2

Jetez un coup d'œil à la Article du DDJ par Bob Jenkins de 1997 . La constante magique ("golden ratio") s'explique comme suit :

Le nombre d'or est vraiment une valeur arbitraire. Son but est d'éviter de faire correspondre tous les zéros à tous les zéros.