knuth multiplicatif de hachage

Est-ce une mise en œuvre correcte de la Knuth multiplicatif de hachage.

int hash(int v)
{
    v *= 2654435761;
    return v >> 32;
}

Déborde dans la multiplication affecte l'algorithme?

Comment améliorer les performances de cette méthode?

Vous voudrez certainement utiliser unsigned int (ou unsigned long long, car elle semble dépendre de la taille de l' >32 bits) au lieu de la plaine int.
Oui, dépassement de sera certainement éviter ce travail. En fait, si votre int est typique de ce code renvoie toujours 0 ou -1.
Votre de décalage de bits est (si l'int est de 32 bits) à l'extrême. Combien de morceaux de votre hash? Soustraire de 32
ok, donc si je veux 32bit de hachage, je n'ai pas besoin de décaler les bits
est dessin à la mauvaise conclusion, oui, vous avez à décalage de bits. Vous avez juste besoin de commencer avec un type entier, qui est de plus de 32 bits, tels que uint64_t.

OriginalL'auteur José | 2012-08-08

  1. 11

    Ok, je l'ai regardé dans TAOCP volume 3 (2e édition), de l'article 6.4, page 516.

    Cette mise en œuvre n'est pas correct, même si, comme je l'ai mentionné dans les commentaires il peut donner le résultat correct de toute façon.

    Une manière correcte (je pense - n'hésitez pas à lire le chapitre correspondant de TAOCP et vérifier cela) est quelque chose comme ceci: (important: oui, vous devez passer le résultat à droite de la réduire, de ne pas l'utiliser au niveau du bit. Cependant, ce n'est pas de la responsabilité de cette fonction - la réduction de la portée n'est pas bien partie de hachage lui-même)

    uint32_t hash(uint32_t v)
{
    return v * UINT32_C(2654435761);
    //do not comment about the lack of right shift. I'm not ignoring it. read on.
}

    Note le uint32_ts '(par opposition à int's) - assurez-vous que la multiplication des débordements modulo 2^32, comme il est censé le faire si vous choisissez 32, comme la taille de mot. Il ya aussi pas de décalage à droite par k ici, car il n'y a aucune raison de donner la responsabilité de gamme-la réduction de base de la fonction de hachage et il est effectivement plus utile pour obtenir le résultat complet. La constante 2654435761 est à partir de la question, la réelle suggéré constante est 2654435769, mais c'est une petite différence, qui autant que je sache, n'affecte pas la qualité de la table de hachage.

    D'autres implémentations de passer le résultat à droite par une quantité (pas toute la taille de mot bien, qui ne fait pas de sens et C++ n'aime pas), en fonction du nombre de bits de hachage dont vous avez besoin. Ou ils peuvent utiliser une autre constante (sous certaines conditions) ou d'un autre mot de taille. La réduction de la valeur de hachage modulo quelque chose est pas valide la mise en œuvre, mais une erreur commune, il est probable qu'un standard de facto façon de faire de la plage de réduction sur une table de hachage. Bas les bits d'une multiplicatif de hachage sont les pires de qualité bits (ils dépendent moins de l'entrée), vous ne voulez utiliser que si vous avez vraiment besoin de plus de bits, tout en réduisant le hachage modulo une puissance de deux serait de retour que le pire des bits. En effet, c'est l'équivalent de jeter la plupart de l'entrée des bits de trop. La réduction modulo un non-pouvoir-de-deux n'est pas si mauvais puisqu'il ne mélange dans les bits supérieurs, mais ce n'est pas la façon dont le multiplicative de hachage a été défini.

    Donc, pour être clair, oui il y a un décalage à droite, mais c'est la réduction de la portée pas de hachage et ne peut être la responsabilité de la table de hachage, car il dépend de sa taille interne.

    Le type doit être signés, sinon le dépassement est pas spécifié (donc peut-être tort, et pas seulement sur la non-2-complément d'architectures, mais aussi sur trop intelligent compilateurs) et le droit facultatif maj serait signé maj (trompe).

    Sur la page je mentionne au sommet, il y a cette formule:

    knuth multiplicatif de hachage

    Ici, nous avons Un = 2654435761 (ou 2654435769), w = 232 et M = 232. Le calcul de AK/w donne un point fixe résultat avec le format Q32.32, le mod 1 étape ne prend que les 32 fraction bits. Mais c'est juste la même chose que de faire une multiplication modulaire et puis dire que le résultat est la fraction bits. Bien sûr, lorsqu'il est multiplié par M, tous la fraction bits devenir entier bits car de la façon dont M a été choisi, et il simplifie juste un simple vieux multiplication modulaire. Lorsque M est une puissance plus faible des deux, qui vient de la droite déplace le résultat, comme mentionné.

    "CS 3110 Conférence 21: fonctions de Hachage: Multiplicatif de hachage" affirme que "La division par 2^q est crucial. L'erreur courante lors multiplicatif de hachage est d'oublier de le faire."
    ce qui est bien, ce que j'ai fait ici est de choisir M=2^32, mais lorsqu'il n'est pas tous les 32 bits sont souhaitées c'est le fond de bits qui doit être jetée.
    Cette entrée de Wikipedia en.wikipedia.org/wiki/Hash_table#Choosing_a_good_hash_function affirme que multiplicatif de hachage a une mauvaise clustering et n'est donc pas approprié pour ouvrir schéma d'adressage (en.wikipedia.org/wiki/Open_addressing). Comment est-il vrai? Si c'est le cas, est-il une alternative? Merci beaucoup
    dans mon expérience, il n'est pas mauvais. Notez que la source de la revendication bas bits, ce qui est la pire chose à faire, il n'est donc pas surprenant qu'ils ont obtenu un mauvais résultat. Le fond de bits d'un produit ne dépend pas d'une hausse des bits à partir de l'entrée, de sorte que c'est l'équivalent de jeter plus de la clé de loin avant le hachage.
    juste assez. Je pense que parler des chiffres concrets de bits, il serait clair que vous parlez déjà débordé résultat de la multiplication: "si vous avez besoin pour réduire l'résultant 32 bits valeur de hachage d'un plus petit nombre, 24 bits, parce que quelque chose dans votre système nécessite un 24-bits de la valeur, alors vous devriez utiliser le top 24 bits (c'est à dire décalage à droite par 8) plutôt que d'utiliser le bas de 24 bits, depuis le sommet de bits dépend plus de l'entrée."

    OriginalL'auteur harold

  2. 13

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

    Supposons que p est entre 0 et 32, l'algorithme va comme ceci:

    • De calcul alpha comme l'entier le plus proche à 2^32 (-1 + sqrt(5)) /2. Nous obtenons alpha = 2 654 435 769.

    • Calculer k * alpha et de réduire le résultat modulo 2^32:

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

    • Garder le plus de p bits de n1:

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

    Ainsi, une bonne mise en œuvre de Knuth multiplicatif algorithme 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 passer le résultat par (32 - p) est une erreur majeure. Comme vous l'auriez perdu toutes les bonnes propriétés de la table de hachage. Il aurait pour effet de transformer une même séquence dans une même séquence qui serait très mauvais comme tous les impairs slots serait rester inoccupée. C'est comme de prendre un bon vin et de la mélanger avec du Coca-cola. Par ailleurs, le web est plein de gens misquoting Knuth et à l'aide d'une multiplication par 2 654 435 761 sans prendre les bits supérieurs. Je viens d'ouvrir le Knuth et il n'a jamais dit une telle chose. Il ressemble à un mec qui a décidé qu'il était "intelligent" a décidé de faire un premier nombre à près de 2 654 435 769.

    Bare à l'esprit que la plupart des tables de hachage implémentations ne permettent pas ce genre de signature dans leur interface, comme ils ne permettent

    uint32_t hash(int x);

    et de réduire hash(x) modulo 2^p pour calculer la valeur de hachage pour x. Ces tables de hachage ne peut pas accepter l'Knuth multiplicatif de hachage. Cela pourrait être une raison pour laquelle tant de gens complètement ruiné l'algorithme en oubliant de prendre le plus de p bits.
    Si vous ne pouvez pas utiliser la Knuth multiplicatif de hachage avec std::unordered_map ou std::unordered_set. Mais je pense que les tables de hachage utiliser un nombre premier comme la taille, de sorte que le Knuth multiplicatif de hachage n'est pas utile dans ce cas. À l'aide de hash(x) = x être un bon ajustement pour les tables.

    Source: "Introduction aux Algorithmes, troisième édition", Cormen et coll., 13.3.2 p:263

    Source: "The Art of Computer Programming, Volume 3, de Tri et de Recherche", D. E. Knuth, 6.4 p:516

    N'est-ce pas la principale raison pour laquelle les gens "vous avez oublié de prendre le plus de p bits" en fait, juste qu'ils ont été à l'aide de 4 bits entiers non signés, pour qui p = 32, donc 32 - p est de 0?
    Notez également que si l'aide de l'intégrale 32 bits, la valeur de hachage va transformer un nombre pair de nombres pairs.

    OriginalL'auteur InsideLoop

  3. 0

    Si l'argument est un pointeur puis-je utiliser ce

    #include <inttypes.h>

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);
}

    J'ai l'habitude de l'utiliser comme le secours par défaut fonction de hachage dans la hashmap implémentations, dictionnaires, jeux, etc...

    OriginalL'auteur couven92

  4. 0

    Risquez d'être en retard, mais voici une Implémentation Java de Knuth Méthode :

    Pour une table de hachage de Taille N : 

    public long hash(int key) {
    long l = 2654435769L;
    return (key * l >> 32) % N ;
}
    Pourquoi ne pas utiliser un long littérale 2654435769L? l'appel de parseLong semble ici prix
    Droit, devrait être en mesure de le faire sans trop de soucis 🙂 Édité

    OriginalL'auteur schrodingers_cat16