Phenquestions
Supposons que vous êtes propriétaire d'un grand magasin de provisions dans le comté où vous habitez. Supposons que vous habitez dans une grande zone, qui n'est pas une zone commerciale. Vous n'êtes pas le seul à avoir un magasin de provisions dans la région ; vous avez quelques concurrents. Et puis il vous vient à l'esprit que vous devez enregistrer les numéros de téléphone de vos clients dans un cahier. Bien sûr, le cahier est petit, et vous ne pouvez pas enregistrer tous les numéros de téléphone de tous vos clients.
Vous décidez donc de n'enregistrer que les numéros de téléphone de vos clients réguliers. Et donc vous avez un tableau avec deux colonnes. La colonne de gauche contient les noms des clients et la colonne de droite les numéros de téléphone correspondants. De cette façon, il y a une correspondance entre les noms des clients et les numéros de téléphone. La colonne de droite du tableau peut être considérée comme la table de hachage principale. Les noms des clients sont maintenant appelés clés et les numéros de téléphone sont appelés valeurs. Notez que lorsqu'un client part en transfert, vous devrez annuler sa ligne, permettant à la ligne de se vider ou d'être remplacée par celle d'un nouveau client régulier. Notez également qu'avec le temps, le nombre de clients réguliers peut augmenter ou diminuer, et ainsi la table peut augmenter ou diminuer.
Comme autre exemple de cartographie, supposons qu'il existe 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 (en présence et contribution). Le barman peut décider d'enregistrer les noms des membres et leur choix de boisson. Il élabore un tableau 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 de boisson est trouvé 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 autre boisson sucrée ou alcoolisée. Le barman 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 numérote les lignes à partir de zéro (i.e. 0, 1, 2, 3, 4, etc.), en descendant, un index par ligne. Avec cela, son problème est résolu, car un nom de membre correspond désormais à 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é sur l'index correspondant.
La colonne de valeurs (boissons) forme à elle seule la table de hachage de base. Dans la table modifiée, la colonne des indices et leurs valeurs associées (avec ou sans doublons) forment une table de hachage normale - la définition complète d'une table de hachage est donnée ci-dessous. Les clés (première colonne) ne font pas nécessairement partie de la table de hachage.
Comme autre exemple encore, considérons un serveur réseau où un utilisateur de son ordinateur client peut ajouter des informations, supprimer des informations ou modifier des informations. Il y a beaucoup d'utilisateurs pour le serveur. Chaque nom d'utilisateur correspond à un mot de passe stocké dans le serveur. Ceux qui maintiennent le serveur peuvent voir les noms d'utilisateur et le mot de passe correspondant, et ainsi pouvoir corrompre le travail des utilisateurs.
Le propriétaire du serveur décide donc de produire une fonction qui crypte un mot de passe avant qu'il ne soit stocké. Un utilisateur se connecte au serveur, avec son mot de passe normal compris. Cependant, maintenant, chaque mot de passe est stocké sous une forme cryptée. Si quelqu'un voit un mot de passe crypté et essaie de se connecter en l'utilisant, 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 à zéro, de sorte que chaque mot de passe crypté est associé à un index, alors la colonne d'indices et la colonne de mot de passe crypté forment une table de hachage normale. Les clés ne font pas nécessairement partie de la table de hachage.
A noter, dans ce cas, que chaque clé, qui est un mot de passe compris, correspond à un nom d'utilisateur. Donc, il y a un nom d'utilisateur qui correspond à une clé qui est mappée à un index, qui est associé à une valeur qui est une clé chiffré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 en pointeurs (références) et en listes chaînées, afin d'apprécier la suite de ce tutoriel.
Signification de la fonction de hachage et de la table de hachage
Déployer
Un tableau est un ensemble d'emplacements mémoire consécutifs. Tous les emplacements sont de la même taille. La valeur du 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 ; etc. Un tableau ne peut normalement pas augmenter ou réduire. Afin de modifier la taille (longueur) d'un tableau, un nouveau tableau doit être créé et les 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 supérieur à la taille du tableau. L'index résultant de la fonction de hachage est appelé une valeur de hachage ou un condensé ou un code de hachage ou simplement un hachage.
Table de hachage
Une table de hachage est un tableau avec des valeurs, aux indices desquels les clés sont mappées. Les clés sont indirectement mappées sur les valeurs. En fait, les clés sont dites mappées sur les valeurs, puisque 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 du tableau et pas vraiment aux valeurs, car il peut 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 (emplacements) sont appelées buckets.
Notez que certains seaux sont vides. Une table de hachage ne doit pas nécessairement avoir des valeurs dans tous ses buckets. Les valeurs dans les buckets ne doivent pas nécessairement être dans l'ordre croissant. Cependant, les indices auxquels ils sont associés sont par 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 une 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 compartiment associé à l'index haché, une nouvelle valeur peut être mise dans ce compartiment. 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 des 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 valeurs.
Une table de hachage est un tableau avec une fonction de hachage. La fonction prend une clé et hache un index correspondant, et connecte ainsi les clés aux valeurs, dans le tableau. Les clés ne doivent pas nécessairement faire partie de la table de hachage.
Pourquoi un tableau et non une liste liée pour la table de hachage
Le tableau d'une table de hachage peut être remplacé par une structure de données de liste chaînée, mais il y aurait un problème. Le premier élément d'une liste chaînée est naturellement à l'index 0 ; le deuxième élément est naturellement à l'indice 1 ; le troisième est naturellement à l'indice 2 ; etc. Le problème avec la liste chaîné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 se fait 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 le but est d'insérer une valeur, l'index haché peut déjà avoir une valeur associée, et c'est une collision ; la nouvelle valeur ne peut pas être mise là où il y a déjà une valeur. Il existe des moyens de résoudre les collisions - voir ci-dessous.
Pourquoi une collision se produit
Dans l'exemple de magasin d'approvisionnement 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, alors que le tableau a une taille limitée et ne peut pas prendre tous les clients. Ainsi, seules les boissons des clients réguliers sont stockées dans le tableau. La collision se produirait lorsqu'un client non régulier devient régulier. Les clients de la boutique forment un grand ensemble, tandis que le nombre de seaux pour les clients dans le tableau est limité.
Avec les tables de hachage, ce sont les valeurs des clés qui sont très probables, qui sont enregistrées. Lorsqu'une clé qui n'était pas probable, devient probable, il y aurait probablement une collision. En fait, la collision se produit toujours avec les tables de hachage.
Principes de base de la résolution des collisions
Deux approches de la résolution des collisions sont appelées chaînage séparé et adressage ouvert. En théorie, les clés ne devraient pas être dans la structure de données ou ne devraient pas faire partie de la table de hachage. Cependant, les deux approches nécessitent que la colonne clé précède la table de hachage et fasse partie de la structure globale. Au lieu que les clés se trouvent dans la colonne des clés, les pointeurs vers les clés peuvent se trouver dans la colonne des clés.
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 résolution peut avoir des compartiments 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 (ni au-dessus ni en dessous) de la valeur en collision. Donc deux ou trois valeurs finissent par avoir le même indice. Rarement plus de trois devraient avoir le même index.
Plusieurs valeurs peuvent-elles vraiment avoir le même indice 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 chaînée, qui contient une, deux ou trois valeurs en collision. Le diagramme suivant est un exemple de table de hachage pour le chaînage séparé des clients et de leurs numéros de téléphone :
Les seaux vides sont marqués de la lettre x. Le reste des emplacements ont des pointeurs vers des listes chaînées. Chaque élément de la liste chaînée a deux champs de données : un pour le nom du client et l'autre pour le numéro de téléphone. Un conflit se produit pour les clés : Peter Jones et Suzan Lee. Les valeurs correspondantes sont constituées de deux éléments d'une liste chaînée.
Pour les clés en conflit, le critère pour insérer la valeur est le même critère utilisé pour localiser (et lire) la valeur.
Adressage ouvert
Avec l'adressage ouvert, toutes les valeurs sont stockées dans le bucket array. Lorsqu'un conflit survient, la nouvelle valeur est insérée dans un seau vide, la nouvelle valeur correspondante pour le conflit, selon un certain critère. Le critère utilisé pour insérer une valeur en conflit est le même critère utilisé pour localiser (rechercher et lire) la valeur.
Le schéma suivant illustre la résolution des conflits avec l'adressage ouvert :
La fonction de hachage prend la clé, Peter Jones et hache l'index, 152, et stocke son numéro de téléphone dans le compartiment associé. Après un certain temps, la fonction de hachage hache le même index, 152 de la clé, Suzan Lee, entrant en collision avec l'index de Peter Jones. Pour résoudre ce problème, la valeur de Suzan Lee est stockée dans le compartiment de l'index suivant, 153, qui était vide. La fonction de hachage hache l'index, 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. Donc la valeur pour Robin Hood est placée dans le prochain seau vide, qui est celui de l'index 154.
Méthodes de résolution des conflits pour le chaînage séparé et l'adressage ouvert
Le chaînage séparé a ses méthodes de résolution des conflits, et l'adressage ouvert a également ses propres méthodes de résolution des conflits.
Méthodes de résolution des conflits de chaînage séparés
Les méthodes de chaînage séparé des tables de hachage sont brièvement expliquées maintenant :
Chaînage séparé avec des listes chaînées
Cette méthode est comme expliqué ci-dessus. Cependant, chaque élément de la liste chaînée ne doit pas nécessairement avoir le champ clé (e.g. champ nom du client ci-dessus).
Chaînage séparé avec des cellules de tête de liste
Dans cette méthode, le premier élément de la liste chaînée est stocké dans un bucket du tableau. Ceci est possible, si le type de données du tableau est l'élément de la liste chaînée.
Chaînage séparé avec d'autres structures
Toute autre structure de données, telle que l'arbre de recherche binaire à équilibrage automatique qui prend en charge les opérations requises, peut être utilisée à la place de la liste chaînée - voir plus loin.
Méthodes de résolution des conflits d'adressage ouverts
Une méthode pour résoudre les conflits dans l'adressage ouvert est appelée séquence de sonde. Trois séquences de sondes bien connues sont brièvement expliquées maintenant :
Sondage linéaire
Avec le sondage linéaire, lorsqu'un conflit se produit, le seau vide le plus proche sous le seau en conflit est recherché. De plus, avec le sondage linéaire, la clé et sa valeur sont stockées dans le même seau.
Sondage quadratique
Supposons que le conflit se produise à l'indice H. Le prochain emplacement vide (seau) à l'indice H+12 est utilisé; si c'est déjà occupé, alors le prochain vide à H+22 est utilisé, s'il est déjà occupé, alors le prochain vide à H + 32 est utilisé, et ainsi de suite. Il existe des variantes à cela.
Double hachage
Avec le double hachage, il y a deux fonctions de hachage. Le premier calcule (hachage) l'index. En cas de conflit, le second utilise la même clé pour déterminer jusqu'où 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 de clés est relativement petit et que chaque clé correspond à un entier particulier dans la table de hachage.
Dans le jeu de caractères ASCII, les caractères majuscules peuvent être mappés à leurs lettres 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 vaut 97, b vaut 98, c vaut 99, etc. Pour mapper de A à a, ajoutez 32 à 65 ; pour mapper de B à b, ajoutez 32 à 66 ; pour mapper de C à c, ajoutez 32 à 67 ; etc. Ici, les lettres majuscules sont les clés, et les lettres 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 buckets du tableau peuvent être vides. Ainsi, les compartiments du tableau de 64 à 0 peuvent être vides. La fonction de hachage ajoute simplement 32 au numéro de code majuscule pour obtenir l'index, et donc la lettre minuscule. Une telle fonction est une fonction de hachage parfaite.
Hachage d'indices entiers à entiers
Il existe différentes méthodes pour hacher un entier. L'un d'eux est appelé la méthode de division modulo (Fonction).
La fonction de hachage de division modulo
Une fonction dans un logiciel informatique n'est pas une fonction mathématique. En informatique (logiciel), une fonction consiste en un ensemble d'instructions précédées d'arguments. Pour la fonction de division modulo, les clés sont des nombres entiers et sont mappées aux indices du tableau de buckets. L'ensemble de clés est grand, donc seules les clés qui sont très susceptibles de se produire dans l'activité seraient mappées. Ainsi, des collisions se produisent lorsque des clés improbables doivent être mappé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 aussi appelé le modulo. Remarque : il est possible d'avoir un modulo de 0.
Pour ce hachage, la taille de la table est généralement une puissance de 2, e.g. 64 = 26 ou 256 = 28, 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'indice du tableau de buckets. La valeur associée dans le bucket est une valeur de votre choix (valeur pour la clé).
Hachage des clés de longueur variable
Ici, les clés du jeu 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 ont des tailles d'octets différentes, elles sont dites de longueur variable. L'une des méthodes de hachage de longueurs variables est appelée Radix Conversion Hashing.
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) = x0unek−1+X1unek−2+… +xk−2une1+Xk−1une0
Où (x0, x1,… , xk−1) sont les caractères de la chaîne d'entrée et a est une base, e.g. 29 (voir plus loin). 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 peut ne pas être nécessairement un nombre ou du texte. Cela peut aussi être un record. Un enregistrement est une liste écrite horizontalement. Dans une paire clé/valeur, chaque clé peut en fait faire référence à un autre texte, 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 opèrent sur la liste. Chaque élément de la liste peut consister en 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 c'est plus un système qu'une structure de données. Les clés et leurs valeurs correspondantes sont peu dépendantes les unes 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 sont très dépendantes les unes 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. Lors de 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 clé/valeur, où il n'y a pas de doublon 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 que, avec la table de hachage générale, les clés ne doivent pas être stockées. Le problème des valeurs dupliquées est naturellement résolu par les indices du tableau de buckets. Ne pas confondre entre valeurs dupliquées et collision à un index.
Puisqu'un tableau associatif est une structure de données, il comporte au moins les opérations suivantes :
Opérations sur les tableaux associatifs
insérer ou ajouter
Cela insère une nouvelle paire clé/valeur dans la collection, mappant la clé à sa valeur.
réaffecter
Cette opération remplace la valeur d'une clé particulière par 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 fonction de hachage. La fonction mappe les clés aux valeurs du tableau via les indices du tableau. Les clés ne doivent pas nécessairement faire partie de la structure de données. Le jeu 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 séparé, soit par l'approche d'adressage ouvert. Un tableau associatif est un cas particulier de la structure de données de table de hachage.
