Question Comment fonctionne une table de hachage?


Je cherche une explication de comment fonctionne une table de hachage - en anglais clair pour un nigaud comme moi!

Par exemple, je sais qu'il prend la clé, calcule le hachage (je cherche une explication comment) et ensuite effectue une sorte de modulo pour savoir 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?

Modifier: 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.


441
2018-04-08 15:48


origine


Réponses:


Voici une explication en termes simples.

Supposons que vous souhaitiez remplir une bibliothèque de livres et ne pas simplement les 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 qu'il devrait prendre. Avec le titre, la personne, avec l'aide du bibliothécaire, devrait être capable de trouver le livre facilement et rapidement.

Alors, comment pouvez-vous faire cela? Bien sûr, vous pouvez garder une sorte de liste de l'endroit où vous mettez chaque livre, mais alors vous avez le même problème que la recherche dans la bibliothèque, vous devez rechercher dans la liste. Certes, la liste serait plus petite et plus facile à chercher, mais vous ne voulez toujours pas effectuer une recherche séquentielle d'une extrémité de la bibliothèque (ou de la 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 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 concevez une petite méthode intelligente. Vous prenez le titre du livre, exécutez-le à travers un petit programme informatique, qui crache un numéro de rayon et un numéro de slot sur cette étagère. C'est ici que vous placez le livre.

La beauté de ce programme est que plus tard, quand une personne revient pour lire le livre, vous donnez une nouvelle fois le titre au programme et récupérez le même numéro d'étagère et le même numéro d'emplacement que celui qui vous a été attribué à l'origine. où le livre est situé.

Le programme, comme d'autres l'ont déjà mentionné, est appelé un algorithme de hachage ou de 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 chaque lettre et symbole en un nombre et les résume tous. 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 introduisez la même entrée encore et encore, il continuera à cracher le même nombre à chaque fois.

Ok, c'est comme ça que fonctionne une table de hachage.

Des trucs techniques suivent.

D'abord, il y a la taille du nombre. Habituellement, la sortie d'un tel algorithme de hachage est à l'intérieur d'une plage d'un grand nombre, généralement beaucoup plus grand 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 de hachage pourrait être de l'ordre de 0 à un milliard, ce qui est beaucoup plus élevé.

Alors que faisons-nous? Nous utilisons ce qu'on appelle le calcul de module, qui dit essentiellement que si vous avez compté le nombre que vous vouliez (le chiffre d'un milliard) mais que vous vouliez rester dans une fourchette beaucoup plus petite, chaque fois que vous atteignez la limite 0, mais vous devez garder une trace de jusqu'où dans la grande séquence vous êtes venu.

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 n'est que de 7 livres, vous comptez 1, 2, 3, 4, 5, 6, et quand vous arrivez à 7, vous revenez à 0. Puisque nous avons besoin de 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 division et un reste. Le reste de la division 17 par 7 est 3 (7 va 2 fois dans 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 prochain problème. Collisions Puisque l'algorithme n'a aucun moyen d'espacer les livres afin qu'ils remplissent la bibliothèque exactement (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, quand vous arrivez à l'étagère et au numéro de slot dans lequel vous souhaitez placer un livre, il y a déjà un livre.

Diverses méthodes de gestion des collisions existent, y compris l’exécution des données dans un autre calcul pour obtenir un autre emplacement dans la table (double hachage), ou simplement pour trouver un espace proche de celui que vous avez reçu (c'est-à-dire juste à côté du livre précédent en supposant que la fente était disponible aussi sondage linéaire). Cela voudrait dire que vous avez quelques 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 pouvez ajouter plus de livres à la bibliothèque que la bibliothèque ne le permet. En d'autres termes, vous devez construire une bibliothèque plus grande. Puisque 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 devoir trouver de nouveaux emplacements pour tous les livres depuis le calcul pour trouver leurs taches a changé.

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


851
2018-04-08 16:33



Usage et Lingo:

  1. Tables de hachage sont utilisés pour stocker et récupérer rapidement des données (ou des enregistrements).
  2. Les enregistrements sont stockés dans seaux en utilisant clés de hachage
  3. Touches de hachage sont calculés 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 seau peut avoir plusieurs enregistrements qui sont organisés dans un ordre particulier.

Exemple de 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) pour 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éthodologie de hachage pour stocker et récupérer leurs dossiers.

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 le touche dièse par 300 afin d'identifier le classeur dans lequel il est contenu. Quand ils ont ouvert le classeur, ils découvriraient qu'il contenait de nombreux dossiers classé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 de 300 (le touche dièse) afin de déterminer quel classeur avait 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 cherchant dans les dossiers, ils trouveraient rapidement le dossier du client et le récupéreraient.

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


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

Comme Simon l'a mentionné que je crois être très important est que la partie de hachage consiste à transformer un grand espace (de longueur arbitraire, généralement des chaînes, etc.) et à le mapper à 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 est de diviser l'ensemble de vos données en segments de manière à 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 simplement la première lettre du nom de famille. Donc, si vous avez 26 classeurs contenant chacun une lettre de A à Z, vous avez en théorie juste segmenté vos données et amélioré le processus de classement et de récupération.

J'espère que cela t'aides,

Jeach!


90
2018-04-08 17:20



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

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 met en correspondance avec un espace utile pour l'indexation (des entiers non signés, disons).

Si vous avez seulement 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 (votre uint32 ou quoi que ce soit) alors vous ne pouvez pas avoir une valeur unique pour chacun. Quand deux choses ou plus aboutissent au même résultat, vous devrez gérer la redondance d'une 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 implique que vous voulez qu'il soit peu probable d'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 ne vous souciez pas de l’utilisation de la mémoire. Vous pouvez ensuite créer un tableau aussi longtemps que votre jeu d'indexation (tous les uint32, par exemple). Lorsque vous ajoutez quelque chose à la table, vous la hachez et regardez 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 touche.

Donc, comme vous allez un long, chaque entrée de votre hashtable (le tableau) est soit vide, ou contient une entrée, ou une liste d'entrées. Récupérer est une simple indexation dans le tableau, soit en retournant la valeur, soit en parcourant la liste des valeurs et en retournant la bonne.

Bien sûr, dans la pratique, vous ne pouvez généralement pas faire cela, cela gaspille trop de mémoire. Donc, vous faites tout ce qui est 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 que cela fonctionne mieux, mais ce sont les bases.


63
2018-04-08 16:11



Beaucoup de réponses, mais aucune n'est très visuel, et les tables de hachage peuvent facilement "cliquer" lors de la visualisation.

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 disposé en mémoire comme ci-dessous, où ()Les nombres 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 (index [0], [1]...) est connu comme un seau, et lance une liste de liens éventuellement vide valeurs (alias éléments, dans cet exemple - les gens des noms)
  • chaque valeur (par ex. "fred" avec du hasch 42) est liée à seau [hash % number_of_buckets] par exemple. 42 % 10 == [2]; % est l'opérateur de module - le reste lorsqu'il est divisé par le nombre de compartiments
  • plusieurs valeurs de données peuvent entrer en collision at et être lié à partir du même compartiment, le plus souvent parce que leurs valeurs de hachage entrent en collision après l'opération de module (par ex. 42 % 10 == [2], et 9282 % 10 == [2]), mais parfois parce que les valeurs de hachage sont les mêmes (par ex. "fred" et "jane" les deux montrés avec hash 42 au dessus)
    • la plupart des tables de hachage gèrent les collisions - avec une performance légèrement réduite mais aucune confusion fonctionnelle - en comparant la valeur complète (ici le texte) d'une clé recherchée ou insérée à chaque clé déjà dans la liste chaînée du hachage

Si la taille de la table augmente, les tables de hachage implémentées comme ci-dessus ont tendance à se redimensionner (c'est-à-dire créer un plus grand nombre de compartiments, créer des listes chaînées nouvelles / mises à jour, supprimer l'ancien tableau). facteur de charge) quelque part entre 0,5 et 1,0. Avec le facteur de charge 1 et une fonction de hachage cryptographique, 36,8% des seaux 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, 0,3% cinq etc. - les longueurs de la liste moyenne 2.0 éléments, peu importe combien d'éléments sont dans la table (c.-à-d. S'il y a 100 éléments et 100 seaux, ou 100 millions d'éléments et 100 millions de seaux), ce qui explique pourquoi O / 1 .

(Notes: toutes les tables de hachage n'utilisent pas de listes chaînées, mais la plupart des hachages fermés, en particulier avec les opérations d'effacement supportées, ont des propriétés de performances moins stables avec les fonctions de hachage / de hachage).

Quelques mots sur les fonctions de hachage

Une fonction de hachage minimisant les collisions dans le cas le plus défavorable consiste à pulvériser les clés autour des compartiments de table de hachage de façon aléatoire, tout en générant toujours la même valeur de hachage pour la même clé. Même un seul bit changeant n'importe où dans la clé ferait idéalement - de manière aléatoire - inverser 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 citerai un moyen facile à comprendre - pas le plus évolutif ou le cache amical mais intrinsèquement élégant (comme le cryptage avec un tampon unique!) - car je pense qu'il contribue à ramener les qualités souhaitables mentionnées ci-dessus. Dites que vous étiez Hash 64 bits doubles - vous pouvez créer 8 tableaux contenant chacun 256 nombres aléatoires (c.-à-d. size_t random[8][256]), puis utilisez chaque tranche de 8 bits / 1 octet du doubleReprésentation de la mémoire à indexer dans une table différente, XORing les nombres aléatoires que vous recherchez. Avec cette approche, il est facile de voir un peu changer quelque part dans le double résultats dans un nombre aléatoire différent recherché dans l'un des tableaux, et une valeur finale totalement décorrélée.

Pourtant, de nombreuses fonctions de hachage des bibliothèques passent des entiers inchangés, ce qui est extrêmement sujet aux collisions dans les cas les plus graves, mais l'espoir est que dans le cas assez courant des clés entières qui s'incrémentent, elles seront mappées vide que les 36,8% de feuilles de hachage aléatoires, ce qui réduit le nombre de collisions et réduit le nombre de listes chaînées d'éléments en collision plus longues que celles obtenues par des mappages aléatoires. Il est également intéressant de gagner du temps pour générer un hash fort. Lorsque les clés ne s'incrémentent pas bien, l'espoir est qu'ils seront assez aléatoires, ils n'auront pas besoin d'une fonction de hachage fort pour randomiser complètement leur placement 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 aide quelqu'un ...


31
2018-06-01 06:59



Vous êtes sur le point d'expliquer cela complètement, mais il vous manque deux choses. La hashtable est juste un tableau. Le tableau lui-même contiendra quelque chose dans chaque emplacement. Vous stockez au minimum la valeur de hachage ou la valeur elle-même dans cet emplacement. En plus de cela, vous pouvez également stocker une liste chaînée / chaînée de valeurs qui sont entrées en collision sur cet emplacement, ou vous pouvez utiliser la méthode d'adressage ouverte. 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 hashvalue elle-même n'indique généralement pas la fente dans laquelle 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 créneaux disponibles. Ainsi, un autre calcul doit être effectué par la table de hachage elle-même pour déterminer dans quel intervalle la valeur devrait aller. 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 peut y avoir d'autres méthodes plus avancées pour déterminer l'index de fente, mais ceci est le commun que j'ai vu ... serait intéressé par d'autres qui fonctionnent mieux.

Avec la méthode du module, si vous avez une table de 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 à 1000 seront des valeurs d'intervalle potentiellement en conflit. Les chances que cela se produise dépendent à la fois de votre méthode de hachage, ainsi que du nombre total d'éléments que vous ajoutez à 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 distribution 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 à ajouter 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 # le GetHashCode() La méthode est assez lente et entraîne des collisions de valeur réelles dans beaucoup de 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 distribution 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'entiers 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 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. :)


24
2018-05-15 01:41



Voici comment cela fonctionne dans ma compréhension:

Voici un exemple: image de la table entière comme une série de seaux. Supposons que vous ayez une implémentation avec des codes de hachage alphanumériques et que vous ayez un seau 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 n'a besoin que de rechercher et de rechercher parmi les 15 objets du 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. L'objectif est simplement de faire en sorte que différents objets renvoient des codes différents et que des objets é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.


17
2018-04-08 16:02



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 vont hacher le même index dans le tableau, et vous voulez garder 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 aussi simples à écrire. Comme vous pouvez le constater, les insertions, recherches et suppressions de notre tableau de listes liées sont 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.


12
2018-04-08 17:24



C'est encore plus simple que ça.

Une table de hachage n'est rien de plus qu'un tableau (généralement clairsemé un) 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 séparées. UNE bien L'algorithme de hachage l'empêche autant que possible (c'est pourquoi il est généralement relégué au type car il possède des informations spécifiques qu'un algorithme de hachage général ne peut probablement pas connaître), mais il est impossible de prévenir.

Pour cette raison, vous pouvez avoir plusieurs clés qui vont générer 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, super et la valeur associée à la clé est retournée, sinon, rien n'est retourné.


10
2018-04-08 16:04



Vous prenez un tas de choses, et un tableau.

Pour chaque chose, vous créez un index, appelé hash. La chose importante à propos du hachage, c'est qu'il «se disperse» 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 déterminant la valeur de hachage, puis en regardant ce qui se trouve dans le seau à cet endroit et en vérifiant si c'est ce que vous recherchez.

Lorsque votre hachage fonctionne correctement et que votre tableau est assez 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 la première chose est cochée.


8
2018-04-08 16:22



La façon 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 objet possède 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.


2
2018-04-08 15:52