Voici une explication en termes simples.

supposons que vous voulez remplir une bibliothèque de livres et pas juste des trucs dans, mais vous voulez être en mesure de facilement les retrouver quand 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 pour démarrer, alors c'est tout ce que cela devrait prendre. Avec le titre, la personne, avec l'aide du bibliothécaire, devrait être en mesure de trouver le livre facilement et rapidement.

Alors, comment pouvez-vous faire? Bien, évidemment, vous pouvez garder une sorte de liste de où vous mettez chaque livre, mais ensuite, vous avez le même problème que la recherche de la bibliothèque, vous devez rechercher dans la liste. Certes, la liste serait plus petite et plus facile à rechercher, mais vous ne voulez pas chercher séquentiellement d'un bout à l'autre de la bibliothèque (ou de la liste).

Vous voulez quelque chose qui, avec le titre de l'ouvrage, peut vous donner le bon endroit à la fois, donc tout ce que vous avez à faire est de se promener sur la droite étagère, et ramasser le livre.

mais comment faire? Bien, avec un peu de prévoyance lorsque vous remplissez la bibliothèque et beaucoup de travail quand vous remplissez la bibliothèque.

au lieu de commencer à remplir la bibliothèque d'un bout à l'autre, vous concevez une petite méthode intelligente. Vous prenez le titre du livre, le lancer à travers un petit programme informatique, qui crache un numéro d'étagère et un numéro de fente 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 alimentez le titre à travers le programme une fois de plus, et obtenez le même numéro d'étagère et le numéro de fente que vous avez été donné à l'origine, et c'est ici que le livre est situé.

le programme, comme d'autres l'ont déjà mentionné, s'appelle un algorithme de hachage ou calcul de hachage et généralement fonctionne en prenant les données introduites dans elle (le titre du livre dans ce cas) et calcule un nombre de celui-ci.

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 nous allons en rester là pour l'instant.

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

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

les trucs techniques suivent.

D'abord, il y a la taille du nombre. Généralement, la sortie d'un tel algorithme de hachage est à l'intérieur d'une gamme de quelques grand nombre, en général beaucoup plus grande que l'espace que vous avez dans votre tableau. 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 dans la gamme de 0 à 1 milliard, ce qui est bien plus élevé.

alors, qu'est-ce qu'on fait? Nous utilisons quelque chose appelé calcul de module, qui essentiellement dit que si vous comptiez le nombre que vous vouliez (c.-à-d. le nombre d'un milliard) mais voulait rester à l'intérieur d'une gamme beaucoup plus petite, chaque fois que vous frappez la limite de cette gamme plus petite que vous avez commencé à nouveau à 0, mais vous devez garder une trace de la distance dans la grande séquence que vous êtes venu.

Dire que la sortie de l'algorithme de hachage est dans le gamme de 0 à 20 et vous obtenez la valeur 17 à partir d'un titre particulier. Si la taille de la Bibliothèque est seulement 7 livres, vous comptez 1, 2, 3, 4, 5, 6, et quand tu arrives à 7, tu recommences à 0. Depuis que nous avons besoin de compter 17 fois, nous avons 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, et le nombre final est de 3.

bien sûr le calcul du module n'est pas fait comme ça, il est fait avec la division et un reste. Le reste de la division 17 par 7 est 3 (7 VA 2 fois dans 17 à 14 et le la différence entre 17 et 14 est de 3).

ainsi, vous mettez le livre dans la fente numéro 3.

cela nous amène au problème suivant. Collision. Puisque l'algorithme n'a aucun moyen d'espacer les livres de sorte 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é avant. Dans le sens bibliothèque, quand vous arrivez à l'étagère et le numéro de fente que vous souhaitez mettre un livre, il ya déjà un livre là.

diverses méthodes de traitement des collisions existent, y compris l'exécution des données dans un autre calcul pour obtenir une autre place dans la table ( double hachage ), ou tout simplement pour trouver un espace proche de celui qui vous a été donné (c.-à-d. juste à côté du livre précédent en supposant que la fente était disponible également connu sous le nom de sonde linéaire ). Cela signifie que vous avez un peu de creuser quand vous essayez de trouver le livre plus tard, mais il est encore mieux que de simplement commencer à un bout de la bibliothèque.

enfin, à un moment donné, vous pourriez vouloir mettre plus de livres dans la bibliothèque que la bibliothèque permet. En d'autres termes, vous devez construire une plus grande bibliothèque. Puisque l'emplacement exact dans la bibliothèque a été calculé en utilisant la taille exacte et actuelle de la bibliothèque, il va de suivre que si vous redimensionnez la bibliothèque vous pourriez finir par devoir trouver de nouveaux emplacements pour tous les livres puisque le calcul fait pour trouver leurs emplacements a changé.

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

Usage et jargon:

1. tables de hachage sont utilisés pour stocker et extraire rapidement des données (ou des enregistrements).
2. les enregistrements sont stockés dans seaux utilisant clés de hachage
3. 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 dossier.
4. Chaque seau 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 avait un total de 300 classeurs pour conserver les informations détaillées (les dossiers) pour leurs environ 30.000 clients. Chaque dossier était clairement identifié avec son numéro unique de 0 à 299.

les préposés au classement de l'époque devaient rapidement récupérer et stocker les dossiers des clients pour le personnel en service. 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 déposer un dossier-client, les préposés au classement utiliseraient le numéro de client unique inscrit sur le dossier. En utilisant ce numéro de client, ils moduleraient la clé de hachage par 300 en ordre d'identifier le classeur dans lequel il est contenu. Lorsqu'ils ouvraient le classeur, ils découvraient qu'il contenait de nombreux dossiers classés par numéro de client. Après avoir identifié le bon endroit, ils le glisseraient simplement.

pour récupérer un dossier client, les préposés au classement recevraient un numéro de client sur une feuille de papier. En utilisant ce numéro de client unique, ils le moduleraient par 300 (La clé de hachage ) afin de déterminer classeur a le dossier clients. Lorsqu'ils ouvraient le classeur, ils découvraient qu'il contenait de nombreux dossiers classés par numéro de client. En fouillant dans les dossiers, ils trouveraient rapidement le dossier client et le récupéreraient.

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

il est important de se rappeler que les ordinateurs (et leurs algorithmes) traitent les nombres mieux que les chaînes. L'accès à un grand tableau à l'aide d'un indice est significativement beaucoup plus rapide que l'accès séquentiel.

comme Simon a mentionné que je crois être très important est que la partie de fringage est de transformer un grand espace (de longueur arbitraire, généralement des cordes, etc) et de le mappage à un petit espace (de taille connue, généralement numéros) pour l'indexation. Ceci si très important de se rappeler!

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

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

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 segmenté vos données et amélioré le classement et la récupération processus.

Espère que cette aide,

Jeach!

il s'avère que c'est un domaine assez profond de la théorie, mais le contour 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, disons).

si vous n'avez qu'un petit espace de choses à hachurer, vous pourriez vous en tirer en interprétant simplement ces choses comme des entiers, et vous avez terminé (par exemple 4 chaînes d'octets)

D'habitude, cependant, vous avez un espace beaucoup plus grand. Si l'espace des choses que vous autorisez comme clés est plus grand que l'espace des choses que vous utilisez pour indexer (votre uint32 ou autre) alors vous ne pouvez pas avoir une valeur unique pour chacun d'eux. Quand deux ou plusieurs choses hachent au même résultat, vous aurez à gérer la redondance d'une manière appropriée (ceci est généralement appelé une collision, et la façon dont vous le gérer ou non dépendra un peu de ce que vous utilisez le hachage pour.)

cela implique que vous voulez qu'il soit peu probable d'avoir le même résultat, et vous aimeriez probablement aussi vraiment que la fonction de hachage soit rapide.

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

Dans la pratique, d'habitude vous devriez être capable de trouver une fonction qui fonctionne bien pour votre application et l'utiliser.

maintenant pour faire ce travail comme un hashtable: imaginez-vous je me fichais de l'usage de la mémoire. Ensuite, vous pouvez créer un tableau aussi longtemps que votre indexation ensemble (tous les uint32, par exemple). Comme vous ajoutez quelque chose à la table, vous Hachez sa clé et regardez le tableau à cet index. Si il n'y a rien, vous mettez votre valeur. S'il y a déjà quelque chose là-bas, vous ajoutez cette nouvelle entrée à une liste de choses à cette adresse, avec suffisamment d'Informations (votre clé originale, ou quelque chose de intelligent) pour trouver quelle entrée appartient réellement à quelle clé.

ainsi comme vous allez un long, chaque entrée dans votre hashtable (le tableau) est soit vide, ou contient une entrée, ou une liste d'entrées. Extraire est un simple comme l'indexation dans le tableau, et soit retourner la valeur, ou marcher dans la liste des valeurs et retourner la bonne.

bien sûr dans la pratique, vous ne pouvez généralement pas faire cela, il 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 else est implicitement nulle).

il y a beaucoup de stratagèmes et de trucs pour améliorer ce travail, mais c'est l'essentiel.

beaucoup de réponses , mais aucun d'entre eux sont très visuel , et les tables de hachage peuvent facilement "cliquer" quand visualisé.

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é dans la mémoire comme ci-dessous, où () - les nombres joints 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 connu comme un seau , et commence une-éventuellement vide-liste liée de valeurs (alias éléments , dans cet exemple - noms )
• chaque valeur (par exemple "fred" avec hachage 42 ) est liée à partir du seau [hash % number_of_buckets] par exemple 42 % 10 == [2] ; % est l'opérateur du module - le reste divisé par le nombre de seaux
• les valeurs de données multiples peuvent entrer en collision et être reliées à partir du même seau, le plus souvent parce que leurs valeurs de hachage entrent en collision après le fonctionnement du module (par exemple 42 % 10 == [2] , et 9282 % 10 == [2] ), mais occasionnellement parce que les valeurs de hachage sont les mêmes (par exemple "fred" et "jane" tous deux indiqués avec hachage 42 surtout)
  • la plupart des tables de hachage traitent les collisions - avec une performance légèrement réduite mais aucune confusion fonctionnelle - en comparant la pleine valeur (ici le texte) d'une clé recherchée ou insérée à chaque clé déjà dans la liste liée au hachage-à seau

si la taille de la table augmente, les tables de hachage mises en œuvre comme ci-dessus ont tendance à se redimensionner (c.-à-d. créer un plus grand tableau de seaux, créer nouveau / mis à jour lié listes il y de", de supprimer l'ancien tableau) pour garder le ratio d'éléments de seaux (aka facteur de charge ) quelque part dans l'0,5 à 1,0 gamme. Avec le facteur de charge 1 et une fonction de hachage de résistance cryptographique, 36,8% des seaux auront tendance à être vides, 36,8% ont un élément, 18,4% deux éléments, 6,1% trois éléments, 1,5% quatre éléments, .3% cinq etc.. - les longueurs de liste moyenne 2.0 éléments peu importe combien d'éléments sont dans le tableau (i.e. qu'il y ait 100 éléments et 100 seaux, ou 100 millions d'éléments et 100 millions de seaux), c'est pourquoi nous disons recherche/insertion/effacement sont O(1) opérations à temps constant.

(Notes: Toutes les tables de hachage n'utilisent pas des listes liées, mais la plupart des tables à usage général le font, comme le hachage fermé (aka open addressing) - en particulier avec les opérations d'effacement prises en charge - a des propriétés de performance moins stables avec des clés à risque de collision/fonctions de hachage).

quelques mots sur fonctions de hachage

un but général, dans le pire des cas, la fonction de hachage minimisant les collisions est de pulvériser les touches autour des seaux de la table de hachage efficacement au hasard, tout en générant toujours la même valeur de hachage pour la même clé. Même un bit changeant n'importe où dans la clé idéalement - au hasard - retournerait environ la moitié des bits dans la valeur de hachage résultante.

c'est normalement orchestré avec des maths trop compliquées pour que je puisse grogner. Je vais vous parler de l'un facile-à-comprendre - pas le plus évolutive ou cache sympathique mais fondamentalement élégant (comme le cryptage avec un pad!)- comme je pense qu'il aide à ramener à la maison les qualités souhaitables mentionnées ci-dessus. Supposons que vous Hachez 64 bits double s-vous pouvez créer 8 tables chacune de 256 nombres aléatoires (i.e. size_t random[8][256] ), puis utiliser chaque tranche de 8 bits/1 octet de la représentation de mémoire de double pour indexer dans une table différente, Xoriant les nombres aléatoires que vous recherchez. Avec cette approche, il est facile de voir qu'un peu de changement n'importe où dans le double résulte en un nombre aléatoire différent étant regardé dans l'un des tableaux, et une valeur finale totalement non corrélée.

encore, de nombreuses fonctions de hachage de bibliothèques passent des entiers inchangés, ce qui est extrêmement sujet à collision dans les pires cas, mais l'espoir est que dans le cas assez commun de touches entières qui ont tendance à augmenter, ils vont mapper dans les seaux successifs laissant moins de vide que le 36,8% de feuilles hachées au hasard, ayant ainsi moins de collisions et moins de listes d'éléments de collision plus longues que celles obtenues par des mappages au hasard. C'est aussi génial d'économiser le temps qu'il faut pour générer un hash fort. Quand les touches ne s'incrémentent pas bien, l'espoir est qu'elles seront assez aléatoires, elles n'auront pas besoin d'une forte fonction de hachage pour totalement randomiser leur placement dans des seaux.

Eh bien, c'était moins amusant et plus lourd aller que l'explication de la table de hachage, mais l'espoir il aide quelqu'un....

vous êtes sur le point d'expliquer tout ça, mais il manque certaines choses. Le hashtable n'est qu'un tableau. Le tableau lui-même contiendra quelque chose dans chaque logement. Au minimum, vous stockerez le hashvalue ou la valeur elle-même dans cette fente. En plus de cela, vous pouvez également stocker une liste de valeurs liées/enchaînées qui sont entrées en collision sur cette fente, 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 récupérer de cette fente.

il est important de noter que le hashvalue lui-même n'indique généralement pas la fente dans laquelle placer la valeur. Par exemple, un hashvalue peut être une valeur entière négative. De toute évidence, un nombre négatif ne peut pas indiquer l'emplacement d'un tableau. En outre, les valeurs de hachage auront tendance à plusieurs fois être des nombres plus grands que les fentes disponibles. Ainsi, un autre calcul doit être effectué par le hashtable lui-même pour déterminer dans quelle fente la valeur doit entrer. C'est fait avec une opération de mathématiques de module comme:

uint slotIndex = hashValue % hashTableSize;

cette valeur est la fente dans laquelle la valeur entrera. Dans l'adressage ouvert, si la fente est déjà remplie d'une autre valeur de hachage et/ou d'autres données, l'opération de module sera exécutée une fois de plus pour trouver la fente suivante:

slotIndex = (remainder + 1) % hashTableSize;

je suppose qu'il peut y avoir d'autres méthodes plus avancées pour déterminer l'indice de fente, mais c'est le commun que j'ai vu... serait intéressé par toute autre mieux.

avec la méthode du module, si vous avez une table de la taille de dire 1000, toute valeur de hashvalue qui est entre 1 et 1000 ira dans la fente correspondante. Toutes les valeurs négatives et toutes les valeurs supérieures à 1000 peuvent entrer en collision avec les valeurs des slots. Les chances que cela se produise dépendent à la fois de votre méthode de hachage, ainsi que le nombre total d'articles que vous ajoutez à la table de hachage. Généralement, il est préférable de faire la taille du hashtable de telle sorte que le nombre total de valeurs ajouté à cela est seulement égale à 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 seau/fente et il effectuera très rapidement pour les deux 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 n'importe quel moyen, puis redimensionnez votre hashtable une fois que le nombre d'éléments ajoutés atteint 70% de la capacité.

j'espère que cela a aider.

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 un réel plaisir, construisez votre propre hashfunction et essayez de L'amener à ne jamais entrer en collision sur les données spécifiques que vous Hachez, exécutez plus vite que GetHashCode, et avoir une distribution assez égale. J'ai fait cela en utilisant des valeurs de hashcode longues au lieu de valeurs de taille int et cela a fonctionné assez bien sur jusqu'à 32 millions d'entires hashvalues dans le hashtable 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. Quand vous pouvez atteindre ceci, le hashtable est très rapide. :)

C'est ainsi que cela fonctionne selon mon entendement:

voici un exemple: représentez 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 seau correspondant.

disons que vous avez 200 objets, mais seulement 15 d'entre eux ont des codes de hachage qui commencent par le la lettre' B 'la table de hachage n'aurait besoin que de regarder et de chercher à travers les 15 objets dans le seau' B', plutôt que les 200 objets.

en ce qui concerne le calcul du code hash, il n'y a rien de magique. Le but est juste de faire en sorte que des objets différents 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 comme un code de hachage pour toutes les instances, mais vous détruiriez essentiellement l'utilité d'un une table de hachage, comme si elle allait devenir un seau géant.

court et doux:

une table de hash enroule un tableau, appelons-le internalArray . Les éléments sont insérés dans le tableau de cette façon:

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

parfois, deux clés vont hash au 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 voir, inserts, Lookup, et suppression de notre tableau de listes liées est presque O (1).

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

c'est encore plus simple que ça.

un hashtable n'est rien de plus qu'un tableau (habituellement clairsemé un) de vecteurs qui contiennent des paires clé/valeur. La taille maximale de ce tableau est généralement plus petit que le nombre d'éléments dans l'ensemble des 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 basé sur les valeurs de l'élément qui sera stockés dans le tableau.

c'est ici que les vecteurs de stockage des paires clé/valeur dans le tableau entrent en jeu. Parce que l'ensemble des valeurs qui peuvent être des indices dans le tableau est typiquement plus petit que le nombre de toutes les valeurs possibles que le type peut avoir, il est possible que votre algorithme de hachage va générer la même valeur pour deux clés séparées. Un bon algorithme de hachage permettra d'éviter autant que possible (c'est pourquoi il est relégué au type généralement parce qu'il a des informations spécifiques qu'un algorithme général de hachage ne peut pas savoir), mais il est impossible de prévenir.

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érer, et d'une comparaison est faite entre la clé dans le vecteur et la clé qui est regardé. Si elle est trouvée, grande et la valeur associée à la clé est retournée, sinon, rien est retourné.

Vous prenez un tas de choses, et un tableau.

pour chaque chose, vous faites un index pour elle, appelé un hachage. Ce qui est important avec le hash, c'est qu'il se disperse beaucoup; vous ne voulez pas que deux choses similaires aient des hash similaires.

mettez vos affaires dans le tableau à la position indiquée par le hachage. Plus d'une chose peut finir à un hachage donné, donc vous stockez les choses dans des tableaux ou quelque chose d'autre approprié, que nous généralement appeler un seau.

quand vous cherchez des choses dans le hachis, vous passez par les mêmes étapes, en déterminant la valeur du hachis, puis en voyant ce qu'il y a dans le seau à cet endroit et en vérifiant si c'est ce que vous cherchez.

quand votre hachage fonctionne bien et que votre tableau est assez grand, il n'y aura que quelques choses au plus à n'importe quel indice particulier dans le tableau, donc vous n'aurez pas à regarder beaucoup.

pour bonus points, faites en sorte que lorsque votre table de hachage est accédé, il déplace la chose trouvée (s'il y en a) au début du seau, donc la prochaine fois c'est la première chose vérifiée.

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

toutes les réponses jusqu'à présent sont bonnes, et obtenir différents aspects de la façon dont un hashtable fonctionne. Voici un exemple simple qui pourrait être utile. Disons que nous voulons stocker certains éléments avec des chaînes alphabétiques minuscules comme des 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 l'associer à un entier, donc "alligator "a un code de hachage de 0," bee "a un code de hachage de 1," zebra " serait de 25, etc.

ensuite, nous avons un tableau de 26 seaux (pourrait être Arrayylists en Java), et nous avons mis l'article dans le seau 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 vont dans le seau pour ce code de hachage ainsi une recherche linéaire devrait être faite dans le seau pour trouver un particulier article.

dans notre exemple, si nous avions seulement quelques douzaines d'articles avec des clés couvrant l'alphabet, cela fonctionnerait très bien. Cependant, si nous avions un million d'articles ou si toutes les clés commençaient par " a " ou "b", alors notre table de hachage ne serait pas idéale. Pour obtenir de meilleures performances, nous aurions besoin d'une autre fonction de hachage et/ou plus de seaux.

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 supporte le fonctionnement de l'indexation, où vous pouvez accéder à L'élément I, A[I], en une seule étape, peu importe la taille de A est.

donc, par exemple, si vous voulez stocker des informations sur un groupe de personnes qui ont tous des âges différents, une manière simple serait d'avoir un tableau qui est assez grand, et utiliser l'âge de chaque personne comme un index dans le tableau. Thay façon, vous pourriez avoir une étape d'accès à l'information.

Mais bien sûr, il pourrait y avoir plus d'une personne avec le même âge, donc ce que vous mettez dans le tableau lors de 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é un "seau"). Il ralentit seulement s'il y a tant de gens que les seaux deviennent grands. Ensuite, vous avez besoin d'un plus grand tableau, et une autre façon d'obtenir plus d'informations d'identification de la personne, comme les premières lettres de leur nom de famille, au lieu d'utiliser l'âge.

C'est l'idée de base. Au lieu d'utiliser l'âge, n'importe quelle fonction de la personne qui produit une bonne répartition des valeurs peut être utilisée. C'est la fonction de hachage. Comme vous pourriez prendre chaque tiers de la représentation ASCII du nom de la personne, brouillé dans un certain ordre. Tout ce qui importe est que vous ne voulez pas trop de gens pour hachurer au même seau, parce que la vitesse dépend des seaux restant petit.

une table de hachage fonctionne totalement sur le fait que le calcul pratique suit le modèle de machine à accès aléatoire c.-à-d. la valeur à n'importe quelle adresse dans la mémoire peut être accessible dans le temps O(1) ou le temps constant.

ainsi, 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 l'étudiant, si c'est 4 chiffres alors cet univers est un ensemble de nombres de 1 à 9999), et une façon de les mapper à un ensemble fini de nombres de taille je peux allouer la mémoire dans mon système, théoriquement ma table de hachage est prêt.

généralement, dans les applications, la taille de l'univers des clés est très grand que le nombre d'éléments que je veux ajouter à la table de hachage(Je ne veux pas gaspiller une mémoire de 1 Go pour hachage ,disons, 10000 ou 100000 valeurs entières parce qu'ils sont de 32 bits de long en reprsentaion binaire). Ainsi, nous utilisons ce hachage. C'est une sorte de mélange d'opération "mathématique", qui fait correspondre mon grand univers à un petit ensemble de valeurs que je peux intégrer dans mémoire. Dans la pratique, 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 cartographié à un petit ensemble, la cartographie doit être de plusieurs à un. Donc, différentes clés seront allotées dans le même espace(?? pas juste). Il ya quelques façons de gérer cela, je connais juste les deux populaires d'entre eux:

• utilisez l'espace qui devait être attribué à la valeur une référence à une liste liée. Cette liste liée stockera une ou plusieurs valeurs, qui viennent à résider dans la même fente dans beaucoup à une cartographie. La liste contient également des clés pour aider quelqu'un qui vient de la 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 pour le gars.
• utilise 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. Quand je vais stocker un valeur, je vois si l'emplacement mémoire requis est libre ou occupé. Si elle est libre, 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 libre et je stocke ma valeur là. Lors de la recherche ou le retrait de la valeur, je retourne sur le même chemin comme indiqué par la séquence et à chaque emplacement demander la valeur s'il est là jusqu'à ce que je le trouve ou rechercher tous les emplacements possibles dans le tableau.

Introduction à Algorithmes par CLRS fournit un très bon aperçu sur le sujet.

pour tous ceux qui recherchent le langage de programmation, voici comment cela fonctionne. La mise en œuvre interne des hashtables avancés comporte de nombreuses complexités et optimisations pour l'allocation de stockage/désallocation et la recherche, mais l'idée de haut niveau 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 de base est: pour une valeur donnée à insérer, le seau doit être UNIQUE et dérivable de la valeur qu'il est censé stocker.