Pourquoi les fonctions de hachage utiliser un nombre premier module?
Il y A longtemps, j'ai acheté une des structures de données livre hors de la table de négociation pour $1.25. En elle, l'explication d'une fonction de hachage a dit qu'il devrait finalement mod par un nombre premier en raison de "la nature des mathématiques".
Qu'attendez-vous de 1,25 $livre?
De toute façon, j'ai eu des années à réfléchir sur la nature des mathématiques, et ne peut toujours pas comprendre.
Est la distribution de nombres vraiment plus, même lorsqu'il existe un nombre premier de seaux? Ou est-ce un ancien programmeur de l'histoire que tout le monde accepte parce que tout le monde d'autre l'accepte?
- Parfaitement raisonnable question: Pourquoi devrait-il être un nombre premier de seaux?
- Cette question semble être hors-sujet, car il est plus que probable appartient sur Informatique.
- cs.stackexchange.com/a/64191/64222 un autre bien argumenté explication.
- connexes: Pourquoi est-il préférable d'utiliser un nombre premier comme un mod dans une fonction de hachage? et Pourquoi Java est hashCode() en Chaîne de caractères utilisez 31 comme un multiplicateur? et cette réponse
Vous devez vous connecter pour publier un commentaire.
Généralement 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:
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, puis les collisions sont minimisés dans certains cas courants. Si elles 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.]
La première chose à faire lors de l'insertion/récupération à partir de la table de hachage est de calculer le hashCode de la clé et ensuite trouver le bon seau en découpant le hashCode de la taille de la table de hachage en faisant hashCode % table_length. Voici 2 'états' que vous avez probablement lu quelque part
Et en voici la preuve.
Si supposons que votre hashCode fonction des résultats dans la suite de hashCodes entre autres {x , 2x, 3x, 4x, 5x, 6x...}, puis tous ceux-ci vont être regroupés dans juste m nombre de compartiments, où m = table_length/GreatestCommonFactor(table_length, x). (Il est trivial de vérifier/tirer cette). Maintenant, vous pouvez effectuer l'une des opérations suivantes pour éviter le regroupement des
Assurez-vous de ne pas générer trop d'hashCodes qui sont des multiples d'un autre hashCode comme dans {x, 2x, 3x, 4x, 5x, 6x...}.Mais cela peut être difficile si votre table de hachage est censé avoir des millions d'entrées.
Ou tout simplement faire de m égale à la table_length en faisant GreatestCommonFactor(table_length, x) égal à 1, je.e en faisant table_length premiers avec x. Et si x peut être n'importe quel numéro, puis assurez-vous que table_length est un nombre premier.
De - http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html
http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/
Assez d'explication claire, avec des photos aussi.
Edit: en résumé, les nombres premiers sont utilisés parce que vous avez le plus de chances d'obtenir une valeur unique lors de la multiplication des valeurs par le premier nombre choisi et l'ajout de tous. Par exemple, étant donné une chaîne de caractères, en multipliant chaque lettre de la valeur avec le nombre premier et puis en ajoutant celles de tous vous donnera sa valeur de hachage.
Une meilleure question serait, exactement pourquoi le nombre 31?
*32est un simple décalage de bits, ou mieux, une immédiate adresse facteur d'échelle (par exemple,lea eax,eax*8; leax, eax,eax*4sur x86/x64). Donc*31est un bon candidat pour le premier numéro de la multiplication. C'était à peu près vrai il y a quelques années - maintenant, dernière Processeurs de l'architecture ont une quasi-instantanéité de la multiplication - division est toujours plus lent...tl;dr
index[hash(input)%2]seraient le résultat d'une collision de la moitié de toutes les hachages et une plage de valeurs.index[hash(input)%prime]résultats dans un accident de <2 de toutes les tables de hachage. La fixation du diviseur à la taille de la table s'assure également que le nombre ne peut être supérieur à la table.Nombres premiers sont utilisés parce que vous avez de bonnes chances d'obtenir une valeur unique pour une typique fonction de hachage qui utilise des polynômes modulo P.
Dites, vous utilisez une telle fonction de hachage pour les chaînes de longueur <= N, et vous avez une collision. Cela signifie que 2 différents polynômes de produire la même valeur modulo P. La différence de ces polynômes est encore un polynôme de même degré N (ou moins). Il n'a pas plus de N racines (c'est ici la nature de la démonstration mathématique elle-même, puisque cette revendication n'est vrai que pour un polynôme sur un champ => nombre premier). Donc, si N est de beaucoup inférieure à P, vous êtes susceptibles de ne pas avoir de collision. Après cela, l'expérience peut sans doute montrer que 37 est assez grand pour éviter les collisions pour une table de hachage de chaînes de caractères qui ont une longueur de 5 à 10, et est assez petit pour l'utiliser pour les calculs.
Juste pour donner un autre point de vue il y a ce site:
http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth
Qui prétend que vous devez utiliser le plus grand nombre de seaux possible, par opposition à l'arrondi vers le bas à un premier nombre de compartiments. Il semble comme une possibilité raisonnable. Intuitivement, je peux certainement voir comment un grand nombre de seaux serait mieux, mais je suis incapable de faire un argument mathématique de cette.
http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/
Il dépend du choix de la fonction de hachage.
De nombreuses fonctions de hachage combiner les différents éléments dans les données en les multipliant avec certains facteurs modulo la puissance de deux correspondant à la taille de mot de la machine (que le module est gratuit simplement en laissant le calcul de débordement).
Vous ne voulez pas de facteur commun entre un multiplicateur pour un élément de données et la taille de la table de hachage, car il pourrait arriver que la variation de l'élément de données n'a pas de répartir les données sur l'ensemble de la table. Si vous choisissez une prime pour la taille de la table tel un facteur commun est très peu probable.
D'autre part, ces facteurs sont généralement constitués de nombres premiers impairs, donc vous devriez également être en sécurité à l'aide de puissances de deux pour votre table de hachage (par exemple, Eclipse utilise 31 lorsqu'il génère le Java hashCode() la méthode).
Supposons que votre tableau de taille (ou le nombre de modulo) est T = (B*C). Maintenant, si hachage pour vos commentaires, c'est comme (N*A*B) où N peut être un entier, alors votre sortie ne sera pas bien réparti. Parce que chaque fois que n devient C, 2C, 3C, etc., votre sortie va commencer à répéter. par exemple, votre sortie sera distribué que dans C les positions. A noter que C est ici (T /HCF(tableau de taille, hash)).
Ce problème peut être éliminé en faisant HCF 1. Les nombres premiers sont très bons pour cela.
Une autre chose intéressante est que, lorsque T est 2^N. il donnera à la sortie exactement le même que tout le bas de N bits d'entrée de hachage. Comme chaque nombre peut être représenté des puissances de 2, quand nous allons prendre le modulo d'un nombre quelconque de T, nous allons déduire l'ensemble des puissances de 2, numéro de formulaire, qui sont >= N, donc toujours en donnant le numéro de modèle spécifique, liée à l'entrée. C'est aussi un mauvais choix.
De même, T que 10^N est mauvaise, car de semblables motifs (pattern en notation décimale des nombres au lieu de binaire).
Donc, les nombres premiers ont tendance à donner une meilleure répartition des résultats, d'où sont bon choix pour la taille de la table.
Je crois qu'il a juste à voir avec le fait que les ordinateurs de travail avec en base 2. Il suffit de penser à la façon dont la même chose travaille pour la base 10:
Il n'a pas d'importance ce que le nombre est: tant que ça se termine avec 8, ses modulo 10 8.
De choisir un assez grand, non-puissance de deux numéro assurez-vous que la fonction de hachage est vraiment une fonction de tous les bits d'entrée, plutôt qu'un sous-ensemble d'entre eux.
Je voudrais ajouter quelque chose pour Steve Jessop est de la réponse(je ne peux pas commenter car je n'ai pas assez de réputation). Mais j'ai trouvé utile du matériel. Sa réponse est très utile, mais il a fait une erreur: le seau de taille ne devrait pas être une puissance de 2. Je vais juste citer le livre "Introduction à l'Algorithme" par Thomas Cormen, Charles Leisersen, et al sur page263:
Espère que cela aide.
Pour une fonction de hachage, il est non seulement important de minimiser les colisions en général, mais il est impossible de rester avec le même hash, tandis que chaning quelques octets.
Dire que vous avez une équation:
(x + y*z) % key = xavec0<x<keyet0<z<key.Si la clé est un primenumber n*y=clé est vrai pour tout n dans N et false pour tous les autres le nombre.
Un exemple de cas où la clé n'est pas un premier exemple:
x=1, z=2 et key=8
Parce que la clé/z=4 est encore un nombre naturel, 4 devient une solution de notre équation et dans ce cas (n/2)*y = clé est vrai pour tout n dans N. Le montant de solutions de l'équation ont practially doublé parce que 8 n'est pas un nombre premier.
Si notre attaquant sait déjà que 8 est solution de l'équation qu'il peut changer le fichier à partir de la production de 8 à 4 et obtient toujours le même hachage.
J'ai lu le populaire site wordpress liés à certaines de ces réponses d'en haut. De ce que j'ai compris, j'aimerais partager une simple observation que j'ai faite.
Vous pouvez trouver tous les détails dans l'article ici, mais supposons ce qui suit est vrai:
Général hashmap mise en veut que 2 choses à être unique.
Comment pouvons-nous obtenir l'index unique? En faisant de la taille initiale de l'interne contenant un premier ainsi. Donc, fondamentalement, le premier est impliqué parce qu'il possède ce trait unique de produire des numéros uniques qui à la fin nous devons à l'aide de l'ID d'objets et de trouver des indices à l'intérieur du récipient interne.
Exemple:
key = "key"
value = "valeur"
uniqueId = "k" * 31 ^ 2 +
"e" * 31 ^ 1` +
"y"
cartes à id unique
Maintenant, nous voulons un emplacement unique de notre valeur, de sorte que nous
uniqueId % internalContainerSize == uniqueLocationForValue, en supposantinternalContainerSizeest aussi un nombre premier.Je sais que c'est simplifié, mais je suis l'espoir d'obtenir l'idée générale à travers.