Numéro magique dans boost :: hash_combine

94

La boost::hash_combinefonction de modèle prend une référence à un hachage (appelé seed) et à un objet v. Selon la documentation , il se combine seedavec le hachage de vby

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

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

Je parie que l'ajout aide à mapper des valeurs similaires largement les unes des autres afin que les tables de hachage ne se décomposent pas, mais quelqu'un peut-il expliquer quelle est la constante magique?

c++ algorithm boost hash magic-numbers Fred Foo
la source
Étant donné que sur de nombreux ordinateurs un coût de rotation entier à peu près identique à celui d'un décalage, il y aurait un avantage à convertir l'expression en: <code> seed ^ = hash_value (v) + 0x9e3779b9 + rotl (seed, 6) + rotr (seed, 2); </code>
John Yates

Réponses:

140

Le nombre magique est censé être 32 bits aléatoires, chacun étant également susceptible d'être 0 ou 1, et sans corrélation simple entre les bits. Une manière courante de trouver une chaîne de ces bits est d'utiliser le développement 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

Donc, inclure ce nombre "au hasard" change chaque bit de la graine; comme vous le dites, cela signifie que les valeurs consécutives seront très éloignées. L'inclusion des versions décalées de l'ancienne graine garantit que, même si elle hash_value()a une plage de valeurs assez petite, les différences seront bientôt réparties sur tous les bits.

Mike Seymour
la source
14
Cool! J'aime quand la théorie des nombres devient soudainement utile :)
Fred Foo
8
@larsmans J'adore votre utilisation de «soudainement» - c'est très approprié! La théorie des nombres est comme "ouais, c'est bien ... mais j'ai du vrai travail à faire, désolé" dans 99% des cas. Et puis, comme vous le dites, «soudainement», la théorie des nombres est super utile. Ce n'est pas comme un marteau où c'est plutôt utile pour un grand nombre de choses. Au lieu de cela, c'est comme un scalpel extrêmement utile pour un petit nombre de choses.
corsiKa
5
@SamKellett fonctionnerait encore mieux si vous utilisiez le nombre correct de parenthèses et que vous obteniez0x9e3779b97f4a7800
Barry
5
Comme le nombre à virgule flottante de Python n'a pas assez de précision, les ratios dorés 64 bits ci-dessus ne sont pas corrects. Le résultat réel devrait être 0x9e3779b97f4a7c15.
kennytm
1
@kennytm Vous ne voulez pas dire 0x9e3779b97f4a7c16? Je veux dire, c'est seulement 1 off.
bit2shift
25

Jetez un œil à l' article DDJ de Bob Jenkins de 1997 . La constante magique ("nombre d'or") est expliquée comme suit:

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

NPE
la source