Comment fonctionne une table de hachage?

Je cherche une explication de la façon dont une table de hachage fonctionne – en anglais simple pour un simple comme moi!

Par exemple, je sais qu’il prend la clé, calcule le hash (je cherche une explication comment) et effectue ensuite 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 mes connaissances s’arrêtent .

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.

Voici une explication en termes simples.

Supposons que vous vouliez remplir une bibliothèque de livres et pas seulement les y insérer, mais vous voulez 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, alors c’est tout ce que cela devrait prendre. Avec le titre, la personne, avec l’aide du bibliothécaire, devrait pouvoir trouver le livre facilement et rapidement.

Alors, comment peux-tu faire ça? Eh bien, évidemment, vous pouvez garder une sorte de liste de l’endroit où vous mettez chaque livre, mais vous avez alors 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 souhaitez toujours pas effectuer une recherche séquentielle d’un bout de la bibliothèque (ou de la liste) à l’autre.

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

Mais comment cela peut-il être fait? Eh bien, avec un peu de prévoyance 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 créez une petite méthode intelligente. Vous prenez le titre du livre, exécutez-le dans 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, quand une personne revient lire le livre, vous alimentez le titre une fois de plus dans le programme et récupérez le même numéro d’étagère et le même numéro d’emplacement que vous avez reçu à l’origine. où se trouve le livre.

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

Par souci de simplicité, supposons que chaque lettre et chaque symbole soient convertis en un nombre et qu’ils soient tous cumulés. En réalité, c’est beaucoup plus compliqué que cela, mais laissez-le pour le moment.

La beauté d’un tel algorithme est que si vous alimentez la même entrée à plusieurs resockets, il continuera à cracher le même numéro à chaque fois.

Ok, donc c’est fondamentalement la façon dont fonctionne une table de hachage.

Le matériel technique suit.

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, supposons que nous ayons de la place pour exactement un million de livres dans la bibliothèque. La sortie du calcul de hachage pourrait être comprise entre 0 et 1 milliard, ce qui est beaucoup plus élevé.

Alors que faisons-nous? Nous utilisons quelque chose appelé le calcul du module, qui dit essentiellement que si vous comptiez jusqu’au nombre que vous vouliez (c’est-à-dire le milliard), mais que vous vouliez restr dans une plage beaucoup plus petite, 0, mais vous devez garder une trace de la distance parcourue dans la grande séquence.

Supposons que la sortie de l’algorithme de hachage se situe entre 0 et 20 et que vous obtenez la valeur 17 d’un titre particulier. Si la taille de la bibliothèque est seulement de 7 livres, vous comptez 1, 2, 3, 4, 5, 6 et à 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 n’est pas fait comme ça, c’est fait avec la division et le rest. Le rest de la division de 17 par 7 est 3 (7 va 2 fois en 17 à 14 et la différence entre 17 et 14 est 3).

Ainsi, vous mettez le livre dans le logement numéro 3.

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

Diverses méthodes de gestion des collisions existent, y compris exécuter les données dans un autre calcul pour obtenir un autre point dans la table ( double hachage ) ou simplement pour trouver un espace proche de celui qui vous a été donné (c.-à-d. était disponible également connu sous le nom de sondage linéaire ). Cela signifierait que vous avez du mal à 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 placer plus de livres dans la bibliothèque que ne le permet la bibliothèque. En d’autres termes, vous devez construire une bibliothèque plus grande. Comme le point exact de 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 devrez peut-être trouver de nouveaux emplacements pour tous les livres depuis le calcul effectué. a changé.

J’espère que cette explication était un peu plus terre à terre que les seaux et les fonctions 🙂

Usage et Lingo:

  1. Les tables de hachage permettent de stocker et de récupérer rapidement des données (ou des 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 contenue dans l’enregistrement. Cette valeur choisie doit être une valeur commune à tous les enregistrements.
  4. Chaque compartiment peut avoir plusieurs enregistrements organisés dans un ordre particulier.

Exemple de monde réel:

Hash & Co. , fondée en 1803 et dépourvue de toute technologie informatique, comptait au total 300 classeurs pour conserver les informations détaillées (les registres) de ses quelque 30 000 clients. Chaque dossier a été clairement identifié avec son numéro unique de 0 à 299.

Les préposés au classement de l’époque devaient chercher et stocker rapidement les dossiers des clients pour le personnel en activité. Le personnel avait décidé qu’il serait plus efficace d’utiliser une méthode de hachage pour stocker et récupérer leurs enregistrements.

Pour classer un dossier client, les commis au classement utilisent le numéro de client unique inscrit dans le dossier. En utilisant ce numéro de client, ils moduleraient la clé de hachage de 300 afin d’identifier le classeur dans lequel ils se trouvent. Lorsqu’ils ont ouvert le classeur, ils découvriraient qu’il contenait de nombreux dossiers commandés par numéro de client. Après avoir identifié le bon emplacement, ils le glisseraient simplement

Pour récupérer un dossier de client, les commis au classement recevraient un numéro de client sur un bout de papier. En utilisant ce numéro de client unique, ils le moduleraient par 300 (la clé de hachage ) afin de déterminer le classeur contenant le dossier des clients. Lorsqu’ils ont ouvert le classeur, ils ont découvert qu’il contenait de nombreux dossiers commandés par numéro de client. En parcourant les enregistrements, ils trouvaient rapidement le dossier du client et le récupéraient.

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


Une chose importante à retenir est que les ordinateurs (et leurs algorithmes) traitent mieux les nombres que les chaînes. L’access à un grand tableau à l’aide d’un index est donc beaucoup plus rapide que l’access séquentiel.

Comme Simon l’a mentionné, il est très important que la partie de hachage transforme un grand espace (de longueur arbitraire, généralement des chaînes, etc.) et le mappe sur un petit espace (de taille connue, généralement des nombres) pour l’indexation. Ceci est très important à retenir!

Ainsi, dans l’exemple ci-dessus, les quelque 30 000 clients possibles sont associés à un espace plus restreint.


L’idée principale consiste à diviser l’ensemble de vos données en segments afin d’accélérer la recherche, ce qui prend généralement beaucoup de temps. Dans notre exemple ci-dessus, chacun des 300 classeurs contiendrait (statistiquement) environ 100 enregistrements. La recherche (quel que soit l’ordre) sur 100 enregistrements est beaucoup plus rapide que le traitement de 30 000 enregistrements.

Vous avez peut-être remarqué que certains le font déjà. Mais au lieu de concevoir une méthode de hachage pour générer une clé de hachage, ils utiliseront dans la plupart des cas 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!

Cela se révèle être un domaine théorique assez approfondi, mais les grandes lignes sont simples.

Une fonction de hachage est essentiellement une fonction qui prend des choses dans un espace (par exemple 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 à hacher, vous pouvez vous contenter d’interpréter ces choses comme des nombres entiers, et vous avez terminé (par exemple, des chaînes de 4 octets).

Cependant, vous avez généralement beaucoup plus d’espace. Si l’espace que vous autorisez en tant que clés est plus grand que l’espace que vous utilisez pour indexer (celui de votre uint32 ou autre), vous ne pouvez pas avoir une valeur unique pour chacun. Lorsque deux choses ou plus aboutissent au même résultat, vous devrez gérer la redondance de manière appropriée (ceci est généralement appelé collision, et comment vous le manipulez ou ne dépendez pas un peu de ce que vous êtes). en utilisant le hachage pour).

Cela implique que vous ne voulez pas avoir le même résultat, et vous voudriez probablement aussi que la fonction de hachage soit rapide.

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

En pratique, vous devriez normalement être capable 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 n’aimiez pas l’utilisation de la mémoire. Ensuite, vous pouvez créer un tableau aussi longtemps que votre jeu 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 mettez votre valeur là-bas. S’il y a déjà quelque chose, vous ajoutez cette nouvelle entrée à une liste de choses à cette adresse, avec suffisamment d’informations (votre clé d’origine ou quelque chose d’intelligent) pour trouver quelle entrée appartient réellement à quelle clé.

Ainsi, chaque entrée de votre table de hachage (le tableau) est vide ou contient une entrée ou une liste d’entrées. La récupération est simple comme indexation dans le tableau, soit en retournant la valeur, soit en parcourant la liste des valeurs et en renvoyant la bonne.

Bien sûr, dans la pratique, vous ne pouvez généralement pas faire cela, cela gaspille trop de mémoire. Vous faites donc tout ce qui est basé sur un tableau fragmenté (où les seules entrées sont celles que vous utilisez réellement, tout le rest est implicitement nul).

Il existe de nombreux schémas et astuces pour que cela fonctionne mieux, mais ce sont les bases.

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 comme des tableaux de listes liées. Si nous imaginons une table stockant des noms de personnes, après quelques insertions, elle pourrait être mise en mémoire comme ci-dessous, où () – les nombres regroupé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 appelée un compartiment et lance une liste de valeurs – éventuellement vide – liée ( éléments , dans cet exemple – noms de personnes)
  • chaque valeur (par exemple "fred" avec hash 42 ) est liée à un seau [hash % number_of_buckets] par exemple 42 % 10 == [2] ; % est l’opérateur de module – le rest lorsqu’il est divisé par le nombre de compartiments
  • plusieurs valeurs de données peuvent entrer en collision et être liées au même compartiment, le plus souvent parce que leurs valeurs de hachage entrent en collision après l’opération de module (par exemple 42 % 10 == [2] et 9282 % 10 == [2] ) les valeurs de hachage sont les mêmes (par exemple, "fred" et "jane" tous deux affichés avec le hash 42 ci-dessus)
    • La plupart des tables de hachage gèrent les collisions – avec des performances légèrement réduites mais sans confusion fonctionnelle – en comparant la valeur complète (ici le texte) d’une clé recherchée ou insérée à chaque clé déjà présente dans la liste des liens.

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 nombre de compartiments, créer des listes liées nouvelles / mises à jour, supprimer l’ancien tableau) facteur ) quelque part entre 0,5 et 1,0. Avec un facteur de charge 1 et une fonction de hachage de la force cryptographique, 36,8% des godets ont tendance à être vides, 36,8% ont un élément, 18,4% deux éléments, 6,1% trois éléments, 1,5% quatre éléments, – la longueur des listes fait en moyenne 2,0 éléments, quel que soit le nombre d’éléments de la table (soit 100 éléments et 100 seaux, soit 100 millions d’éléments et 100 millions de seaux), ce qui explique pourquoi 1) opérations à temps constant.

(Notes: toutes les tables de hachage n’utilisent pas de listes liées, mais les plus courantes, comme le hachage fermé (adressage ouvert) – en particulier avec les opérations d’effacement sockets en charge – ont des propriétés de performances moins stables avec des touches / fonctions de hachage sujettes aux collisions).

Quelques mots sur les fonctions de hachage

Une fonction de hachage à usage général, minimisant les collisions, consiste à pulvériser les clés autour des compartiments de la table de hachage de manière 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é retournera idéalement, de manière aléatoire, environ la moitié des bits de la valeur de hachage résultante.

Ceci est normalement orchestré avec des maths trop compliquées pour moi. Je mentionnerai une méthode facile à comprendre – pas la plus évolutive ni la plus conviviale pour le cache mais insortingnsèquement élégante (comme le chiffrement avec un bloc-notes unique!) – car cela aide à mettre en évidence les qualités souhaitables mentionnées ci-dessus. Supposons que vous ayez haché des double 64 bits – vous pourriez créer 8 tables de 256 nombres aléatoires (ie size_t random[8][256] ), puis utiliser chaque tranche de 8 bits / 1 octet de la représentation mémoire du double pour indexer dans un tableau différent, en sélectionnant les nombres aléatoires que vous recherchez. Avec cette approche, il est facile de voir qu’un peu de changement dans le double traduit par un nombre aléatoire différent dans l’une des tables, et une valeur finale totalement décorrélée.

Cependant, les fonctions de hachage de nombreuses bibliothèques ne modifient pas les entiers, ce qui est extrêmement susceptible de provoquer des collisions dans les cas les plus défavorables, mais on espère que dans le cas assez courant des clés entières qui s’incrémentent, elles se transforment vide que les feuilles de hachage aléatoire à 36,8%, ce qui a pour effet d’avoir moins de collisions et moins de listes d’éléments de C’est aussi génial de gagner du temps pour générer un hash fort. Lorsque les touches ne s’incrémentent pas bien, l’espoir est qu’elles seront assez aléatoires pour qu’elles n’aient pas besoin d’une fonction de hachage forte pour aléatoirement placer leur position dans des seaux.

Eh bien, c’était moins amusant et plus lourd que l’explication de la table de hachage, mais j’espère que ça aidera quelqu’un …

Vous êtes sur le point d’expliquer cela complètement, mais il vous manque deux choses. La table de hachage est juste 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. En outre, les valeurs de hachage auront tendance à être plusieurs fois supérieures aux intervalles disponibles. La table de hachage doit donc effectuer un autre calcul pour déterminer dans quel emplacement la valeur doit entrer. Ceci est fait avec une opération mathématique de module comme:

 uint slotIndex = hashValue % hashTableSize; 

Cette valeur correspond à l’emplacement dans lequel la valeur entrera. 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 le prochain emplacement:

 slotIndex = (remainder + 1) % hashTableSize; 

Je suppose qu’il existe peut-être d’autres méthodes plus avancées pour déterminer l’indice de créneau, mais c’est la méthode la plus courante que j’ai vue … serait intéressée par d’autres qui fonctionnent mieux.

Avec la méthode du module, si vous avez une table de taille 1000, par exemple, toute valeur de hash comprise entre 1 et 1000 ira dans le logement correspondant. Toutes les valeurs négatives et toutes les valeurs supérieures à 1 000 risquent d’entrer en collision avec les valeurs des intervalles. Les chances que cela se produise dépendent à la fois de votre méthode de hachage et du nombre total d’éléments ajoutés à la table de hachage. En règle générale, il est recommandé de faire en sorte que la taille de la table de hachage soit telle que le nombre total de valeurs ajoutées ne soit que d’environ 70% de sa taille. Si votre fonction de hachage fait un bon travail de dissortingbution uniforme, vous rencontrerez généralement très peu de collisions entre compartiments / emplacements, voire aucune, et elle fonctionnera très rapidement pour les opérations de recherche et d’écriture. Si le nombre total de valeurs à append n’est pas connu à l’avance, faites une bonne estimation en utilisant tous les moyens, puis redimensionnez votre table de hachage une fois que le nombre d’éléments ajoutés atteint 70% de sa capacité.

J’espère que cela a aidé.

PS – En C #, la méthode GetHashCode() est assez lente et entraîne des collisions de valeurs réelles dans de nombreuses conditions que j’ai testées. Pour plus de plaisir, créez votre propre fonction de hachage et essayez de ne JAMAIS entrer en collision avec les données spécifiques que vous avez hachées, exécutez plus rapidement que GetHashCode, et ayez une dissortingbution assez uniforme. Je l’ai fait en utilisant long au lieu de valeurs de hachage de taille int et il a fonctionné assez bien sur jusqu’à 32 millions d’entités hashvalues ​​dans la table de hachage avec 0 collisions. Malheureusement, je ne peux pas partager le code car il appartient à mon employeur … mais je peux vous dire que cela est possible pour certains domaines de données. Lorsque vous pouvez y parvenir, la table de hachage est TRÈS rapide. 🙂

Voilà comment cela fonctionne dans ma compréhension:

Voici un exemple: imaginez la table entière sous la forme d’une série de seaux. Supposons que vous ayez une implémentation avec des codes de hachage alphanumériques et que vous 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 objects, mais seulement 15 d’entre eux ont des codes de hachage commençant par la lettre ‘B.’ La table de hachage n’a besoin que de rechercher et de rechercher parmi les 15 objects du compartiment «B», plutôt que les 200 objects.

En ce qui concerne le calcul du code de hachage, il n’ya rien de magique à ce sujet. L’objective est simplement de faire en sorte que différents objects renvoient des codes différents et que des objects égaux renvoient des codes égaux. Vous pourriez écrire une classe qui retourne 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 ne ferait que devenir un compartiment géant.

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 faisant internalArray un 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, l'insertion, la recherche et la suppression de notre tableau de listes liées est presque O (1).

Lorsque notre interne interne est trop pleine, 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.

C’est encore plus simple que ça.

Une table de hachage n’est rien de plus qu’un tableau (généralement rare ) de vecteurs contenant des paires clé / valeur. La taille maximale de ce tableau est généralement inférieure au nombre d’éléments de l’ensemble de valeurs possibles pour le type de données stocké 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 des paires clé / valeur dans le tableau entre en jeu. Parce que l’ensemble des valeurs pouvant être des index dans le tableau est généralement inférieur au nombre de toutes les valeurs possibles du type, il est possible que votre hachage l’algorithme va générer la même valeur pour deux clés distinctes. Un bon algorithme de hachage permettra d’éviter cela autant que possible (ce qui explique pourquoi il est généralement relégué au type car 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.

De ce fait, 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. Si elle est trouvée, la valeur associée à la clé est renvoyée, sinon rien n’est renvoyé.

Vous prenez un tas de choses, et un tableau.

Pour chaque chose, vous créez un index, appelé hash. L’important à propos du hash est qu’il «diffuse» beaucoup; vous ne voulez pas que deux choses similaires aient des hachages similaires.

Vous mettez vos choses dans le tableau à la position indiquée par le hachage. Plus d’une chose peut arriver à un hachage donné, donc vous stockez les choses dans des tableaux ou autre chose appropriée, ce que nous appelons généralement un compartiment.

Lorsque vous examinez le hachage, vous suivez les mêmes étapes en calculant la valeur du hachage, puis vous voyez ce qui se trouve à cet emplacement et vérifiez si c’est ce que vous recherchez.

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

Pour obtenir des points bonus, faites en sorte que lorsque vous accédez à votre table de hachage, la chose trouvée (le cas échéant) soit déplacée au début du compartiment, la prochaine fois que vous cochez la première case.

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

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 des éléments avec des chaînes alphabétiques minuscules comme clés.

Comme l’explique Simon, la fonction de hachage est utilisée pour mapper un grand espace vers 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 25, etc.

Ensuite, nous avons un tableau de 26 compartiments (ce 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 plus d’un élément qui a une clé qui 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, donc une recherche linéaire devra être faite dans le compartiment pour trouver un article particulier.

Dans notre exemple, si nous avions juste quelques dizaines d’articles avec des clés couvrant l’alphabet, cela fonctionnerait très bien. Cependant, si nous avions un million d’éléments ou si 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.

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 au Iième élément, 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 ayant toutes des âges différents, une méthode simple consisterait à disposer d’un tableau suffisamment grand et à utiliser l’âge de chaque personne comme index dans le tableau. De toute façon, vous pouvez accéder en une seule étape aux informations de toute personne.

Mais bien sûr, il pourrait y avoir plus d’une personne du même âge, de sorte que 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 en une seule étape, plus un peu de recherche dans cette liste (appelée “compartiment”). Cela ralentit seulement s’il y a tellement de personnes que les seaux deviennent gros. Ensuite, vous avez besoin d’un plus grand nombre et d’une autre manière 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.

C’est 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 vous pouvez 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 gens hachent le même seau, car la vitesse dépend des seaux qui restnt petits.

Une table de hachage fonctionne totalement sur le fait que le calcul pratique suit un modèle de machine à access aléatoire, c.-à-d. Que la valeur à n’importe quelle adresse en mémoire est accessible en temps O (1) ou 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 le rouleau n ° pour étudiant, s’il s’agit de 4 chiffres, cet univers est un ensemble de 1 à 9999) façon de les mapper à un ensemble fini de nombres 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 importante par rapport au nombre d’éléments que je souhaite append à la table de hachage (je ne veux pas gaspiller une mémoire de 1 Go pour des valeurs entières de 10000 ou 100000). bit long en reprsentaion binary). Donc, nous utilisons ce hachage. C’est en quelque sorte une opération de type “mathématique” qui associe mon grand univers à un petit ensemble de valeurs que je peux stocker en mémoire. Dans des 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). Ainsi, nous ne gaspillons pas beaucoup de mémoire.

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

  • Utilisez l’espace à atsortingbuer à la valeur en tant que référence à une liste chaînée. Cette liste chaînée stockera une ou plusieurs valeurs, qui viendront résider dans le même emplacement dans plusieurs mappages. La liste chaînée contient également des clés pour aider quelqu’un qui effectue une recherche. 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 type.
  • Utilisez une double fonction de hachage dans un tableau qui donne la même séquence de valeurs à chaque fois plutôt qu’une seule valeur. Lorsque je vais stocker une valeur, je vois si l’emplacement de mémoire requirejs est libre ou occupé. Si c’est gratuit, je peux y stocker ma valeur, si elle est occupée, je prends la valeur suivante de la séquence et ainsi de suite jusqu’à ce que je trouve un emplacement gratuit et que je stocke ma valeur là-bas. Lors de la recherche ou de la recherche de la valeur, je retourne sur le même chemin que celui donné par la séquence et à chaque emplacement, demandez la valeur si elle existe jusqu’à ce que je la trouve ou recherche tous les emplacements possibles dans le tableau.

Introduction aux algorithmes par le CLRS fournit un très bon aperçu du sujet.

Pour tous ceux qui recherchent le langage de programmation, voici comment cela fonctionne. L’implémentation interne des hashtables avancés comporte de nombreuses complexités et optimisations pour l’allocation / la désallocation du stockage et la recherche, mais les idées de haut niveau seront sensiblement les mêmes.

 (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 avoir lieu.

La règle de base est la suivante: pour qu’une valeur donnée soit insérée, le bucket doit être UNIQUE & DERIVE DE LA VALEUR qu’il est supposé stocker.

Bucket est un espace dans lequel les valeurs sont stockées – car ici je l’ai gardé int comme un index de tableau, mais peut-être aussi un emplacement de mémoire.