Nombre magique dans boost::hash_combine

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

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

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

Je parie que les plus aide à la cartographie des valeurs similaires largement séparées, afin de sonder les tables de hachage ne se décomposent pas, mais quelqu'un peut m'expliquer ce que la magie de la constante est?

  • Étant donné que sur de nombreux ordinateurs un entier tourner coûtent environ le même prix qu'un changement aurait-il un quelconque avantage dans la conversion de l'expression: <code> la graine ^= hash_value(v) + 0x9e3779b9 + rotl(semences, 6) + rotr(semences, 2); </code>
InformationsquelleAutor Fred Foo | 2011-02-09
  1. 126

    Le nombre magique est censé être 32 bits aléatoires, où chacun est tout aussi susceptibles d'être égal à 0 ou 1, et avec pas de corrélation simple entre les bits. Une façon courante de trouver une chaîne de tels morceaux est d'utiliser le binaire de l'expansion 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 y compris ce nombre de façon "aléatoire" des changements de chaque bit de la semence; comme vous le dites, cela signifie que les valeurs consécutives seront éloignés. Y compris la nouvelle versions de la semence vieille de permet de s'assurer que, même si hash_value() a une assez petite plage de valeurs, les différences vont bientôt se propager à travers tous les bits.

    • Nice, j'avais lu qu'ils avaient remarqué cela a fonctionné assez bien, mais ne savait pas c'est venu du nombre d'or 🙂
    • Cool! J'aime quand la théorie devient soudainement utile 🙂
    • J'aime beaucoup ton utilisation de "subitement" - il est très approprié! La théorie des nombres est comme "ouais, c'est gentil... mais j'ai un réel travail à faire, désolé" dans 99% des cas. Et puis, comme vous le dites, "subitement", la théorie des nombres est super super utile. Ce n'est pas comme un marteau où il est plutôt utile pour un grand nombre de choses. Au lieu de cela, c'est comme un scalpel être très utile pour un petit nombre de choses.
    • Ainsi, le nombre magique doit être différent selon sizeof(size_t)?
    • ce serait plus logique. Cette seule ligne: python -c "import math; print hex(int(2**64 / (1 + math.sqrt(5)) / 2))" produit 0x278dde6e5fd29e00 pour moi. J'attends qui fonctionne assez bien pour quand size_t est 64-bits.
    • Serait encore mieux si vous avez utilisé le bon nombre de parenthèses et a obtenu 0x9e3779b97f4a7800
    • haha, doh! la grande tache
    • Parce que Python est nombre à virgule flottante n'a pas assez de précision, la version 64 bits d'or ratios ci-dessus ne sont pas correctes. Le résultat devrait être 0x9e3779b97f4a7c15.
    • En parlant de qui, cela suppose que le nombre d'or est ce qu'on appelle un nombre normal - ça l'est probablement.
    • Ne pas vous le dire 0x9e3779b97f4a7c16? Je veux dire, il est à seulement 1 arrêt.
    • Cela dépend si vous voulez arrondir vers le haut ou ronde.
    • cette valeur est arrondie vers le bas par la coulée. Quelle formule avez-vous réellement l'utiliser? Oh, attendez, laissez-moi deviner, vous avez divisé 0xFFFFFFFFFFFFFFFF par phi et pas 2^64.
    • arrondi vers le bas est certainement 0x...c15. wolframalpha.com/input/...
    • WolframAlpha a la perte de précision entre les opérations.
    • vous n'avez aucun moyen de spécification de la précision souhaitée dans il. Essayez long double à la place.
    • Vous êtes l'introduction de la perte de précision en raison de la "0.5" (qui est par défaut à 7 chiffres). Utiliser "1/2" exacte de l'arithmétique, ou d'utiliser des "0.500000000000000000" si vous voulez plus de précision. long double seulement a 64 bits de précision, il n'est pas tout à fait assez pour le calcul ici.
    • N'est pas de la connerie moi, 1/2 est exactement 0.5 dans cet univers, à proprement parler. sizeof(long double) de 10 octets (80 bits) sur coliru (x87 long double) et de 16 octets (128 bits) sur GCC x86-64.

    InformationsquelleAutor Mike Seymour
  2. 22

    Prendre un coup d'oeil à la DDJ article de Bob Jenkins depuis 1997. La magie de la constante ("nombre d'or") est expliquée comme suit:

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

    InformationsquelleAutor NPE