knuth hachage multiplicatif

Ok, j’ai cherché dans TAOCP volume 3 (2e édition), section 6.4, page 516.

Cette implémentation n’est pas correcte, bien que, comme je l’ai mentionné dans les commentaires, elle puisse quand même donner le résultat correct.

Une manière correcte (je pense – sentez-vous libre de lire le chapitre pertinent de TAOCP et de vérifier ceci) est quelque chose comme ceci:

 uint32_t hash(uint32_t v) { return v * UINT32_C(2654435761); } 

Notez les uint32_t (par opposition à int ) – ils s’assurent que la multiplication déborde du modulo 2 ^ 32, comme il est supposé le faire si vous choisissez 32 comme taille du mot. Ici aussi, il n’ya pas de décalage correct de k , car il n’ya aucune raison de donner la responsabilité de la réduction de la scope à la fonction de hachage de base et il est en fait plus utile d’obtenir le résultat complet. La constante 2654435761 est tirée de la question. La constante suggérée est 2654435769, mais c’est une petite différence qui, à ma connaissance, n’affecte pas la qualité du hachage.

D’autres implémentations valides décalent légèrement le résultat (pas la taille du mot, cela n’a aucun sens et C ++ ne l’aime pas), en fonction du nombre de bits de hachage dont vous avez besoin. Ils peuvent aussi utiliser une autre constante (sous certaines conditions) ou une autre taille de mot. Réduire le hachage modulo n’est pas une implémentation valide, mais une erreur courante. Il s’agit probablement d’un moyen standard de facto de réduire la scope d’un hachage. Les bits du bas d’un hachage multiplicatif sont les bits de la plus mauvaise qualité (ils dépendent de moins de l’entrée), vous ne voulez les utiliser que si vous avez vraiment besoin de plus de bits, tout en réduisant le hachage modulo, une puissance de deux ne renverrait que le pire bits . En effet, cela revient également à jeter la plupart des bits d’entrée. Réduire modulo avec un non-pouvoir de deux n’est pas si grave puisqu’il mélange les bits les plus élevés, mais ce n’est pas la définition du hachage multiplicatif.

Le type doit être non signé, sinon le débordement n’est pas spécifié (donc potentiellement faux, pas seulement sur les architectures avec complément à 2, mais aussi sur les compilateurs trop intelligents) et le décalage à droite optionnel serait un décalage signé (faux).

Sur la page que je mentionne en haut, il y a cette formule:

Ici, nous avons A = 2654435761 (ou 2654435769), w = 2 ³² et M = 2 ³² . Le calcul de AK / w donne un résultat en virgule fixe au format Q32.32, l’étape mod 1 ne prenant que les 32 bits de fraction. Mais c’est exactement la même chose que de faire une multiplication modulaire et de dire ensuite que le résultat est le nombre de bits de fraction. Bien sûr, lorsque multiplié par M, tous les bits de fraction deviennent des bits d’entier en raison de la façon dont M a été choisi, ce qui simplifie donc une simple multiplication modulaire. Lorsque M est une puissance inférieure à deux, cela modifie le résultat comme indiqué.

Le hachage multiplicatif de Knuth est utilisé pour calculer une valeur de hachage dans {0, 1, 2, ..., 2^p - 1} partir d’un entier k.

Supposons que p soit compris entre 0 et 32, l’algorithme est le suivant:

• Calculez alpha comme l’entier le plus proche de 2 ^ 32 (-1 + sqrt (5)) / 2. Nous obtenons alpha = 2 654 435 769.

• Calculez k * alpha et réduisez le résultat modulo 2 ^ 32:

  k * alpha = n0 * 2 ^ 32 + n1 avec 0 <= n1 <2 ^ 32

• Conservez les p bits les plus élevés de n1:

  n1 = m1 * 2 ^ (32-p) + m2 avec 0 <= m2 <2 ^ (32 - p)

Donc, une implémentation correcte de l’algorithme multiplicatif de Knuth en C ++ est:

 std::uint32_t knuth(int x, int p) { assert(p >= 0 && p <= 32); const std::uint32_t knuth = 2654435769; const std::uint32_t y = x; return (y * knuth) >> (32 - p); } 

Oublier de décaler le résultat de (32 – p) est une erreur majeure. Comme vous auriez perdu toutes les bonnes propriétés du hachage. Cela transformerait une séquence paire en une séquence paire, ce qui serait très mauvais, car tous les créneaux impairs restraient inoccupés. C’est comme prendre un bon vin et le mélanger avec du Coca-Cola. À propos, le Web regorge de gens qui citent mal Knuth et multiplient par 2 654 435 761 sans prendre les bits les plus élevés. Je viens d’ouvrir le Knuth et il n’a jamais dit une telle chose. On dirait qu’un gars qui a décidé qu’il était “intelligent” a décidé de prendre un nombre premier proche de 2 654 435 769.

N’oubliez pas que la plupart des implémentations de tables de hachage n’autorisent pas ce type de signature dans leur interface, car elles ne permettent que

 uint32_t hash(int x); 

et réduisez le hash(x) modulo 2 ^ p pour calculer la valeur de hachage pour x. Ces tables de hachage ne peuvent pas accepter le hachage multiplicatif de Knuth. C’est peut-être une raison pour laquelle tant de gens ont complètement ruiné l’algorithme en oubliant de prendre les p bits les plus élevés. Vous ne pouvez donc pas utiliser le hash multiplicatif de Knuth avec std::unordered_map ou std::unordered_set . Mais je pense que ces tables de hachage utilisent un nombre premier comme taille, de sorte que le hachage multiplicatif de Knuth n’est pas utile dans ce cas. L’utilisation de hash(x) = x conviendrait parfaitement pour ces tables.

Source: “Introduction aux algorithmes, troisième édition”, Cormen et al., 13.3.2 p: 263

Source: “L’art de la programmation informatique, volume 3, le sorting et la recherche”, DE Knuth, 6.4 p: 516

Si l’argument d’entrée est un pointeur, je l’utilise

 #include  uint32_t knuth_mul_hash(void* k) { ptrdiff_t v = (ptrdiff_t)k * UINT32_C(2654435761); v >>= ((sizeof(ptrdiff_t) - sizeof(uint32_t)) * 8); // Right-shift v by the size difference between a pointer and a 32-bit integer (0 for x86, 32 for x64) return (uint32_t)(v & UINT32_MAX); } 

Je l’utilise généralement comme fonction de hachage de secours par défaut dans les implémentations, les dictionnaires, les ensembles, etc.