Comment fonctionne une table de hachage?

494

Je cherche une explication du fonctionnement d'une table de hachage - en anglais simple pour un simple comme moi!

Par exemple, je sais qu'il prend la clé, calcule le hachage (je cherche une explication comment) puis effectue une sorte de modulo pour déterminer où il se trouve dans le tableau où la valeur est stockée, mais c'est là que ma connaissance s'arrête .

Quelqu'un pourrait-il clarifier le processus?

Edit: je ne demande pas spécifiquement comment les codes de hachage sont calculés, mais un aperçu général du fonctionnement d'une table de hachage.

Arec Barrwin
la source
4
Récemment, j'ai écrit cet article ( en.algoritmy.net/article/50101/Hash-table ) décrivant plusieurs façons, comment stocker et rechercher des données, avec un accent sur les tables de hachage et leurs stratégies (chaînage séparé, sondage linéaire, double hachage )
malejpavouk
1
Vous pouvez penser à une table de hachage comme une version étendue d'un tableau, ce n'est pas seulement limité à des clés entières consécutives.
user253751
1
En voici un autre: intelligentjava.wordpress.com/2016/10/19/…
nesvarbu

Réponses:

913

Voici une explication en termes simples.

Supposons que vous souhaitiez remplir une bibliothèque de livres et non pas simplement les remplir, mais que vous souhaitiez pouvoir les retrouver facilement lorsque vous en avez besoin.

Donc, vous décidez que si la personne qui veut lire un livre connaît le titre du livre et le titre exact à démarrer, c'est tout ce qu'il faut. Avec le titre, la personne, avec l'aide du bibliothécaire, devrait pouvoir trouver le livre facilement et rapidement.

Alors, comment pouvez-vous faire cela? Eh bien, évidemment, vous pouvez garder une sorte de liste où vous placez chaque livre, mais vous avez le même problème que la recherche dans la bibliothèque, vous devez rechercher la liste. Certes, la liste serait plus petite et plus facile à rechercher, mais vous ne voulez toujours pas effectuer une recherche séquentielle d'une extrémité de la bibliothèque (ou liste) à l'autre.

Vous voulez quelque chose qui, avec le titre du livre, peut vous donner le bon endroit à la fois, alors tout ce que vous avez à faire est de simplement vous diriger vers la bonne étagère et de prendre le livre.

Mais comment y arriver? Eh bien, avec un peu de réflexion lorsque vous remplissez la bibliothèque et beaucoup de travail lorsque vous remplissez la bibliothèque.

Au lieu de simplement commencer à remplir la bibliothèque d'un bout à l'autre, vous concevez une petite méthode intelligente. Vous prenez le titre du livre, l'exécutez à travers un petit programme informatique, qui crache un numéro d'étagère et un numéro d'emplacement sur cette étagère. C'est là que vous placez le livre.

La beauté de ce programme est que plus tard, lorsqu'une personne revient pour lire le livre, vous réintroduisez le titre dans le programme et récupérez le même numéro d'étagère et de slot que celui qui vous avait été initialement attribué, et c'est où se trouve le livre.

Le programme, comme d'autres l'ont déjà mentionné, est appelé algorithme de hachage ou calcul de hachage et fonctionne généralement en prenant les données qui y sont introduites (le titre du livre dans ce cas) et en calcule un nombre.

Pour simplifier, disons qu'il convertit simplement chaque lettre et symbole en un nombre et les résume tous. En réalité, c'est beaucoup plus compliqué que cela, mais laissons cela pour l'instant.

La beauté d'un tel algorithme est que si vous y introduisez la même entrée encore et encore, il continuera à cracher le même nombre à chaque fois.

Ok, c'est donc essentiellement comment fonctionne une table de hachage.

Les trucs techniques suivent.

Tout d'abord, il y a la taille du nombre. Habituellement, la sortie d'un tel algorithme de hachage se situe dans une plage d'un grand nombre, généralement beaucoup plus grande que l'espace que vous avez dans votre table. Par exemple, disons que nous avons de la place pour exactement un million de livres dans la bibliothèque. La sortie du calcul du hachage pourrait être de l'ordre de 0 à un milliard, ce qui est beaucoup plus élevé.

Alors que faisons-nous? Nous utilisons quelque chose appelé calcul de module, qui dit essentiellement que si vous comptiez jusqu'au nombre que vous vouliez (c'est-à-dire le nombre d'un milliard) mais que vous vouliez rester dans une plage beaucoup plus petite, chaque fois que vous atteigniez la limite de cette plage plus petite, vous recommençiez à 0, mais vous devez savoir jusqu'où vous êtes arrivé dans la grande séquence.

Supposons que la sortie de l'algorithme de hachage se situe dans la plage de 0 à 20 et que vous obtenez la valeur 17 à partir d'un titre particulier. Si la taille de la bibliothèque n'est que de 7 livres, vous comptez 1, 2, 3, 4, 5, 6 et lorsque vous atteignez 7, vous recommencez à 0. Comme nous devons compter 17 fois, nous en avons 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3 et le nombre final est 3.

Bien sûr, le calcul du module ne se fait pas comme ça, il se fait avec la division et un reste. Le reste de la division de 17 par 7 est de 3 (7 va 2 fois en 17 à 14 et la différence entre 17 et 14 est de 3).

Ainsi, vous placez le livre dans l'emplacement numéro 3.

Cela conduit au problème suivant. Collisions. Puisque l'algorithme n'a aucun moyen d'espacer les livres afin qu'ils remplissent exactement la bibliothèque (ou la table de hachage si vous voulez), il finira invariablement par calculer un nombre qui a été utilisé auparavant. Dans le sens de la bibliothèque, lorsque vous arrivez à l'étagère et au numéro d'emplacement dans lequel vous souhaitez mettre un livre, il y a déjà un livre là-bas.

Il existe différentes méthodes de gestion des collisions, notamment l'exécution des données dans un autre calcul pour obtenir un autre emplacement dans le tableau ( double hachage ), ou simplement pour trouver un espace proche de celui qui vous a été donné (c'est-à-dire juste à côté du livre précédent en supposant l'emplacement était également connu sous le nom de palpage linéaire ). Cela signifierait que vous avez des recherches à faire lorsque vous essayez de trouver le livre plus tard, mais c'est toujours mieux que de simplement commencer à une extrémité de la bibliothèque.

Enfin, à un moment donné, vous voudrez peut-être mettre plus de livres dans la bibliothèque que la bibliothèque ne le permet. En d'autres termes, vous devez créer une plus grande bibliothèque. Étant donné que l'emplacement exact dans la bibliothèque a été calculé en utilisant la taille exacte et actuelle de la bibliothèque, il s'ensuit que si vous redimensionnez la bibliothèque, vous pourriez avoir à trouver de nouveaux emplacements pour tous les livres depuis le calcul effectué pour trouver leurs emplacements. a changé.

J'espère que cette explication était un peu plus terre à terre que les seaux et les fonctions :)

Lasse V. Karlsen
la source
Merci pour une si bonne explication. Savez-vous où je peux trouver plus de détails techniques sur la façon dont il est implémenté dans le framework 4.x .Net?
Johnny_D
Non, ce n'est qu'un chiffre. Vous devez simplement numéroter chaque étagère et emplacement en commençant à 0 ou 1 et en augmentant de 1 pour chaque emplacement sur cette étagère, puis continuer la numérotation sur l'étagère suivante.
Lasse V. Karlsen
2
«Il existe différentes méthodes de gestion des collisions, y compris l'exécution des données dans un autre calcul pour obtenir une autre place dans le tableau» - qu'entendez-vous par un autre calcul? C'est juste un autre algorithme? OK, supposons donc que nous utilisons un autre algorithme qui génère un nombre différent en fonction du nom du livre. Plus tard, si je devais trouver ce livre, comment saurais-je quel algorithme utiliser? J'utiliserais le premier algorithme, le deuxième algorithme et ainsi de suite jusqu'à ce que je trouve le livre dont le titre est celui que je recherche?
user107986
1
@KyleDelaney: Non pour le hachage fermé (où les collisions sont gérées en trouvant un autre compartiment, ce qui signifie que l'utilisation de la mémoire est fixe mais que vous passez plus de temps à rechercher dans les compartiments). Pour le hachage ouvert aka enchaînement dans un cas pathologique (fonction de hachage terrible ou entrées délibérément conçues pour entrer en collision avec un adversaire / pirate), vous pourriez vous retrouver avec la plupart des compartiments de hachage vides, mais l'utilisation totale de la mémoire n'est pas pire - juste plus de pointeurs NULL au lieu de indexation dans les données utilement.
Tony Delroy
3
@KyleDelaney: besoin de la chose "@Tony" pour être notifié de vos commentaires. Il semble que vous vous posiez des questions sur le chaînage: disons que nous avons trois nœuds de valeur A{ptrA, valueA}, B{ptrB, valueB}, C{ptrC, valueC}et une table de hachage avec trois compartiments [ptr1, ptr2, ptr3]. Qu'il y ait ou non des collisions lors de l'insertion, l'utilisation de la mémoire est fixe. Vous pouvez ne pas avoir de collisions: A{NULL, valueA} B{NULL, valueB} C{NULL, valueC}et [&A, &B, &C], ou toutes les collisions A{&B, valueA} B{&C, valueB}, C{NULL, valueC}et [NULL, &A, NULL]: les seaux NULL sont-ils "gaspillés"? Un peu, pas du tout. Même mémoire totale utilisée.
Tony Delroy
104

Utilisation et Lingo:

  1. Les tables de hachage sont utilisées pour stocker et récupérer rapidement des données (ou enregistrements).
  2. Les enregistrements sont stockés dans des compartiments à l' aide de clés de hachage
  3. Les clés de hachage sont calculées en appliquant un algorithme de hachage à une valeur choisie (la valeur de clé ) contenue dans l'enregistrement. Cette valeur choisie doit être une valeur commune à tous les enregistrements.
  4. Chaque compartiment peut avoir plusieurs enregistrements qui sont organisés dans un ordre particulier.

Exemple du monde réel:

Hash & Co. , fondée en 1803 et dépourvue de toute technologie informatique, disposait d'un total de 300 classeurs pour conserver les informations détaillées (les dossiers) de leurs quelque 30 000 clients. Chaque dossier a été clairement identifié par son numéro de client, un numéro unique de 0 à 29 999.

Les greffiers de l'époque devaient chercher et stocker rapidement les dossiers des clients pour le personnel travaillant. Le personnel avait décidé qu'il serait plus efficace d'utiliser une méthodologie de hachage pour stocker et récupérer leurs enregistrements.

Pour déposer un dossier client, les commis au classement utiliseraient le numéro de client unique inscrit sur le dossier. À l'aide de ce numéro de client, ils moduleraient la clé de hachage de 300 afin d'identifier le classeur dans lequel il se trouve. Lorsqu'ils ouvriraient le classeur, ils découvriraient qu'il contenait de nombreux dossiers classés par numéro de client. Après avoir identifié l'emplacement correct, ils le glissaient simplement.

Pour récupérer un dossier client, les greffiers recevraient un numéro de client sur une feuille de papier. En utilisant ce numéro de client unique (la clé de hachage ), ils le moduleraient par 300 afin de déterminer quel classeur avait le dossier clients. En ouvrant le classeur, ils découvriraient qu'il contenait de nombreux dossiers classés par numéro de client. En parcourant les enregistrements, ils trouveraient rapidement le dossier client et le récupéreraient.

Dans notre exemple réel, nos seaux sont des classeurs et nos dossiers sont des dossiers .


Une chose importante à retenir est que les ordinateurs (et leurs algorithmes) traitent mieux les nombres que les chaînes. Ainsi, l'accès à un grand tableau à l'aide d'un index est beaucoup plus rapide que l'accès séquentiel.

Comme Simon l'a mentionné, je pense que ce qui est très important, c'est que la partie de hachage consiste à transformer un grand espace (de longueur arbitraire, généralement des chaînes, etc.) et à le mapper sur un petit espace (de taille connue, généralement des nombres) pour l'indexation. C'est très important à retenir!

Ainsi, dans l'exemple ci-dessus, les quelque 30 000 clients possibles sont mappés sur un espace plus petit.


L'idée principale est de diviser l'ensemble de vos données en segments afin d'accélérer la recherche réelle qui prend généralement beaucoup de temps. Dans notre exemple ci-dessus, chacun des 300 classeurs contiendrait (statistiquement) environ 100 enregistrements. La recherche (quelle que soit la commande) de 100 enregistrements est beaucoup plus rapide que d'avoir à traiter 30 000 enregistrements.

Vous avez peut-être remarqué que certains le font déjà. Mais au lieu de concevoir une méthodologie de hachage pour générer une clé de hachage, ils utiliseront dans la plupart des cas simplement la première lettre du nom de famille. Donc, si vous avez 26 classeurs contenant chacun une lettre de A à Z, vous venez en théorie de segmenter vos données et d'améliorer le processus de classement et de récupération.

J'espère que cela t'aides,

Jeach!

Jeach
la source
2
Vous décrivez un type spécifique de stratégie d'évitement de collision de table de hachage, appelé de manière variable «adressage ouvert» ou «adressage fermé» (oui, triste mais vrai) ou «chaînage». Il existe un autre type qui n'utilise pas les compartiments de liste mais stocke à la place les éléments «en ligne».
Konrad Rudolph
2
excellente description. sauf que chaque classeur contiendrait, en moyenne, environ des 100enregistrements (30 000 enregistrements / 300 armoires = 100). Cela pourrait valoir la peine d'être modifié.
Ryan Tuck
@TonyD, accédez à ce site sha-1 en ligne et générez un hachage SHA-1 TonyDque vous tapez dans le champ de texte. Vous vous retrouverez avec une valeur générée de quelque chose qui ressemble e5dc41578f88877b333c8b31634cf77e4911ed8c. Ce n'est rien de plus qu'un grand nombre hexadécimal de 160 bits (20 octets). Vous pouvez ensuite l'utiliser pour déterminer quel compartiment (une quantité limitée) sera utilisé pour stocker votre enregistrement.
Jeach
@TonyD, je ne sais pas où le terme "clé de hachage" est référé dans une affaire conflictuelle? Si oui, veuillez indiquer les deux emplacements ou plus. Ou êtes-vous en train de dire que «nous» utilisons le terme «clé de hachage» alors que d'autres sites tels que Wikipedia utilisent des «valeurs de hachage, des codes de hachage, des sommes de hachage ou simplement des hachages»? Dans l'affirmative, qui s'en soucie tant que le terme utilisé est cohérent au sein d'un groupe ou d'une organisation. Les programmeurs utilisent souvent le terme "clé". Je dirais personnellement qu'une autre bonne option serait la "valeur de hachage". Mais j'exclurais l'utilisation de "code de hachage, somme de hachage ou simplement hachage". Concentrez-vous sur l'algorithme et non sur les mots!
Jeach
2
@TonyD, j'ai changé le texte en "ils moduleraient la clé de hachage par 300", en espérant que ce sera plus propre et plus clair pour tout le monde. Merci!
Jeach
64

Cela s'avère être un domaine assez profond de la théorie, mais le schéma de base est simple.

Essentiellement, une fonction de hachage est juste une fonction qui prend les choses d'un espace (disons des chaînes de longueur arbitraire) et les mappe à un espace utile pour l'indexation (entiers non signés, par exemple).

Si vous n'avez qu'un petit espace de choses à hacher, vous pourriez vous contenter d'interpréter ces choses comme des entiers, et vous avez terminé (par exemple, des chaînes de 4 octets)

Habituellement, cependant, vous avez un espace beaucoup plus grand. Si l'espace des choses que vous autorisez en tant que clés est plus grand que l'espace des choses que vous utilisez pour indexer (vos uint32 ou autre), vous ne pouvez pas éventuellement avoir une valeur unique pour chacune. Lorsque deux ou plusieurs choses hachent le même résultat, vous devrez gérer la redondance de manière appropriée (on parle généralement de collision, et la façon dont vous la gérez ou non dépendra un peu de ce que vous êtes en utilisant le hachage pour).

Cela signifie que vous voulez qu'il ne soit pas susceptible d'avoir le même résultat, et vous aimeriez probablement aussi que la fonction de hachage soit rapide.

Équilibrer ces deux propriétés (et quelques autres) a occupé de nombreuses personnes!

Dans la pratique, vous devriez généralement être en mesure de trouver une fonction qui fonctionne bien pour votre application et de l'utiliser.

Maintenant, pour que cela fonctionne comme une table de hachage: imaginez que vous ne vous souciez pas de l'utilisation de la mémoire. Ensuite, vous pouvez créer un tableau aussi longtemps que votre ensemble d'indexation (tous les uint32, par exemple). Lorsque vous ajoutez quelque chose à la table, vous hachez sa clé et examinez le tableau à cet index. S'il n'y a rien, vous y mettez votre valeur. S'il y a déjà quelque chose, vous ajoutez cette nouvelle entrée à une liste de choses à cette adresse, ainsi que suffisamment d'informations (votre clé d'origine ou quelque chose d'intelligent) pour trouver quelle entrée appartient réellement à quelle clé.

Donc, au fur et à mesure que vous avancez, chaque entrée de votre table de hachage (le tableau) est soit vide, soit contient une entrée, ou une liste d'entrées. La récupération est aussi simple que l'indexation dans le tableau, et soit le retour de la valeur, soit la lecture de la liste de valeurs et le retour de la bonne.

Bien sûr, en pratique, vous ne pouvez généralement pas faire cela, cela gaspille trop de mémoire. Donc, vous faites tout basé sur un tableau clairsemé (où les seules entrées sont celles que vous utilisez réellement, tout le reste est implicitement nul).

Il existe de nombreux schémas et astuces pour améliorer le fonctionnement, mais ce sont les bases.

Simon
la source
1
Désolé, je sais que c'est une vieille question / réponse, mais j'ai essayé de comprendre ce dernier point que vous faites. Une table de hachage a une complexité temporelle O (1). Cependant, une fois que vous utilisez un tableau fragmenté, ne vous reste-t-il pas besoin de faire une recherche binaire pour trouver votre valeur? À ce stade, la complexité temporelle ne devient-elle pas O (log n)?
herbrandson
@herbrandson: non ... un tableau clairsemé signifie simplement que relativement peu d'indices ont été remplis avec des valeurs - vous pouvez toujours indexer directement à l'élément de tableau spécifique pour la valeur de hachage que vous avez calculée à partir de votre clé; Pourtant, l'implémentation de tableaux clairsemés que Simon décrit n'est sensée que dans des circonstances très limitées: lorsque les tailles de compartiment sont de l'ordre des tailles de page de mémoire (par exemple, les intclés à une densité de 1 sur 1000 et 4 000 pages = la plupart des pages touchées), et lorsque le système d'exploitation traite efficacement toutes les pages 0 (de sorte que les pages de tous les compartiments inutilisés n'ont pas besoin de mémoire de sauvegarde), lorsque l'espace d'adressage est abondant ....
Tony Delroy
@TonyDelroy - c'est vrai que c'est une simplification excessive mais l'idée était de donner un aperçu de ce qu'ils sont et pourquoi, pas une mise en œuvre pratique. Les détails de ce dernier sont plus nuancés, comme vous le dites dans votre extension.
Simon
48

Beaucoup de réponses, mais aucune n'est très visuelle , et les tables de hachage peuvent facilement "cliquer" lorsqu'elles sont visualisées.

Les tables de hachage sont souvent implémentées sous forme de tableaux de listes liées. Si nous imaginons un tableau stockant les noms des personnes, après quelques insertions, il pourrait être présenté en mémoire comme ci-dessous, où les ()chiffres fermés sont des valeurs de hachage du texte / nom.

bucket#  bucket content / linked list

[0]      --> "sue"(780) --> null
[1]      null
[2]      --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null
[3]      --> "mary"(73) --> null
[4]      null
[5]      --> "masayuki"(75) --> "sarwar"(105) --> null
[6]      --> "margaret"(2626) --> null
[7]      null
[8]      --> "bob"(308) --> null
[9]      null

Quelques points:

  • chacune des entrées du tableau (indices [0], [1]...) est connue sous le nom de bucket , et démarre une liste de valeurs liées - éventuellement vide - (alias éléments , dans cet exemple - noms de personnes )
  • chaque valeur (par exemple "fred"avec un hachage 42) est liée à partir d'un seau, [hash % number_of_buckets]par exemple 42 % 10 == [2]; %est l' opérateur modulo - le reste lorsqu'il est divisé par le nombre de compartiments
  • plusieurs valeurs de données peuvent entrer en collision et être liées à partir du même compartiment, le plus souvent parce que leurs valeurs de hachage entrent en collision après l'opération modulo (par exemple 42 % 10 == [2], et 9282 % 10 == [2]), mais parfois parce que les valeurs de hachage sont les mêmes (par exemple "fred"et les "jane"deux sont illustrées par le hachage 42ci-dessus)
    • la plupart des tables de hachage gèrent les collisions - avec des performances légèrement réduites mais pas de confusion fonctionnelle - en comparant la valeur complète (ici le texte) d'une valeur recherchée ou insérée à chaque valeur déjà dans la liste chaînée dans le compartiment haché

Les longueurs des listes liées se rapportent au facteur de charge et non au nombre de valeurs

Si la taille de la table augmente, les tables de hachage implémentées comme ci-dessus ont tendance à se redimensionner (c.-à-d. Créer un plus grand tableau de compartiments, créer des listes liées nouvelles / mises à jour à partir de là, supprimer l'ancien tableau) pour conserver le rapport des valeurs aux compartiments (aka charger facteur ) quelque part dans la plage de 0,5 à 1,0.

Hans donne la formule réelle pour les autres facteurs de charge dans un commentaire ci-dessous, mais pour les valeurs indicatives: avec le facteur de charge 1 et une fonction de hachage de la force cryptographique, 1 / e (~ 36,8%) des seaux auront tendance à être vides, un autre 1 / e (~ 36,8%) ont un élément, 1 / (2e) ou ~ 18,4% deux éléments, 1 / (3! E) environ 6,1% trois éléments, 1 / (4! E) ou ~ 1,5% quatre éléments, 1 / (5! E) ~ .3% en ont cinq, etc. - la longueur moyenne de la chaîne des godets non vides est de ~ 1,58 quel que soit le nombre d'éléments dans le tableau (c'est-à-dire s'il y a 100 éléments et 100 godets, ou 100 millions éléments et 100 millions de compartiments), c'est pourquoi nous disons que la recherche / insertion / effacement sont des opérations à temps constant O (1) .

Comment une table de hachage peut associer des clés à des valeurs

Étant donné une implémentation de table de hachage comme décrit ci-dessus, nous pouvons imaginer créer un type de valeur tel que struct Value { string name; int age; };, et une comparaison d'égalité et des fonctions de hachage qui ne regardent que le namechamp (en ignorant l'âge), puis quelque chose de merveilleux se produit: nous pouvons stocker des Valueenregistrements comme {"sue", 63}dans la table , puis recherchez plus tard "poursuivre" sans connaître son âge, trouvez la valeur stockée et récupérez ou même mettez à jour son âge
- joyeux anniversaire Sue - ce qui, de façon intéressante, ne change pas la valeur de hachage et ne nécessite donc pas de déplacer l'enregistrement de Sue vers un autre seau.

Lorsque nous faisons cela, nous utilisons la table de hachage comme un conteneur associatif aka map , et les valeurs qu'il stocke peuvent être considérées comme consistant en une clé (le nom) et un ou plusieurs autres champs encore appelés - confus - la valeur ( dans mon exemple, juste l'âge). Une implémentation de table de hachage utilisée comme carte est connue sous le nom de carte de hachage .

Cela contraste avec l'exemple plus haut dans cette réponse où nous avons stocké des valeurs discrètes comme "sue", que vous pourriez considérer comme étant sa propre clé: ce type d'utilisation est connu comme un ensemble de hachage .

Il existe d'autres façons d'implémenter une table de hachage

Toutes les tables de hachage n'utilisent pas de listes chaînées (connues sous le nom de chaînage séparé ), mais la plupart des applications générales le font, car la principale alternative de hachage fermé (aka adressage ouvert ) - en particulier avec les opérations d'effacement prises en charge - a des propriétés de performance moins stables avec des clés sujettes aux collisions / fonctions de hachage.


Quelques mots sur les fonctions de hachage

Hachage fort ...

La fonction de hachage minimisant les collisions dans le pire des cas est de pulvériser les clés autour des compartiments de la table de hachage de manière efficace et aléatoire, tout en générant toujours la même valeur de hachage pour la même clé. Même un bit qui change n'importe où dans la clé inverserait idéalement - au hasard - environ la moitié des bits de la valeur de hachage résultante.

Ceci est normalement orchestré avec des mathématiques trop compliquées pour moi. Je mentionnerai un moyen facile à comprendre - pas le plus évolutif ou le plus convivial pour le cache mais intrinsèquement élégant (comme le cryptage avec un tampon unique!) - car je pense qu'il aide à ramener à la maison les qualités souhaitables mentionnées ci-dessus. Supposons que vous hachiez des bits 64 bits double- vous pouvez créer 8 tables de 256 nombres aléatoires chacun (code ci-dessous), puis utiliser chaque tranche de 8 bits / 1 octet de la doublereprésentation mémoire du pour indexer dans une table différente, en XORant la nombres aléatoires que vous recherchez. Avec cette approche, il est facile de voir qu'un peu (dans le sens des chiffres binaires) changer n'importe où dans les doublerésultats, un nombre aléatoire différent est recherché dans l'une des tables et une valeur finale totalement non corrélée.

// note caveats above: cache unfriendly (SLOW) but strong hashing...
size_t random[8][256] = { ...random data... };
const char* p = (const char*)&my_double;
size_t hash = random[0][p[0]] ^ random[1][p[1]] ^ ... ^ random[7][p[7]];

Hachage faible mais souvent rapide ...

De nombreuses fonctions de hachage de bibliothèques transmettent des entiers inchangés (connus sous le nom de fonction de hachage triviale ou d' identité ); c'est l'autre extrême du hachage fort décrit ci-dessus. Un hachage d'identité est extrêmementsujettes aux collisions dans les pires cas, mais l'espoir est que dans le cas assez commun des clés entières qui ont tendance à être incrémentées (peut-être avec quelques lacunes), elles seront mappées en compartiments successifs laissant moins de vide que les feuilles de hachage aléatoires (notre ~ 36,8 % au facteur de charge 1 mentionné ci-dessus), ce qui entraîne moins de collisions et moins de listes chaînées plus longues d'éléments en collision que ne le permettent les mappages aléatoires. Il est également idéal de gagner du temps pour générer un hachage fort, et si les clés sont recherchées afin qu'elles soient trouvées dans des compartiments à proximité en mémoire, améliorant les accès au cache. Lorsque les clés n'augmentent pas correctement, l'espoir est qu'elles seront suffisamment aléatoires, elles n'auront pas besoin d'une fonction de hachage forte pour randomiser totalement leur placement dans des compartiments.

Tony Delroy
la source
6
Permettez-moi de dire: réponse fantastique.
CRThaze
@Tony Delroy Merci pour la réponse étonnante. J'ai encore un point ouvert dans mon esprit. Vous dites que même s'il y a 100 millions de compartiments, le temps de recherche serait O (1) avec le facteur de charge 1 et une fonction de hachage de la force cryptographique. Mais qu'en est-il de trouver le bon seau dans 100 millions? Même si tous les seaux sont triés, n'est-ce pas O (log100.000.000)? Comment trouver le seau O (1)?
selman
@selman: votre question ne fournit pas beaucoup de détails pour expliquer pourquoi vous pensez que cela pourrait être O (log100,000,000), mais vous dites "même si nous avons tous les compartiments triés" - gardez à l'esprit que les valeurs dans les compartiments de table de hachage ne sont jamais "triés" au sens habituel: quelle valeur apparaît dans quel compartiment est déterminé en appliquant la fonction de hachage à la clé. Penser que la complexité est O (log100,000,000) implique que vous imaginez faire une recherche binaire à travers des compartiments triés, mais ce n'est pas ainsi que fonctionne le hachage. Peut-être lisez quelques-unes des autres réponses et voyez si cela commence à avoir plus de sens.
Tony Delroy
@TonyDelroy En effet, les "seaux triés" sont le meilleur scénario que j'imagine. D'où O (log100 000 000). Mais si ce n'est pas le cas, comment l'application peut-elle trouver un compartiment connexe parmi des millions? La fonction de hachage génère-t-elle en quelque sorte un emplacement de mémoire?
selman
1
@selman: parce que la mémoire de l'ordinateur permet un "accès aléatoire" à temps constant: si vous pouvez calculer une adresse mémoire, vous pouvez récupérer le contenu de la mémoire sans avoir à accéder à la mémoire dans d'autres parties du tableau. Ainsi, que vous accédiez au premier compartiment, au dernier compartiment ou à un compartiment n'importe où entre les deux, il aura les mêmes caractéristiques de performances (sans prendre le même temps, bien que soumis aux impacts de mise en cache de la mémoire CPU L1 / L2 / L3 mais ils ne fonctionnent que pour vous aider à accéder rapidement aux compartiments récemment accédés ou à proximité, et peuvent être ignorés pour l'analyse big-O).
Tony Delroy
24

Vous êtes très près d'expliquer cela en détail, mais vous manquez quelques choses. La table de hachage n'est qu'un tableau. Le tableau lui-même contiendra quelque chose dans chaque emplacement. Au minimum, vous stockerez la valeur de hachage ou la valeur elle-même dans cet emplacement. En plus de cela, vous pouvez également stocker une liste liée / chaînée de valeurs qui sont entrées en collision sur cet emplacement, ou vous pouvez utiliser la méthode d'adressage ouvert. Vous pouvez également stocker un pointeur ou des pointeurs vers d'autres données que vous souhaitez extraire de cet emplacement.

Il est important de noter que la valeur de hachage elle-même n'indique généralement pas l'emplacement dans lequel placer la valeur. Par exemple, une valeur de hachage peut être une valeur entière négative. De toute évidence, un nombre négatif ne peut pas pointer vers un emplacement de tableau. De plus, les valeurs de hachage auront tendance à être plusieurs fois plus grandes que les emplacements disponibles. Ainsi, un autre calcul doit être effectué par la table de hachage elle-même pour déterminer dans quel emplacement la valeur doit entrer. Cela se fait avec une opération mathématique de module comme:

uint slotIndex = hashValue % hashTableSize;

Cette valeur est l'emplacement dans lequel la valeur ira. Dans l'adressage ouvert, si l'emplacement est déjà rempli avec une autre valeur de hachage et / ou d'autres données, l'opération de module sera exécutée à nouveau pour trouver l'emplacement suivant:

slotIndex = (remainder + 1) % hashTableSize;

Je suppose qu'il peut y avoir d'autres méthodes plus avancées pour déterminer l'index des emplacements, mais c'est la plus courante que j'ai vue ... serait intéressé par d'autres qui fonctionnent mieux.

Avec la méthode du module, si vous avez une table de disons taille 1000, toute valeur de hachage comprise entre 1 et 1000 ira dans l'emplacement correspondant. Toutes les valeurs négatives et toutes les valeurs supérieures à 1 000 seront potentiellement des valeurs d'emplacement en collision. Les chances que cela se produise dépendent à la fois de votre méthode de hachage et du nombre total d'éléments que vous ajoutez à la table de hachage. En règle générale, il est préférable de définir la taille de la table de hachage de telle sorte que le nombre total de valeurs qui y sont ajoutées ne soit égal qu'à environ 70% de sa taille. Si votre fonction de hachage fait un bon travail de distribution uniforme, vous rencontrerez généralement très peu ou pas de collisions de compartiment / emplacement et elle fonctionnera très rapidement pour les opérations de recherche et d'écriture. Si le nombre total de valeurs à ajouter n'est pas connu à l'avance, faites une bonne estimation par n'importe quel moyen,

J'espère que cela a aidé.

PS - En C #, la GetHashCode()méthode est assez lente et entraîne des collisions de valeurs réelles dans de nombreuses conditions que j'ai testées. Pour vous amuser vraiment, créez votre propre fonction de hachage et essayez de ne jamais heurter les données spécifiques que vous hachez, exécutez plus rapidement que GetHashCode et ayez une distribution assez uniforme. J'ai fait cela en utilisant des valeurs de code de hachage longues au lieu de la taille int et cela a très bien fonctionné sur jusqu'à 32 millions d'entités de valeurs de hachage dans la table de hachage avec 0 collision. Malheureusement, je ne peux pas partager le code car il appartient à mon employeur ... mais je peux révéler qu'il est possible pour certains domaines de données. Lorsque vous pouvez y parvenir, la table de hachage est TRÈS rapide. :)

Chris
la source
Je sais que le message est assez ancien, mais quelqu'un peut-il expliquer ce que (reste + 1) signifie ici
Hari
3
@Hari remainderfait référence au résultat du calcul du module d'origine, et nous y ajoutons 1 afin de trouver le prochain emplacement disponible.
x4nd3r
"Le tableau lui-même contiendra quelque chose dans chaque emplacement. Au minimum, vous stockerez la valeur de hachage ou la valeur elle-même dans cet emplacement." - il est courant que les "slots" (compartiments) ne stockent aucune valeur; Les implémentations d'adressage ouvert stockent souvent NULL ou un pointeur vers le premier nœud dans une liste liée - sans valeur directement dans le slot / bucket. "serait intéressé par d'autres" - le "+1" que vous illustrez est appelé palpage linéaire , souvent plus performant: palpage quadratique . "rencontre généralement très peu ou pas de collisions de seaux / emplacements" - @ 70% de capacité, ~ 12% d'emplacements avec 2 valeurs, ~ 3% 3 ....
Tony Delroy
"J'ai fait cela en utilisant des valeurs de code de hachage longues au lieu de taille int et cela a très bien fonctionné sur jusqu'à 32 millions d'entités de valeurs de hachage dans la table de hachage avec 0 collision." - cela n'est tout simplement pas possible dans le cas général où les valeurs des clés sont effectivement aléatoires dans une plage beaucoup plus grande que le nombre de compartiments. Notez qu'avoir des valeurs de hachage distinctes est souvent assez facile (et votre discussion sur longles valeurs de hachage implique que c'est ce que vous avez réalisé), mais vous assurer qu'elles ne se heurtent pas dans la table de hachage après que l'opération mod /% ne l'est pas (dans le cas général ).
Tony Delroy
(Éviter toutes les collisions est connu sous le nom de hachage parfait . En général, il est pratique pour quelques centaines ou milliers de clés connues à l'avance - gperf est un exemple d'outil pour calculer une telle fonction de hachage. Vous pouvez également écrire la vôtre en très limité circonstances - par exemple, si vos clés sont des pointeurs vers des objets de votre propre pool de mémoire qui est assez plein, avec chaque pointeur à une distance fixe, vous pouvez diviser les pointeurs par cette distance et avoir effectivement un index dans un tableau légèrement clairsemé, en évitant collisions.)
Tony Delroy
17

Voici comment cela fonctionne dans ma compréhension:

Voici un exemple: imaginez la table entière comme une série de compartiments. Supposons que vous ayez une implémentation avec des codes de hachage alphanumériques et ayez un compartiment pour chaque lettre de l'alphabet. Cette implémentation place chaque élément dont le code de hachage commence par une lettre particulière dans le compartiment correspondant.

Disons que vous avez 200 objets, mais seulement 15 d'entre eux ont des codes de hachage qui commencent par la lettre «B». La table de hachage aurait seulement besoin de rechercher et de rechercher parmi les 15 objets dans le compartiment «B», plutôt que les 200 objets.

En ce qui concerne le calcul du code de hachage, il n'y a rien de magique à ce sujet. Le but est simplement que différents objets renvoient des codes différents et que des objets égaux renvoient des codes égaux. Vous pouvez écrire une classe qui renvoie toujours le même entier qu'un code de hachage pour toutes les instances, mais vous détruiriez essentiellement l'utilité d'une table de hachage, car elle deviendrait simplement un seau géant.

AndreiM
la source
13

Court et doux:

Une table de hachage enveloppe un tableau, appelons-le internalArray. Les éléments sont insérés dans le tableau de cette manière:

let insert key value =
    internalArray[hash(key) % internalArray.Length] <- (key, value)
    //oversimplified for educational purposes

Parfois, deux clés hachent le même index dans le tableau et vous souhaitez conserver les deux valeurs. J'aime stocker les deux valeurs dans le même index, ce qui est simple à coder en créant internalArrayun tableau de listes liées:

let insert key value =
    internalArray[hash(key) % internalArray.Length].AddLast(key, value)

Donc, si je voulais récupérer un élément de ma table de hachage, je pourrais écrire:

let get key =
    let linkedList = internalArray[hash(key) % internalArray.Length]
    for (testKey, value) in linkedList
        if (testKey = key) then return value
    return null

Les opérations de suppression sont tout aussi simples à écrire. Comme vous pouvez le constater, les insertions, les recherches et la suppression de notre tableau de listes liées sont presque O (1).

Lorsque notre tableau interne est trop plein, peut-être à environ 85% de sa capacité, nous pouvons redimensionner le tableau interne et déplacer tous les éléments de l'ancien tableau vers le nouveau tableau.

Juliette
la source
11

C'est encore plus simple que ça.

Une table de hachage n'est rien de plus qu'un tableau (généralement clairsemé ) de vecteurs qui contiennent des paires clé / valeur. La taille maximale de ce tableau est généralement inférieure au nombre d'éléments dans l'ensemble de valeurs possibles pour le type de données stockées dans la table de hachage.

L'algorithme de hachage est utilisé pour générer un index dans ce tableau en fonction des valeurs de l'élément qui sera stocké dans le tableau.

C'est là que le stockage des vecteurs de paires clé / valeur dans le tableau entre en jeu. Étant donné que l'ensemble de valeurs pouvant être des index dans le tableau est généralement plus petit que le nombre de toutes les valeurs possibles que le type peut avoir, il est possible que votre hachage algorithme va générer la même valeur pour deux clés distinctes. Un bon algorithme de hachage évitera cela autant que possible (c'est pourquoi il est relégué au type généralement parce qu'il contient des informations spécifiques qu'un algorithme de hachage général ne peut probablement pas connaître), mais il est impossible de les empêcher.

Pour cette raison, vous pouvez avoir plusieurs clés qui généreront le même code de hachage. Lorsque cela se produit, les éléments du vecteur sont itérés et une comparaison directe est effectuée entre la clé du vecteur et la clé recherchée. S'il est trouvé, grand et la valeur associée à la clé est retournée, sinon, rien n'est retourné.

casperOne
la source
10

Vous prenez un tas de choses et un tableau.

Pour chaque chose, vous en faites un index, appelé hachage. L'important à propos du hachage est qu'il «se disperse» beaucoup; vous ne voulez pas que deux choses similaires aient des hachages similaires.

Vous placez vos objets dans le tableau à la position indiquée par le hachage. Plus d'une chose peut se retrouver à un hachage donné, vous stockez donc les choses dans des tableaux ou quelque chose d'autre approprié, que nous appelons généralement un seau.

Lorsque vous recherchez des éléments dans le hachage, vous suivez les mêmes étapes, déterminez la valeur du hachage, puis voyez ce qu'il y a dans le seau à cet emplacement et vérifiez si c'est ce que vous recherchez.

Lorsque votre hachage fonctionne bien et que votre tableau est suffisamment grand, il n'y aura que quelques éléments au maximum dans un index particulier du tableau, vous n'aurez donc pas à regarder beaucoup.

Pour les points bonus, faites en sorte que lorsque votre table de hachage est accédée, elle déplace la chose trouvée (le cas échéant) au début du compartiment, donc la prochaine fois c'est la première chose vérifiée.

le chaos
la source
1
merci pour le dernier point que tout le monde a oublié de mentionner
Sandeep Raju Prabhakar
4

Jusqu'à présent, toutes les réponses sont bonnes et abordent différents aspects du fonctionnement d'une table de hachage. Voici un exemple simple qui pourrait être utile. Disons que nous voulons stocker certains éléments avec des chaînes alphabétiques en minuscules comme clés.

Comme Simon l'a expliqué, la fonction de hachage est utilisée pour mapper d'un grand espace à un petit espace. Une implémentation simple et naïve d'une fonction de hachage pour notre exemple pourrait prendre la première lettre de la chaîne et la mapper à un entier, donc "alligator" a un code de hachage de 0, "bee" a un code de hachage de 1, " zèbre "serait de 25, etc.

Ensuite, nous avons un tableau de 26 compartiments (pourrait être ArrayLists en Java), et nous mettons l'élément dans le compartiment qui correspond au code de hachage de notre clé. Si nous avons plusieurs éléments dont la clé commence par la même lettre, ils auront le même code de hachage, donc tous iront dans le compartiment pour ce code de hachage, de sorte qu'une recherche linéaire devra être effectuée dans le compartiment pour trouver un élément particulier.

Dans notre exemple, si nous n'avions que quelques dizaines d'éléments avec des clés couvrant l'alphabet, cela fonctionnerait très bien. Cependant, si nous avions un million d'articles ou que toutes les clés commençaient toutes par «a» ou «b», notre table de hachage ne serait pas idéale. Pour obtenir de meilleures performances, nous aurions besoin d'une fonction de hachage différente et / ou de plusieurs compartiments.

Greg Graham
la source
3

Voici une autre façon de voir les choses.

Je suppose que vous comprenez le concept d'un tableau A. C'est quelque chose qui prend en charge l'opération d'indexation, où vous pouvez accéder à l'élément Ith, A [I], en une seule étape, quelle que soit la taille de A.

Ainsi, par exemple, si vous souhaitez stocker des informations sur un groupe de personnes qui ont toutes des âges différents, un moyen simple serait d'avoir un tableau suffisamment grand et d'utiliser l'âge de chaque personne comme index dans le tableau. De cette façon, vous pouvez avoir un accès en une seule étape aux informations de toute personne.

Mais bien sûr, il peut y avoir plus d'une personne du même âge, donc ce que vous mettez dans le tableau à chaque entrée est une liste de toutes les personnes qui ont cet âge. Ainsi, vous pouvez accéder aux informations d'une personne individuelle en une seule étape, plus un peu de recherche dans cette liste (appelée "bucket"). Cela ne ralentit que s'il y a tellement de monde que les seaux deviennent gros. Ensuite, vous avez besoin d'un tableau plus large et d'un autre moyen d'obtenir plus d'informations d'identification sur la personne, comme les premières lettres de son nom de famille, au lieu d'utiliser l'âge.

Voilà l'idée de base. Au lieu d'utiliser l'âge, toute fonction de la personne qui produit une bonne répartition des valeurs peut être utilisée. C'est la fonction de hachage. Comme si vous pouviez prendre chaque troisième bit de la représentation ASCII du nom de la personne, brouillé dans un certain ordre. Tout ce qui compte, c'est que vous ne voulez pas que trop de personnes hachent vers le même godet, car la vitesse dépend des godets qui restent petits.

Mike Dunlavey
la source
2

La façon dont le hachage est calculé ne dépend généralement pas de la table de hachage, mais des éléments qui y sont ajoutés. Dans les bibliothèques de frameworks / classes de base telles que .net et Java, chaque objet a une méthode GetHashCode () (ou similaire) renvoyant un code de hachage pour cet objet. L'algorithme de code de hachage idéal et l'implémentation exacte dépendent des données représentées par dans l'objet.

Lucero
la source
2

Une table de hachage fonctionne totalement sur le fait que le calcul pratique suit le modèle de machine à accès aléatoire, c'est-à-dire que la valeur à n'importe quelle adresse en mémoire est accessible en temps O (1) ou en temps constant.

Donc, si j'ai un univers de clés (ensemble de toutes les clés possibles que je peux utiliser dans une application, par exemple, n ° de rouleau pour étudiant, s'il est à 4 chiffres, cet univers est un ensemble de nombres de 1 à 9999), et un façon de les mapper à un ensemble fini de nombres de taille, je peux allouer de la mémoire dans mon système, théoriquement ma table de hachage est prête.

Généralement, dans les applications, la taille de l'univers des clés est très grande par rapport au nombre d'éléments que je souhaite ajouter à la table de hachage (je ne veux pas gaspiller une mémoire de 1 Go pour hacher, disons, 10000 ou 100000 valeurs entières car elles sont 32 peu long en représentation binaire). Donc, nous utilisons ce hachage. C'est une sorte d'opération "mathématique" de mélange, qui mappe mon grand univers à un petit ensemble de valeurs que je peux adapter en mémoire. Dans les cas pratiques, souvent l'espace d'une table de hachage est du même "ordre" (big-O) que le (nombre d'éléments * taille de chaque élément), donc, nous ne gaspillons pas beaucoup de mémoire.

Maintenant, un grand ensemble mappé à un petit ensemble, le mappage doit être plusieurs-à-un. Ainsi, différentes clés se verront attribuer le même espace (?? pas juste). Il y a plusieurs façons de gérer cela, je connais juste les deux populaires:

  • Utilisez l'espace qui devait être alloué à la valeur comme référence à une liste liée. Cette liste chaînée stockera une ou plusieurs valeurs, qui résideront dans le même emplacement dans plusieurs mappages. La liste chaînée contient également des clés pour aider quelqu'un qui vient chercher. C'est comme beaucoup de gens dans le même appartement, quand un livreur arrive, il va dans la chambre et demande spécifiquement le gars.
  • Utilisez une fonction de hachage double dans un tableau qui donne la même séquence de valeurs à chaque fois plutôt qu'une seule valeur. Lorsque je vais enregistrer une valeur, je vois si l'emplacement mémoire requis est libre ou occupé. Si c'est gratuit, je peux y stocker ma valeur, s'il est occupé, je prends la valeur suivante de la séquence et ainsi de suite jusqu'à ce que je trouve un emplacement libre et j'y stocke ma valeur. Lors de la recherche ou de la récupération de la valeur, je reviens sur le même chemin que celui indiqué par la séquence et à chaque emplacement, je demande la valeur si elle est là jusqu'à ce que je la trouve ou que je recherche tous les emplacements possibles dans le tableau.

L'introduction aux algorithmes par CLRS fournit un très bon aperçu du sujet.

div
la source
0

Pour tous ceux qui recherchent le langage de programmation, voici comment cela fonctionne. L'implémentation interne des tables de hachage avancées présente de nombreuses subtilités et optimisations pour l'allocation / désallocation de stockage et la recherche, mais l'idée de niveau supérieur sera très similaire.

(void) addValue : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   if (bucket) 
   {
       //do nothing, just overwrite
   }
   else   //create bucket
   {
      create_extra_space_for_bucket();
   }
   put_value_into_bucket(bucket,value);
}

(bool) exists : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   return bucket;
}

calculate_bucket_from_val()est la fonction de hachage où toute la magie d'unicité doit se produire.

La règle générale est la suivante: pour qu'une valeur donnée soit insérée, le compartiment doit être UNIQUE ET DÉRIVÉ DE LA VALEUR qu'il est censé STOCKER.

Bucket est n'importe quel espace où les valeurs sont stockées - car ici je l'ai gardé comme un index de tableau, mais c'est peut-être aussi un emplacement de mémoire.

Nirav Bhatt
la source
1
"La règle générale est la suivante: pour qu'une valeur donnée soit insérée, le compartiment doit être UNIQUE ET DÉRIVÉ DE LA VALEUR qu'il est censé STOCKER." - cela décrit une fonction de hachage parfaite , qui n'est généralement possible que pour quelques centaines ou milliers de valeurs connues au moment de la compilation. La plupart des tables de hachage doivent gérer les collisions . De plus, les tables de hachage ont tendance à allouer de l'espace pour tous les compartiments, qu'ils soient vides ou non, tandis que votre pseudo-code documente une create_extra_space_for_bucket()étape lors de l'insertion de nouvelles clés. Les seaux peuvent cependant être des pointeurs.
Tony Delroy