Tutoriel de structure de données de table de hachage

En informatique, le mot «map» signifie lier un élément dans un ensemble à un autre élément dans un autre ensemble. Imaginez que sur une page, il y a des mots dans un cercle à gauche, et sur le côté droit de la même page, il y a un autre cercle dans lequel il y a d'autres mots. Supposons que dans chaque cercle, les mots sont écrits au hasard, dispersés dans le cercle. Supposons également que les mots du cercle de gauche sont appelés clés, et les mots du cercle droit sont appelés valeurs. Si une flèche est tirée de chaque mot de gauche à chaque mot à droite, alors il serait dit que les clés ont été mappées aux valeurs.

Supposons que vous êtes propriétaire d'une grande boutique de provisions dans le comté où vous vivez. Supposons que vous vivez dans une grande zone, qui n'est pas une zone commerciale. Vous n'êtes pas le seul à avoir une boutique d'approvisionnement dans la région; Vous avez quelques concurrents. Et puis il vous arrive que vous devriez enregistrer les numéros de téléphone de vos clients dans un livre d'exercices. Bien sûr, le livre d'exercices est petit et vous ne pouvez pas enregistrer tous les numéros de téléphone pour tous vos clients.

Vous décidez donc d'enregistrer uniquement les numéros de téléphone de vos clients réguliers. Et donc vous avez une table avec deux colonnes. La colonne de gauche a les noms des clients, et la colonne à droite a les numéros de téléphone correspondants. De cette façon, il existe une cartographie entre les noms de clients et les numéros de téléphone. La colonne de droite de la table peut être considérée comme le tableau de hachage central. Les noms de clients sont maintenant appelés clés et les numéros de téléphone sont appelés valeurs. Notez que lorsqu'un client se transfère, vous devrez annuler sa ligne, permettant à la ligne vide ou être remplacée par celle d'un nouveau client ordinaire. Notez également qu'avec le temps, le nombre de clients réguliers peut augmenter ou diminuer, et donc le tableau peut croître ou rétrécir.

Comme autre exemple de cartographie, supposons qu'il y a un club d'agriculteurs dans un comté. Bien sûr, tous les agriculteurs ne seront pas membres du club. Certains membres du club ne seront pas des membres réguliers (présence et contribution). Le bar-homme peut décider d'enregistrer les noms des membres et leur choix de boisson. Il développe une table de deux colonnes. Dans la colonne de gauche, il écrit les noms des membres du club. Dans la colonne de droite, il écrit le choix de boisson correspondant.

Il y a un problème ici: il y a des doublons dans la colonne de droite. C'est-à-dire que le même nom d'une boisson se trouve plus d'une fois. En d'autres termes, différents membres boivent la même boisson sucrée ou la même boisson alcoolisée, tandis que d'autres membres boivent une boisson sucrée ou alcoolique différente. Le Bar-Man décide de résoudre ce problème en insérant une colonne étroite entre les deux colonnes. Dans cette colonne du milieu, en commençant par le haut, il compte les lignes à partir de zéro (i.e. 0, 1, 2, 3, 4, etc.), en descendant, un indice par rang. Avec cela, son problème est résolu, car un nom de membre se correspond maintenant à un index, et non au nom d'une boisson. Ainsi, comme une boisson est identifiée par un index, un nom de client est mappé à l'index correspondant.

La colonne des valeurs (boissons) seule forme le tableau de hachage de base. Dans le tableau modifié, la colonne des indices et leurs valeurs associées (avec ou sans doublons) forment un tableau de hachage normal - une définition complète d'un tableau de hachage est donnée ci-dessous. Les touches (première colonne) ne font pas nécessairement partie de la table de hachage.

En tant qu'un autre exemple, considérez un serveur réseau où un utilisateur de son ordinateur client peut ajouter des informations, supprimer certaines informations ou modifier certaines informations. Il existe de nombreux utilisateurs pour le serveur. Chaque nom d'utilisateur correspond à un mot de passe stocké sur le serveur. Ceux qui entretiennent le serveur peuvent voir les noms d'utilisateur et le mot de passe correspondant, et donc être en mesure de corrompre le travail des utilisateurs.

Le propriétaire du serveur décide donc de produire une fonction qui crypte un mot de passe avant d'être stocké. Un utilisateur se connecte au serveur, avec son mot de passe comprise normal. Cependant, maintenant, chaque mot de passe est stocké sous une forme chiffrée. Si quelqu'un voit un mot de passe crypté et essaie de se connecter à l'utiliser, cela ne fonctionnera pas, car la connexion, reçoit un mot de passe compris par le serveur, et non un mot de passe crypté.

Dans ce cas, le mot de passe compris est la clé, et le mot de passe crypté est la valeur. Si le mot de passe crypté se trouve dans une colonne de mots de passe cryptés, alors cette colonne est une table de hachage de base. Si cette colonne est précédée d'une autre colonne avec des indices commençant à partir de zéro, de sorte que chaque mot de passe crypté est associé à un index, puis la colonne des indices et la colonne de mot de passe cryptée, forment un tableau de hachage normal. Les clés ne font pas nécessairement partie de la table de hachage.

Notez, dans ce cas, que chaque clé, qui est un mot de passe compris, correspond à un nom d'utilisateur. Il y a donc un nom d'utilisateur qui correspond à une clé qui est mappée à un index, qui est associé à une valeur qui est une clé cryptée.

La définition d'une fonction de hachage, la définition complète d'une table de hachage, la signification d'un tableau et d'autres détails sont donnés ci-dessous. Vous devez avoir des connaissances dans les pointeurs (références) et les listes liées, afin d'apprécier le reste de ce tutoriel.

Signification de la fonction de hachage et de la table de hachage

Déployer

Un tableau est un ensemble d'emplacements de mémoire consécutifs. Tous les emplacements sont de la même taille. La valeur dans le premier emplacement est accessible avec l'index, 0; La valeur dans le deuxième emplacement est accessible avec l'index, 1; La troisième valeur est accessible avec l'index, 2; quatrième avec index, 3; et ainsi de suite. Un tableau ne peut normalement pas augmenter ou rétrécir. Afin de modifier la taille (longueur) d'un tableau, un nouveau tableau doit être créé et des valeurs correspondantes copiées dans le nouveau tableau. Les valeurs d'un tableau sont toujours du même type.

Fonction de hachage

Dans le logiciel, une fonction de hachage est une fonction qui prend une clé et produit un index correspondant pour une cellule de tableau. Le tableau est de taille fixe (longueur fixe). Le nombre de clés est de taille arbitraire, généralement plus grande que la taille du tableau. L'index résultant de la fonction de hachage est appelé une valeur de hachage ou un digest ou un code de hachage ou simplement un hachage.

Table de hachage

Une table de hachage est un tableau avec des valeurs, aux indices duquel, les clés sont mappées. Les clés sont indirectement mappées aux valeurs. En fait, les clés seraient mappées aux valeurs, car chaque index est associé à une valeur (avec ou sans doublons). Cependant, la fonction qui fait la cartographie (i.e. hachage) relie les clés aux indices de tableau et pas vraiment aux valeurs, car il pourrait y avoir des doublons dans les valeurs. Le diagramme suivant illustre une table de hachage pour les noms des personnes et leurs numéros de téléphone. Les cellules du tableau (fentes) sont appelées seaux.

Notez que certains seaux sont vides. Une table de hachage ne doit pas nécessairement avoir des valeurs dans tous ses seaux. Les valeurs dans les seaux ne doivent pas nécessairement être dans l'ordre croissant. Cependant, les indices auxquels ils sont associés sont en ordre croissant. Les flèches indiquent la cartographie. Notez que les clés ne sont pas dans un tableau. Ils n'ont pas besoin d'être dans aucune structure. Une fonction de hachage prend n'importe quelle clé et hache un index pour un tableau. S'il n'y a pas de valeur dans le seau associé à l'index haché, une nouvelle valeur peut être mise dans ce seau. La relation logique est entre la clé et l'index, et non entre la clé et la valeur associée à l'index.

Les valeurs d'un tableau, comme celles de cette table de hachage, sont toujours du même type de données. Une table de hachage (seaux) peut connecter les clés aux valeurs de différents types de données. Dans ce cas, les valeurs du tableau sont toutes des pointeurs, pointant vers différents types de valeur.

Une table de hachage est un tableau avec une fonction de hachage. La fonction prend une clé et hache un index correspondant, et connecte donc les clés aux valeurs, dans le tableau. Les clés ne doivent pas faire partie de la table de hachage.

Pourquoi le tableau et non la liste liée pour la table de hachage

Le tableau pour une table de hachage peut être remplacé par une structure de données de liste liée, mais il y aurait un problème. Le premier élément d'une liste liée est naturellement à l'index, 0; Le deuxième élément est naturellement à l'index, 1; Le troisième est naturellement à l'index, 2; et ainsi de suite. Le problème avec la liste liée est que pour récupérer une valeur, la liste doit être itérée, et cela prend du temps. L'accès à une valeur dans un tableau est par accès aléatoire. Une fois l'indice connu, la valeur est obtenue sans itération; Cet accès est plus rapide.

Collision

La fonction de hachage prend une clé et hache l'index correspondant, pour lire la valeur associée ou pour insérer une nouvelle valeur. Si le but est de lire une valeur, il n'y a pas de problème (pas de problème), jusqu'à présent. Cependant, si l'objectif est d'insérer une valeur, l'indice haché peut déjà avoir une valeur associée, et c'est une collision; La nouvelle valeur ne peut pas être mise en place où il y a déjà une valeur. Il existe des moyens de résoudre la collision - voir ci-dessous.

Pourquoi la collision se produit

Dans l'exemple de la boutique de disposition ci-dessus, les noms des clients sont les clés, et les noms des boissons sont les valeurs. Notez que les clients sont trop nombreux, tandis que le tableau a une taille limitée et ne peut pas prendre tous les clients. Ainsi, seules les boissons de clients réguliers sont stockées dans le tableau. La collision se produirait lorsqu'un client non régulier deviendrait régulièrement. Les clients de la boutique forment un grand ensemble, tandis que le nombre de seaux pour les clients dans le tableau est limité.

Avec des tables de hachage, ce sont les valeurs des clés très probables, qui sont enregistrées. Lorsqu'une clé qui était peu probable devient probable, il y aurait probablement une collision. En fait, la collision se produit toujours avec des tables de hachage.

Bases de résolution de collision

Deux approches de la résolution de collision sont appelées chaînage séparés et adressage ouvert. En théorie, les clés ne doivent pas être dans la structure des données ou ne doivent pas faire partie du tableau de hachage. Cependant, les deux approches nécessitent que la colonne clé précède le tableau de hachage et fait partie de la structure globale. Au lieu que les clés soient dans la colonne des touches, les pointeurs vers les clés peuvent être dans la colonne des touches.

Une table de hachage pratique comprend une colonne de clés, mais cette colonne de clé ne fait pas officiellement partie de la table de hachage.

L'une ou l'autre approche de la résolution peut avoir des seaux vides, pas nécessairement à la fin du tableau.

Chaînage séparé

Dans un chaînage séparé, lorsqu'une collision se produit, la nouvelle valeur est ajoutée à droite (pas au-dessus ou en dessous) de la valeur colladée. Donc deux ou trois valeurs finissent par avoir le même index. Rarement plus de trois devraient avoir le même indice.

Plus d'une valeur peut-elle vraiment avoir le même index dans un tableau? - Non. Ainsi, dans de nombreux cas, la première valeur de l'index est un pointeur vers une structure de données de liste liée, qui contient les valeurs colladées une, deux ou trois. Le diagramme suivant est un exemple de table de hachage pour un chaînage séparé de clients et leurs numéros de téléphone:

Les seaux vides sont marqués de la lettre x. Les autres créneaux ont des pointeurs vers des listes liées. Chaque élément de la liste liée a deux champs de données: l'un pour le nom du client et l'autre pour le numéro de téléphone. Le conflit se produit pour les clés: Peter Jones et Suzan Lee. Les valeurs correspondantes se composent de deux éléments d'une liste liée.

Pour les clés conflictuelles, le critère pour insérer la valeur est le même critère utilisé pour localiser (et lire) la valeur.

Adressage ouvert

Avec une adresse ouverte, toutes les valeurs sont stockées dans le tableau de seau. Lorsque le conflit se produit, la nouvelle valeur est insérée dans un godet vide nouveau la valeur correspondante du conflit, en suivant certains critères. Le critère utilisé pour insérer une valeur au conflit est le même critère utilisé pour localiser (rechercher et lire) la valeur.

Le diagramme suivant illustre la résolution des conflits avec l'adresse ouverte:

La fonction de hachage prend la clé, Peter Jones et hache l'index, 152, et stocke son numéro de téléphone au seau associé. Après un certain temps, la fonction de hachage hache le même index, 152 de la clé, Suzan Lee, en collision avec l'index de Peter Jones. Pour résoudre ce problème, la valeur de Suzan Lee est stockée dans le seau de l'index suivant, 153, qui était vide. La fonction de hachage hache l'indice, 153 pour la clé, Robin Hood, mais cet index a déjà été utilisé pour résoudre le conflit pour une clé précédente. Ainsi, la valeur de Robin Hood est placée dans le seau vide suivant, qui est celui de l'index 154.

Méthodes de résolution des conflits pour un chaînage séparé et un adressage ouvert

Le chaînage séparé a ses méthodes de résolution des conflits, et l'ouverture ouverte a également ses propres méthodes de résolution des conflits.

Méthodes pour résoudre les conflits de chaînage séparés

Les méthodes de tables de hachage de chaînage séparées sont brièvement expliquées maintenant:

Chaîne séparé avec des listes liées

Cette méthode est comme expliqué ci-dessus. Cependant, chaque élément de la liste liée ne doit pas nécessairement avoir le champ clé (E.g. Champ de nom du client ci-dessus).

Chaîne séparée avec les cellules de la tête de liste

Dans cette méthode, le premier élément de la liste liée est stocké dans un seau du tableau. Ceci est possible, si le type de données du tableau est l'élément de la liste liée.

Séparez le chaînage avec d'autres structures

Toute autre structure de données, comme l'arbre de recherche binaire auto-équilibré qui prend en charge les opérations requises, peut être utilisée à la place de la liste liée - voir plus tard.

Méthodes pour résoudre les conflits d'adressage ouvert

Une méthode pour résoudre les conflits en adressage ouvert est appelé séquence de sonde. Trois séquences de sondes bien connues sont brièvement expliquées maintenant:

Sondage linéaire

Avec sondage linéaire, lorsqu'un conflit se produit, le seau vide le plus proche sous le seau au conflit, est recherché. De plus, avec sondage linéaire, la clé et sa valeur sont stockées dans le même seau.

Sondage quadratique

Supposer que le conflit se produit à l'indice h. La fente vide suivante (seau) à l'index h + 1² est utilisé; Si cela est déjà occupé, alors le prochain vide à H + 2² est utilisé, si cela est déjà occupé, alors le prochain vide à H + 3² est utilisé, et ainsi de suite. Il y a des variantes à ce sujet.

Double hachage

Avec le double hachage, il y a deux fonctions de hachage. Le premier calcule (hachages) l'index. Si un conflit se produit, le second utilise la même clé pour déterminer à quel point la valeur doit être insérée. Il y a plus à cela - voir plus tard.

Fonction de hachage parfaite

Une fonction de hachage parfaite est une fonction de hachage qui ne peut entraîner aucune collision. Cela peut se produire lorsque l'ensemble des clés est relativement petit, et chaque clé correspond à un entier particulier dans la table de hachage.

Dans le jeu de caractères ASCII, les caractères en haut du boîtier peuvent être mappés à leurs lettres en minuscules correspondantes à l'aide d'une fonction de hachage. Les lettres sont représentées dans la mémoire de l'ordinateur sous forme de nombres. Dans le jeu de caractères ASCII, A est 65, B est 66, C est 67, etc. et A est 97, B est 98, C est 99, etc. Pour mapper de A à A, ajoutez 32 à 65; Pour mapper de B à B, ajoutez 32 à 66; pour mapper de C à C, ajouter 32 à 67; et ainsi de suite. Ici, les lettres supérieures sont les clés, et les lettres en minuscules sont les valeurs. La table de hachage pour cela peut être un tableau dont les valeurs sont les indices associés. N'oubliez pas que les seaux du tableau peuvent être vides. Donc les seaux dans le tableau de 64 à 0 peuvent être vides. La fonction de hachage ajoute simplement 32 au numéro de code de cas supérieur pour obtenir l'index, et donc la lettre en bas de la case. Une telle fonction est une fonction de hachage parfaite.

Hachage de l'indice entier aux indices entiers

Il existe différentes méthodes pour le hachage entier. L'un d'eux est appelé la méthode de la division modulo (fonction).

La fonction de hachage de la division modulo

Une fonction dans les logiciels informatiques n'est pas une fonction mathématique. Dans l'informatique (logiciel), une fonction se compose d'un ensemble de déclarations précédées par des arguments. Pour la fonction de division modulo, les clés sont des entiers et sont mappées sur des indices de la table de seaux. L'ensemble des clés est grand, donc seules les clés qui sont très susceptibles de se produire dans l'activité seraient cartographiées. Les collisions se produisent donc lorsque des clés improbables doivent être cartographiées.

Dans la déclaration,

20/6 = 3R2

20 est le dividende, 6 est le diviseur, et 3 reste 2 est le quotient. Le reste 2 est également appelé le modulo. Remarque: il est possible d'avoir un modulo de 0.

Pour ce hachage, la taille du tableau est généralement une puissance de 2, e.g. 64 = 2⁶ ou 256 = 2⁸, etc. Le diviseur de cette fonction de hachage est un nombre premier proche de la taille du tableau. Cette fonction divise la clé par le diviseur et renvoie le modulo. Le modulo est l'index du tableau de seaux. La valeur associée dans le seau est une valeur de votre choix (valeur pour la clé).

Touches de longueur variable de hachage

Ici, les clés de l'ensemble de clés sont des textes de différentes longueurs. Différents entiers peuvent être stockés dans la mémoire en utilisant le même nombre d'octets (la taille d'un caractère anglais est un octet). Lorsque différentes clés sont de tailles d'octets différentes, elles seraient de longueur variable. L'une des méthodes de longueur variable de hachage est appelée hachage de conversion Radix.

Hachage de conversion Radix

Dans une chaîne, chaque caractère de l'ordinateur est un nombre. Dans cette méthode,

Code de hachage (index) = x₀un^{k - 1}+X₁un^{k - 2}+… + X_{k - 2}un¹+X_{k - 1}un⁰

Où (x0, x1,…, xk - 1) sont les caractères de la chaîne d'entrée et a est un radix, e.g. 29 (voir plus tard). k est le nombre de caractères dans la chaîne. Il y a plus à cela - voir plus tard.

Clés et valeurs

Dans une paire clé / valeur, une valeur ne peut pas nécessairement être un nombre ou un texte. Cela peut aussi être un record. Un enregistrement est une liste écrite horizontalement. Dans une paire de touches / valeur, chaque touche peut réellement se référer à un autre texte ou numéro ou enregistrement.

Tableau associatif

Une liste est une structure de données, où les éléments de la liste sont liés, et il existe un ensemble d'opérations qui fonctionnent sur la liste. Chaque élément de liste peut être composé d'une paire d'éléments. La table de hachage générale avec ses clés peut être considérée comme une structure de données, mais elle est plus un système qu'une structure de données. Les clés et leurs valeurs correspondantes ne dépendent pas très des autres. Ils ne sont pas très liés les uns aux autres.

D'un autre côté, un tableau associatif est une chose similaire, mais les clés et leurs valeurs dépendent très les uns des autres; Ils sont très liés les uns aux autres. Par exemple, vous pouvez avoir un tableau associatif de fruits et leurs couleurs. Chaque fruit a naturellement sa couleur. Le nom du fruit est la clé; La couleur est la valeur. Pendant l'insertion, chaque clé est insérée avec sa valeur. Lors de la suppression, chaque clé est supprimée avec sa valeur.

Un tableau associatif est une structure de données de table de hachage composée de paires de clés / valeur, où il n'y a pas de double pour les clés. Les valeurs peuvent avoir des doublons. Dans cette situation, les clés font partie de la structure. C'est-à-dire que les clés doivent être stockées, alors qu'avec la table générale, les clés n'ont pas à être stockées. Le problème des valeurs dupliqués est naturellement résolu par les indices du tableau de seaux. Ne confondez pas entre les valeurs dupliquées et la collision à un index.

Étant donné qu'un tableau associatif est une structure de données, est au moins les opérations suivantes:

Opérations de tableau associatif

insérer ou ajouter

Cela insère une nouvelle paire de clés / valeur dans la collection, cartographier la clé de sa valeur.

réaffecter

Cette opération remplace la valeur d'une clé particulière à une nouvelle valeur.

Supprimer ou supprimer

Cela supprime une clé plus sa valeur correspondante.

chercher

Cette opération recherche la valeur d'une clé particulière et renvoie la valeur (sans la supprimer).

Conclusion

Une structure de données de table de hachage se compose d'un tableau et d'une fonction. La fonction est appelée une fonction de hachage. La fonction mappe les touches des valeurs dans le tableau via les indices du tableau. Les clés ne doivent pas nécessairement faire partie de la structure de données. L'ensemble de clés est généralement plus grand que les valeurs stockées. Lorsqu'une collision se produit, elle est résolue soit par l'approche de chaînage distincte, soit par l'approche d'adressage ouvert. Un tableau associatif est un cas particulier de la structure des données de la table de hachage.