Table de hachage en C++

Fonction de hachage

Dans cette section, nous discuterons de la fonction de hachage qui permet d'exécuter le code de hachage de la clé associée de l'élément de données dans la structure de données, comme mentionné dans ce qui suit :

Le processus d'exécution de l'index d'un tableau est appelé hachage. Parfois, le même type de code est exécuté pour générer le même index en utilisant les mêmes clés appelées collisions qui sont gérées via différents chaînages (création de listes chaînées) et mise en œuvre de stratégies d'adressage ouvert.

Fonctionnement de la table de hachage en C++

Les pointeurs vers les valeurs réelles sont conservés dans la table de hachage. Il utilise une clé pour rechercher l'index d'un tableau auquel les valeurs des clés doivent être stockées à l'emplacement souhaité dans un tableau. Nous avons pris la table de hachage de taille 10 comme mentionné ci-dessous :

Prenons au hasard n'importe quelle donnée par rapport à différentes clés et stockons ces clés dans une table de hachage en calculant simplement l'index. Ainsi, les données sont stockées par rapport aux clés de l'index calculé à l'aide d'une fonction de hachage. Supposons que nous prenions un data = {14,25,42,55,63,84} et des clés =[ 15,9,5,25,66,75 ].

Calculez l'index de ces données à l'aide de la fonction de hachage. La valeur de l'indice est mentionnée dans ce qui suit :

Après avoir créé l'index d'un tableau, placez les données par rapport à la clé sur l'index exact d'un tableau donné, comme décrit précédemment.

Après cela, nous pouvons voir qu'une collision se produit si deux clés ou plus ont le même code de hachage, ce qui entraîne le même index des éléments du tableau. Nous avons une solution pour éviter les risques de collision : sélectionner une bonne méthode de hachage et mettre en œuvre des stratégies précises.

Discutons maintenant des différentes techniques de mise en œuvre à l’aide d’exemples appropriés.

Exemple : ajouter des données dans une table de hachage à l'aide d'une technique de hachage ouvert

Dans cet exemple, nous prenons une technique d'implémentation comme Open Hashing pour éviter les collisions dans la table de hachage. En hachage ou chaînage ouvert, nous créons une liste chaînée pour enchaîner les valeurs de la table de hachage. L'extrait de code de cet exemple est joint ci-dessous et décrit la technique de hachage ouvert :

C'est un exemple très intéressant : nous construisons une liste chaînée et insérons les données dans la table de hachage. Tout d'abord, nous définissons les bibliothèques au début du programme. Le < liste > La bibliothèque est utilisée pour l'implémentation de la liste chaînée. Après cela, nous construisons une classe nommée « HashTable » et créons les attributs de la classe qui sont privés en tant que taille de table et tableau de table à l'aide du mot-clé « private : ». N'oubliez pas que les attributs privés ne sont pas utilisables en dehors de la classe. Ici, nous prenons la taille du tableau comme « 10 ». Nous initialisons la méthode de hachage en utilisant ceci et calculons l'index de la table de hachage. Dans la fonction de hachage, on passe la clé et la taille de la table de hachage.

Nous construisons quelques fonctions requises et rendons ces fonctions publiques dans la classe. N'oubliez pas que les fonctions publiques sont utilisables n'importe où en dehors de la classe. Nous utilisons le mot-clé « public : » pour démarrer la partie publique du cours. . Puisque nous voulons ajouter de nouveaux éléments à la table de hachage, nous créons une fonction nommée « InsertHash » avec une clé comme argument de la fonction. Dans la fonction « insert », on initialise la variable d'index. Nous passons la fonction de hachage à la variable d'index. Après cela, transmettez la variable d'index à la liste chaînée tableHas[]en utilisant la méthode « push » pour insérer un élément dans la table.

Après cela, nous construisons une fonction « viewHashTab » pour afficher la table de hachage afin de voir les données nouvellement insérées. Dans cette fonction, nous prenons une boucle « for » qui recherche les valeurs jusqu'à la fin de la table de hachage. Assurez-vous que les valeurs sont stockées dans le même index que celui développé à l'aide d'une fonction de hachage. Dans la boucle, nous transmettons les valeurs à leur index respectif et terminons la classe ici. Dans la fonction « main », on prend l'objet d'une classe nommée « hasTable ». A l'aide de cet objet de classe, on peut accéder à la méthode d'insertion en passant la clé dans la méthode. La clé que nous avons passée dans la fonction « main » est calculée dans la fonction « insert » qui renvoie la position de l'index dans la table de hachage. Nous avons affiché la table de hachage en appelant la fonction « view » à l'aide d'un objet « Class ».

La sortie de ce code est jointe ci-dessous :

Comme nous pouvons le voir, la table de hachage est créée avec succès à l'aide de la liste chaînée en C++. Le chaînage ouvert est utilisé pour éviter la collision du même index.

Conclusion

En fin de compte, nous avons conclu qu'une table de hachage est la technique la plus émergente pour stocker et obtenir les clés avec des paires de valeurs afin de gérer efficacement d'énormes quantités de données. Les risques de collision sont très élevés dans la table de hachage, détruisant les données et leur stockage. Nous pouvons surmonter cette collision en utilisant différentes techniques de gestion des tables de hachage. En développant la table de hachage en C++, les développeurs peuvent augmenter les performances en utilisant la technique la mieux adaptée pour stocker les données dans la table de hachage. Nous espérons que cet article vous sera utile pour votre compréhension de la table de hachage.