Est-il possible d'implémenter une table de hachage bien distribuée sans utiliser l'opérateur%?

11

Je cherche à implémenter une table de hachage rapide et bien distribuée en C #. J'ai du mal à choisir ma fonction de contrainte de hachage qui prend un code de hachage arbitraire et le "contraint" afin qu'il puisse être utilisé pour indexer les compartiments. Il y a deux options que je vois jusqu'à présent:

  • D'une part, vous pouvez vous assurer que vos compartiments ont toujours un nombre premier d'éléments, et pour contraindre le hachage, vous le modulez simplement par le nombre de compartiments. C'est en fait ce que fait le dictionnaire .NET . Le problème avec cette approche est que l'utilisation de% est extrêmement lente par rapport à d'autres opérations; si vous regardez les tables d'instructions Agner Fog , idiv(qui est le code assembleur généré pour%) a une latence d'instruction de ~ 25 cycles pour les nouveaux processeurs Intel. Comparez cela à environ 3 pour mul, ou 1 pour les opérations de manipulation de bits comme and, orou xor.

  • D'un autre côté, le nombre de compartiments peut toujours être une puissance de 2. Vous devrez toujours calculer le module du hachage afin de ne pas tenter d'indexer en dehors du tableau, mais cette fois ce sera moins cher . Étant donné que pour des puissances de 2 % Nest juste & (N - 1), la contrainte est réduite à une opération de masquage qui ne prend que 1-2 cycles. Cela se fait par sparsehash de Google . L'inconvénient est que nous comptons sur les utilisateurs pour fournir de bons hachages; masquer le hachage coupe essentiellement une partie du hachage, donc nous ne prenons plus en compte tous les bits du hachage. Si le hachage de l'utilisateur est inégalement réparti, par exemple, seuls les bits supérieurs sont remplis ou les bits inférieurs sont toujours les mêmes, alors cette approche a un taux de collisions beaucoup plus élevé.

Je recherche un algorithme que je peux utiliser qui a le meilleur des deux mondes: il prend en compte tous les bits du hachage et est également plus rapide que l'utilisation de%. Il ne doit pas nécessairement être un module, juste quelque chose qui est garanti d'être dans la plage 0..N-1(où N est la longueur des godets) et a une distribution uniforme pour tous les emplacements. Un tel algorithme existe-t-il?

Merci pour ton aide.

James Ko
la source
1
Recherchez l' effet d'avalanche , ainsi que l'explication dans murmurhash3 (smhasher) . Cependant, le point fondamental de votre question n'est pas abordé en adoptant une meilleure fonction de hachage. Au lieu de cela, il s'agit de savoir pourquoi les utilisateurs n'adoptent pas la même meilleure fonction de hachage en premier lieu, et une sollicitation de contre-mesures (comme si les utilisateurs étaient malveillants paresseux).
rwong
Pour modulo rapide (2^N +/- 1), voir stackoverflow.com/questions/763137/…
rwong
@rwong Je suis désolé, mais je ne sais pas trop ce que votre commentaire a à voir avec mon message. Je ne contrôle pas le hachage fourni par l'utilisateur, donc je ne recherche pas une meilleure fonction de hachage. Je ne comprends pas non plus ce que vous entendez par «utilisateurs malveillants paresseux».
James Ko
4
Si la fonction de hachage est médiocre, l'implémenteur de table de hachage ne peut rien faire pour "corriger" la mauvaise distribution. Modulo un nombre premier ne répare pas un mauvais hachage. Considérons une fonction de hachage produisant en sortie des multiples d'un nombre premier. J'ai vu un tel problème dans le vrai code de production.
Frank Hileman

Réponses:

9

Les implémentations modernes de table de hachage n'utilisent pas la fonction modulo. Ils utilisent souvent la puissance de deux tables de taille et coupent les bits inutiles. Une fonction de hachage idéale permettrait cela. L'utilisation de modulo combinée à des tailles de tableaux de nombres premiers est apparue à l'époque où les fonctions de hachage étaient généralement médiocres, comme elles le sont souvent dans le développement .net. Je recommande de lire sur SipHash , une fonction de hachage moderne, puis de lire sur d'autres fonctions modernes, telles que xxHash .

Je devrais expliquer pourquoi les fonctions de hachage .net sont souvent médiocres. Dans .net, les programmeurs sont souvent obligés d'implémenter des fonctions de hachage en remplaçant GetHashcode. Mais .net ne fournit pas les outils nécessaires pour garantir que les fonctions créées par le programmeur sont de haute qualité, à savoir:

  • encapsulation de l'état de hachage dans une structure ou une classe
  • hachage "ajouter" des fonctions, qui ajoutent de nouvelles données à l'état de hachage (ajoutez un tableau d'octets, ou un double, par exemple)
  • une fonction de «finalisation» du hachage, pour produire l'avalanche
  • encapsulation du résultat de hachage - en .net, vous avez un choix, un entier signé 32 bits.

Pour plus d'informations sur l'utilisation d'un résultat de fonction de hachage en tant qu'index de table de hachage, consultez les définitions des formes de hachage universelles dans cet article: Hachage universel 64 bits plus rapide utilisant des multiplications sans report

Frank Hileman
la source
3

Pour utiliser AND tout en conservant tous les bits, utilisez également XOR.

Pour un exemple temp = (hash & 0xFFFF) ^ ( hash >> 16); index = (temp & 0xFF) ^ (temp >> 8);,.

Pour cet exemple, il n'y a pas de modulo et tous les 32 bits d' hasheffet le 8 bits index. Cependant, qu'il soit plus rapide ou non que DIV est quelque chose qui dépend de trop de facteurs, et il peut facilement être plus lent que DIV dans certains cas (par exemple, un grand hachage et un index minuscule).

Brendan
la source
Cela va toujours être plus rapide que DIV / IDIV, mais je ne pense pas que cela réponde à ma question - indexsera dans la plage [0..255]. J'ai besoin de quelque chose dans la gamme [0..n-1], où nest le nombre de seaux.
James Ko
@JamesKo Mais si vous implémentez un dictionnaire, vous contrôlez également le nombre de compartiments (dans une certaine mesure). Ainsi, au lieu de nombres premiers, vous pouvez choisir des puissances de deux. (Que ce soit une bonne idée, je ne peux pas vous le dire.)
svick
@svick Pour des puissances de 2, nous pourrions faire une simple opération de masque. Comme mentionné dans la question, je cherche un moyen bon marché de le faire avec des nombres premiers afin que même les hachages mal distribués soient pris en charge.
James Ko
1

Vous pouvez profiter du fait que de nombreux entiers premiers ont un inverse multiplicatif modulaire. Consultez cet article . Vous avez satisfait à l'une des contraintes en rendant votre indice de compartiment premier et le module 2 ^ n, qui sont intrinsèquement relativement premiers.

L'article décrit l'algorithme pour trouver un nombre tel que la multiplication par ce nombre et l'ignorance du débordement produiront le même résultat que si vous aviez divisé par la taille de l'index de compartiment.

BobDalgleish
la source