Comment fonctionne une table de hachage ?

Question

Je suis à la recherche pour obtenir une explication du fonctionne de hashtable - en langage clair pour un benêt comme moi ! Par exemple, je sais il prend la clé, calcule le hachage (comment ?) et effectue ensuite certains type de de trouver où il se trouve dans le tableau que la valeur est stockée, mais c’est où ma connaissance s’arrête.

N’importe qui préciserait le processus.

Edit : Je ne cherche plus précisément de quelle manière calcule-t-on les codes, mais une présentation générale du fonctionne d’une table de hachage.

Answer 1

Voici une explication traduction en termes usuels.

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.

Alors, vous décidez que si la personne qui veut lire un livre connaît le titre du livre, et le titre exact de démarrage, alors que c'est tout ce qu'il doit prendre. Avec le titre de la personne, avec l'aide de la bibliothécaire, devrait être en mesure d'aller 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. Accordé, la liste serait smallers, et de faciliter la recherche, mais encore, vous ne souhaitez pas rechercher de manière séquentielle à partir d'une extrémité de la bibliothèque (ou une liste) à l'autre.

Vous voulez quelque chose qui, avec le titre de l'ouvrage, peut vous donner le bon endroit à la fois, de sorte que tous vous avez à faire est de tout simplement vous balader sur le côté de la tablette, et de ramasser le livre.

Mais comment peut-il se faire? Bien, avec un peu de prévoyance lorsque vous remplissez la bibliothèque, et en fait, beaucoup de travail quand vous remplissez la bibliothèque.

Au lieu de juste de commencer à remplir la bibliothèque à partir d'une extrémité à l'autre, vous concevoir un astucieux petit méthode. Vous prenez le titre du livre, le lancer à travers un petit programme informatique, qui crache un nombre d'étagère et d'un numéro d'emplacement sur cette étagère. C'est l'endroit où vous placez le livre.

La beauté de ce programme est que plus tard, quand une personne revient à lire le livre, vous nourrissez le titre par le programme une fois de plus, et obtenir le même nombre d'étagère et le numéro de l'emplacement que vous avez été donné à l'origine, et c'est là où le livre se trouve.

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

Pour simplifier, disons qu'elle transforme chaque lettre et le symbole en un certain nombre, et le sommes 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 essentiellement la manière d'une table de hachage œuvres.

Trucs techniques qui suit.

Tout d'abord, il y a la taille de la nombre. Généralement, la sortie d'un tel algorithme de hachage est à l'intérieur d'une gamme de quelques grand nombre, généralement beaucoup plus grand 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 de la table de hachage de calcul pourrait être dans la gamme de 0 à un milliard de dollars, beaucoup plus élevé.

Alors, que faisons-nous? Nous utilisons quelque chose qui s'appelle le module de calcul, qui dit essentiellement que si vous compté le nombre que tu voulais (ie. l'un milliard de nombre), mais a souhaité rester à l'intérieur d'un éventail beaucoup plus petite, à chaque fois que vous atteignez la limite de la plus petite de la gamme, vous avez commencé à revenir à 0, mais vous devez garder une trace de la façon dont beaucoup dans le grand de la séquence que vous venez.

Dire que la sortie de l'algorithme de hachage est dans la gamme de 0 à 20, et vous obtenez la valeur de 17 à partir d'un titre particulier. Si la taille de la bibliothèque est à seulement 7 livres, vous comptez 0, 1, 2, 3, 4, 5, 6, et quand vous arrivez à 7, vous commencer à 0. Depuis que nous avons besoin de compter 17 fois, nous avons 0, 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 module de calcul n'est pas fait comme ça, c'est fait avec de la division, et le reste. Le reste de la division 17 par 7 à 3 (7 va 2 fois en 17, à 14 ans, et la différence entre le 17 et 14 3).

Ainsi, vous avez mis le livre dans le logement nr. 3.

Cela conduit à un autre problème. Les Collisions. Depuis que l'algorithme n'a aucun moyen d'espacer les livres afin qu'ils remplissent la bibliothèque exactement (ou de la table de hachage si vous voulez), il sera, au final, le calcul d'un nombre qui a été utilisé avant. Dans la bibliothèque de sens, quand vous arrivez à la tablette et le numéro de l'emplacement que vous souhaitez faire un livre, il y a déjà un livre.

Divers collision méthodes de manipulation existent, y compris l'exécution des données dans encore un autre mode de calcul pour obtenir une autre place dans la table, ou tout simplement de trouver un espace proche de celui que vous (c'est à dire juste à côté du livre précédent). Cela signifie que vous avez un peu de temps à le faire lorsque vous essayez de trouver le livre plus tard, mais c'est toujours mieux que de simplement en commençant à une extrémité de la bibliothèque.

Enfin, à un certain moment, vous pouvez mettre plus de livres dans la bibliothèque de la bibliothèque permet, en d'autres termes, vous avez besoin pour construire une grande bibliothèque. Depuis l'endroit exact de la bibliothèque a été calculée à l'aide de la réponse exacte et à jour, la taille de la bibliothèque, il va suivre que si vous redimensionnez la bibliothèque, vous pourriez avoir à trouver de nouveaux spots pour tous les livres, puisque le calcul fait pour trouver leurs taches a changé.

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

Answer 2

L'utilisation et le Jargon:

1. Les tables de hachage sont utilisé pour stocker et récupérer des données (ou des dossiers).
2. Les enregistrements sont stockés dans des seaux à l'aide de clés de hachage
3. Clés de hachage sont calculés en appliquant un algorithme de hachage à une valeur choisie contenues dans le dossier. Cette valeur choisie doit être une valeur commune à tous les enregistrements.
4. Chaque seau peut avoir plusieurs registres qui doivent être organisées dans un ordre particulier.

L'Exemple Du Monde Réel:

Hash & Co., fondée en 1803 et dépourvus de toute la technologie de l'ordinateur a eu un total de 300 classeurs pour garder les informations détaillées (les enregistrements) pour leur environ 30 000 clients. Chaque dossier ont été clairement identifié par son numéro unique de 0 à 299.

Les commis au classement de l'époque avait rapidement de récupération et de stockage des enregistrements de client pour le travail personnel. 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, commis au classement serait d'utiliser le client unique, le numéro écrit sur le dossier. À l'aide de ce numéro de client, ils modulent par 300 (la clé de hachage) afin d'identifier le dépôt du cabinet elle est contenue dans. Quand ils ont ouvert le classeur ils allaient découvrir qu'il contenait de nombreux dossiers ordonnés par numéro de client. Après l'identification de l'emplacement correct, ils seraient tout simplement de le glisser dans.

Pour récupérer un dossier client, commis au classement serait donné un numéro de client sur un bout de papier. À l'aide de cet unique numéro de client, ils modulent par 300 (la clé de hachage) afin de déterminer le classeur avait le dossier clients. Quand ils ont ouvert le classeur ils allaient découvrir qu'il contenait de nombreux dossiers ordonnés par numéro de client. La recherche dans les dossiers, il serait de trouver rapidement le dossier du client et de les récupérer.

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

---

Une chose importante à retenir est que les ordinateurs (et leurs algorithmes) de traiter les nombres mieux qu'avec des cordes. L'accès à un grand tableau à l'aide d'un indice est significativement beaucoup plus rapide que l'accès séquentiel.

Comme Simon l'a mentionné ce qui, je crois, très important , c'est que le hachage de la partie est de transformer un grand espace (de longueur arbitraire, généralement des chaînes, etc) et de la cartographie à un petit espace (de taille connue, généralement numéros) pour l'indexation. Ce cas très important de s'en souvenir!

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

---

L'idée principale consiste à diviser l'ensemble de votre jeu de données en segments d'accélérer le réel de la recherche qui est généralement beaucoup de temps. Dans notre exemple ci-dessus, chaque classeur (statistiquement) contiennent environ 300 dossiers. Recherche (quel que soit l'ordre) par le biais de 300 dossiers est beaucoup plus rapide que d'avoir à traiter avec plus de 30 000.

Vous avez peut-être remarqué que certains le font déjà. Mais au lieu de concevoir un hachage méthodologie pour générer une clé de hachage, ils seront dans la plupart des cas, utilisez simplement la première lettre du nom de famille. Donc, si vous avez 26 classeurs contenant chacun une lettre de a à Z, vous, en théorie, juste segmenté vos données et amélioré, le dépôt et le processus de récupération.

Espérons que cela aide,

Jeach!

Answer 3

Cela s'avère être une jolie zone profonde 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 (dire des chaînes de longueur arbitraire) et correspond à un espace utile pour l'indexation (des entiers non signés, par exemple).

Si vous avez seulement un petit espace de les choses de hachage, vous pourriez sortir avec juste l'interprétation de ces choses comme des entiers, et vous êtes fait (par exemple, 4 chaînes d'octets)

Habituellement, cependant, vous avez beaucoup plus d'espace. Si l'espace des choses vous permettre en tant que clés est plus grand que l'espace de les choses que vous utilisez à l'index de votre uint32 ou autre), alors vous ne peut pas avoir une valeur unique pour chacun. Lorsque deux ou plusieurs choses de hachage pour le même résultat, vous devrez gérer la redondance de manière appropriée (c'est généralement considérée comme une collision, et la façon dont vous les manipulez ou de ne pas dépendre un peu sur ce que vous êtes en utilisant le hachage).

Cela implique que vous voulez qu'il soit peu probable d'avoir le même résultat, et vous avez sans doute aussi aurait vraiment envie de la fonction de hachage à être rapide.

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

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 une table de hachage: Imaginez que vous ne se soucient pas de l'utilisation de la mémoire. Ensuite, vous pouvez créer un tableau aussi longtemps que votre indexation ensemble (tous les uint32, par exemple). Comme vous ajouter quelque chose à la table de hachage de clé et de regarder le tableau à l'index. Si il n'y a rien, vous mettez votre valeur. Si il y a déjà quelque chose de là, vous ajoutez cette nouvelle entrée à la liste de choses à cette adresse, avec suffisamment d'informations (votre clé d'origine, ou quelque chose d'intelligent) pour trouver l'entrée qui appartient réellement à la clé.

Donc, comme vous allez le long, à chaque entrée dans la table de hachage (le tableau) est soit vide ou contient une entrée, ou une liste d'entrées. La récupération est aussi simple que l'indexation dans le tableau, et de retourner la valeur, la marche ou la liste des valeurs et le retour de la droite.

Bien sûr, dans la pratique, en général, vous ne pouvez pas faire cela, il gaspille trop de mémoire. Donc, vous n'avez tout basé sur un tableau fragmenté (où les entrées sont ceux que vous utilisez effectivement, tout le reste est implicitement null).

Il y a beaucoup de régimes et des astuces pour que cela fonctionne mieux, mais c'est l'essentiel.

Answer 4

Vous les gars sont très proches à l'explication de ce bien, mais manque un couple de choses. La table de hachage est juste un tableau. Le tableau lui-même contiendra quelque chose dans chaque logement. Au minimum vous permettra de stocker les hashvalue ou de la valeur elle-même dans cette fente. En plus de cela vous pouvez aussi stocker un lien/liste chaînée de valeurs qui ont percuté sur cette machine à sous, ou vous pouvez utiliser l'abordant la méthode. 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'est généralement pas indiquer l'emplacement dans lequel placer la valeur. Par exemple, un hashvalue pourrait être une valeur entière négative. Évidemment un nombre négatif ne peut pas pointer vers un tableau de l'emplacement. En outre, les valeurs de hachage aura tendance à souvent être plus nombreux que ce que les machines à sous disponibles. Ainsi, une autre calcul doit être effectué par la table de hachage lui-même à comprendre que la fente de la valeur doit aller dans. Cela se fait avec un module de mathématiques de l'opération comme:

uint slotIndex = hashValue % hashTableSize;

Cette valeur est la fente la valeur va aller dans. En abordant, si le logement est déjà rempli avec un autre hashvalue et/ou d'autres données, le module opération sera exécutée une fois de plus pour trouver l'emplacement suivant:

slotIndex = (reste + 1) % hashTableSize;

Je suppose qu'il y a peut être d'autres plus avancées des méthodes pour la détermination de l'index d'emplacement, mais c'est la commune que j'ai vu... seraient intéressés à tous les autres qui sont plus performants.

Avec le module méthode, si vous avez une talbe de dire la taille 1000, tout hashvalue qui est compris entre 1 et 1000 va aller dans le logement correspondant. Des valeurs Négatives, et toutes les valeurs supérieures à 1000 sera potentiellement entrer en collision fente de valeurs. Les chances que cela se produise dépendent à la fois sur votre méthode de hachage, ainsi que le nombre de totol éléments que vous ajoutez à la table de hachage. Généralement, il est conseillé d'effectuer la taille de la table de hachage telle que le nombre total de valeurs ajoutées, c'est seulement égale à environ 70% de sa taille. Si votre fonction de hachage fait un bon travail de même de la distribution, vous aurez tendance à avoir très peu ou pas de seau/fente collisions et il va effectuer très rapidement, permettant à la fois de recherche et les opérations d'écriture. Si le nombre total de valeurs à ajouter n'est pas connu à l'avance, faire un bon guestimate en utilisant tous les moyens, et puis redimensionner votre table de hachage, une fois le nombre d'éléments ajoutés à ce qu'il atteigne 70% de sa capacité.

J'espère que cela a aidé.

PS - En C# le GetHashCode() la méthode est assez lent et les résultats réels de la valeur de collisions dans un tas de conditions que j'ai testé. Pour de l'amusement, de construire votre propre hashfunction et essayer de l'obtenir à n'entrent JAMAIS en collision sur les données vous sont hachage, courir plus vite que GetHashCode, et ont une répartition assez égale. J'ai fait cela à l'aide de long au lieu de int taille hashcode valeurs et c'est très bien fonctionné jusqu'à 32 millions d'entrées hashvalues dans la table de hachage avec 0 collisions. Malheureusement je ne peux pas partager le code tel qu'il appartient à mon employeur... mais je peux vous révéler qu'il est possible pour certains domaines de données. Lorsque vous pouvez atteindre cet objectif, la table de hachage est TRÈS rapide. :)

Answer 5

C'est la façon dont il fonctionne dans ma compréhension:

Voici un exemple: l'image de l'ensemble de la table comme une série de seaux. Supposons que vous avez une mise en œuvre avec des alpha-numérique hash-codes et ont un compartiment pour chaque lettre de l'alphabet. Cette mise en place chaque élément dont le code de hachage commence par une lettre donnée dans le seau.

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

Comme la mesure de calculer le code de hachage, il n'y a rien de magique. Le but est juste d'avoir des objets différents de retour et les différents codes pour les objets égaux à rendement égal codes. Vous pourriez écrire une classe qui renvoie toujours le même entier comme un hash-code pour toutes les instances, mais vous serait essentiellement détruire l'utilité d'une table de hachage, comme il serait juste de devenir un géant de seau.