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.

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 :)

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!

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.

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.

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

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.

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.

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é.

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.

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.

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.

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.

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.

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;
}

où 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.