Souvent une simple fonction de hachage fonctionne en prenant les "composantes" de l'entrée (caractères dans le cas d'une chaîne de caractères), et de les multiplier par les pouvoirs de certains constante, et en les ajoutant dans certains type entier. Ainsi, par exemple, un type (bien que pas particulièrement bon) hash d'une chaîne de caractères peut être:
(first char) + k * (second char) + k^2 * (third char) + ...
Alors si un bouquet de chaînes ayant tous le même premier char sont nourris, les résultats seront tous être de la même modulo k, au moins jusqu'à ce que le type integer overflow.
[À titre d'exemple, Java chaîne hashCode est étrangement similaire à celui - ci; il ne les caractères de l'ordre inverse, avec k=31. Ainsi, vous obtenez frappant les relations modulo 31 entre les chaînes qui se terminent de la même façon, et en frappant les relations modulo 2^32 entre les chaînes sont identiques, à l'exception près de la fin. Ce n'est pas sérieusement gâcher hashtable comportement.]
Une table de hachage fonctionne en prenant le module de la table de hachage sur le nombre de compartiments.
Il est important dans une table de hachage de ne pas produire des collisions susceptibles de cas, comme les collisions de réduire l'efficacité de la table de hachage.
Maintenant, supposons que quelqu'un met tout un tas de valeurs dans une table de hachage qui ont une certaine relation entre les éléments, comme ayant tous le même caractère. C'est un assez prévisible mode d'utilisation, je dirais, de sorte que nous n'en voulons pas à produire de trop nombreuses collisions.
Il s'avère que "en raison de la nature des mathématiques", si la constante utilisée dans la table de hachage, et le nombre de compartiments, sont premiers entre eux, alors les collisions sont minimisés dans certains cas courants. Si ils ne sont pas premiers entre eux, alors il ya quelques assez simples relations entre les entrées pour que les collisions ne sont pas minimisés. Tous les hachages de sortir de l'égalité modulo le facteur commun, ce qui veut dire qu'ils vont tous tomber dans le 1/n th des seaux qui ont que la valeur modulo le facteur commun. Vous obtenir n fois le nombre de collisions, où n est le facteur commun. Puisque n est au moins 2, je dirais que c'est inacceptable pour une assez simple cas d'utilisation pour générer au moins deux fois plus de collisions que la normale. Si l'utilisateur va briser notre réseau de distribution dans des seaux, nous voulons qu'il soit un accident bizarre, pas simple d'utilisation prévisibles.
Maintenant, tables de hash implémentations ont évidemment aucun contrôle sur les éléments mis en eux. Ils ne peuvent pas les empêcher d'être liés. Donc la chose à faire est de s'assurer que la constante et les comtes de seau sont premiers entre eux. De cette façon, vous n'êtes pas reposer sur le "dernier" seule composante de déterminer le module de la benne à l'égard de certains petits facteur commun. Autant que je sache, ils n'ont pas à être le premier à atteindre cela, il suffit de premiers entre eux.
Mais si la fonction de hachage et de la table de hachage sont écrits de façon indépendante, puis la table de hachage ne sait pas comment la fonction de hachage œuvres. Il peut être en utilisant une constante avec de petits facteurs. Si vous êtes chanceux, il peut fonctionner de façon totalement différente et être non-linéaire. Si le hachage est assez bonne, alors tout comte de seau est tout simplement parfait. Mais un paranoïaque de la table de hachage ne pouvez pas assumer une bonne fonction de hachage, il doit donc utiliser un nombre premier de seaux. De même, un paranoïaque de la fonction de hachage doit utiliser un largeish premier constante, afin de réduire le risque que quelqu'un utilise un certain nombre de compartiments qui arrive à avoir un facteur commun avec la constante.
Dans la pratique, je pense que c'est assez normal d'utiliser une puissance de 2, comme le nombre de compartiments. C'est pratique et évite d'avoir à les chercher partout ou pré-sélectionner un nombre premier de la bonne grandeur. Si vous comptez sur la fonction de hachage pas à utiliser même les multiplicateurs, qui est généralement une hypothèse sûre. Mais vous pouvez toujours obtenir quelques gros hachage comportements basés sur des fonctions de hachage comme celle-ci, et le premier comte de seau pourrait aider davantage.
Mettre sur le principe que "tout doit être le premier" est autant que je sache suffisamment mais pas une condition nécessaire pour une bonne répartition sur les tables de hashage. Il permet à chacun d'interagir sans avoir besoin de supposer que les autres ont suivi la même règle.
[Edit: il y a une autre plus spécialisée raison de l'utilisation d'un nombre premier de seaux, qui est que si vous gérer les collisions avec linéaire de détection. Alors vous calculer une foulée de l'hashcode, et si cette foulée sort pour être un facteur de le comte de seau, alors vous ne pouvez le faire (bucket_count / foulée) sondes avant que vous êtes de retour où vous avez commencé. Le cas plus que vous voulez éviter, c'est de la foulée = 0, bien sûr, qui doit être spéciale-emballé, mais pour éviter aussi des particuliers-boîtier bucket_count / foulée égal à un entier plus petit, vous pouvez simplement faire le bucket_count premier et pas soin de ce que la foulée est fournie, elle n'est pas 0.]
