hash table c programs implement hash table
Ce didacticiel explique les tables de hachage et les cartes de hachage C ++. Vous découvrirez également les applications et l'implémentation de table de hachage en C ++:
Le hachage est une technique qui permet de mapper une grande quantité de données sur une table plus petite en utilisant une «fonction de hachage».
En utilisant la technique de hachage, nous pouvons rechercher les données plus rapidement et plus efficacement par rapport à d'autres techniques de recherche telles que la recherche linéaire et binaire.
Laissez-nous comprendre la technique de hachage avec un exemple dans ce tutoriel.
=> Lisez la série de formations Easy C ++.
Ce que vous apprendrez:
Hashing en C ++
Prenons l'exemple d'une bibliothèque universitaire qui abrite des milliers de livres. Les livres sont classés en fonction des sujets, des départements, etc. Cependant, chaque section contiendra de nombreux livres, ce qui rend la recherche de livres très difficile.
Ainsi, pour surmonter cette difficulté, nous attribuons un numéro ou une clé unique à chaque livre afin que nous connaissions instantanément l'emplacement du livre. Ceci est en effet réalisé par hachage.
Poursuivant notre exemple de bibliothèque, au lieu d'identifier chaque livre en fonction de son département, sujet, section, etc. qui peut résulter en une très longue chaîne, nous calculons une valeur entière unique ou une clé pour chaque livre de la bibliothèque à l'aide d'une fonction unique et stockez ces clés dans une table séparée.
La fonction unique mentionnée ci-dessus est appelée «fonction de hachage» et la table séparée est appelée «table de hachage». Une fonction de hachage est utilisée pour mapper la valeur donnée à une clé unique particulière dans la table de hachage. Cela se traduit par un accès plus rapide aux éléments. Plus la fonction de hachage est efficace, plus le mappage de chaque élément avec la clé unique sera efficace.
Considérons une fonction de hachage h (x) qui mappe la valeur ' X ' à ' x% 10 ”Dans le tableau. Pour les données données, nous pouvons construire une table de hachage contenant des clés ou des codes de hachage ou des hachages comme indiqué dans le diagramme ci-dessous.
Dans le diagramme ci-dessus, nous pouvons voir que les entrées du tableau sont mappées à leurs positions dans la table de hachage à l'aide d'une fonction de hachage.
Ainsi, nous pouvons dire que le hachage est implémenté en deux étapes comme mentionné ci-dessous:
#1) La valeur est convertie en une clé entière unique ou un hachage à l'aide d'une fonction de hachage. Il est utilisé comme index pour stocker l'élément d'origine, qui tombe dans la table de hachage.
Dans le diagramme ci-dessus, la valeur 1 dans la table de hachage est la clé unique pour stocker l'élément 1 à partir du tableau de données indiqué sur la LHS du diagramme.
#deux) L'élément du tableau de données est stocké dans la table de hachage où il peut être rapidement récupéré à l'aide de la clé hachée. Dans le diagramme ci-dessus, nous avons vu que nous avons stocké tous les éléments dans la table de hachage après avoir calculé leurs emplacements respectifs à l'aide d'une fonction de hachage. Nous pouvons utiliser les expressions suivantes pour récupérer les valeurs de hachage et l'index.
hash = hash_func(key) index = hash % array_sizeFonction de hachage
Nous avons déjà mentionné que l'efficacité du mappage dépend de l'efficacité de la fonction de hachage que nous utilisons.
Une fonction de hachage doit essentiellement remplir les conditions suivantes:
- Facile à calculer: Une fonction de hachage, devrait être facile à calculer les clés uniques.
- Moins de collision: Lorsque les éléments correspondent aux mêmes valeurs de clé, il se produit une collision. Il doit y avoir un minimum de collisions dans la mesure du possible dans la fonction de hachage utilisée. Les collisions étant inévitables, nous devons utiliser des techniques de résolution de collision appropriées pour prendre en charge les collisions.
- Distribution uniforme: La fonction de hachage doit entraîner une distribution uniforme des données dans la table de hachage et empêcher ainsi le clustering.
Table de hachage C ++
La table de hachage ou une carte de hachage est une structure de données qui stocke des pointeurs vers les éléments du tableau de données d'origine.
Dans notre exemple de bibliothèque, la table de hachage de la bibliothèque contiendra des pointeurs vers chacun des livres de la bibliothèque.
Le fait d'avoir des entrées dans la table de hachage facilite la recherche d'un élément particulier dans le tableau.
Comme déjà vu, la table de hachage utilise une fonction de hachage pour calculer l'index dans le tableau de compartiments ou d'emplacements à l'aide desquels la valeur souhaitée peut être trouvée.
Prenons un autre exemple avec le tableau de données suivant:
Supposons que nous ayons une table de hachage de taille 10 comme indiqué ci-dessous:
Utilisons maintenant la fonction de hachage ci-dessous.
Hash_code = Key_value % size_of_hash_tableCela équivaudra à Hash_code = Key_value% 10
En utilisant la fonction ci-dessus, nous mappons les valeurs de clé aux emplacements de la table de hachage, comme indiqué ci-dessous.
| Élément de données | Fonction de hachage | Hash_code |
|---|---|---|
| 22 | 22% 10 = 2 | deux |
| 25 | 25% 10 = 5 | 5 |
| 27 | 27% 10 = 7 | 7 |
| 46 | 46% 10 = 6 | 6 |
| 70 | 70% 10 = 0 | 0 |
| 89 | 89% 10 = 9 | 9 |
| 31 | 31% 10 = 1 | 1 |
En utilisant le tableau ci-dessus, nous pouvons représenter la table de hachage comme suit.
Ainsi, lorsque nous avons besoin d'accéder à un élément à partir de la table de hachage, il faudra juste un temps O (1) pour faire la recherche.
Collision
Nous calculons généralement le code de hachage à l'aide de la fonction de hachage afin de pouvoir mapper la valeur de clé au code de hachage dans la table de hachage. Dans l'exemple ci-dessus du tableau de données, insérons une valeur 12. Dans ce cas, le hash_code pour la valeur de clé 12 sera 2. (12% 10 = 2).
Mais dans la table de hachage, nous avons déjà un mappage vers la valeur-clé 22 pour hash_code 2 comme indiqué ci-dessous:
Comme indiqué ci-dessus, nous avons le même code de hachage pour deux valeurs, 12 et 22, c'est-à-dire 2. Lorsqu'une ou plusieurs valeurs clés correspondent au même emplacement, cela entraîne une collision. Ainsi, l'emplacement du code de hachage est déjà occupé par une valeur de clé et une autre valeur de clé doit être placée au même emplacement.
qu'est-ce qu'un bon fournisseur de messagerie
Dans le cas du hachage, même si nous avons une table de hachage de très grande taille, une collision est forcément là. En effet, nous trouvons une petite valeur unique pour une grande clé en général, il est donc tout à fait possible qu'une ou plusieurs valeurs aient le même code de hachage à un moment donné.
Étant donné qu'une collision est inévitable dans le hachage, nous devons toujours rechercher des moyens de prévenir ou de résoudre la collision. Il existe différentes techniques de résolution de collision que nous pouvons utiliser pour résoudre la collision qui se produit pendant le hachage.
Techniques de résolution de collision
Voici les techniques que nous pouvons utiliser pour résoudre les collisions dans la table de hachage.
Chaînage séparé (hachage ouvert)
Il s'agit de la technique de résolution de collision la plus courante. Ceci est également connu sous le nom de hachage ouvert et est implémenté à l'aide d'une liste liée.
java interview question et réponses pour les nouveaux
Dans une technique de chaînage distincte, chaque entrée de la table de hachage est une liste chaînée. Lorsque la clé correspond au code de hachage, elle est entrée dans une liste correspondant à ce code de hachage particulier. Ainsi, lorsque deux clés ont le même code de hachage, les deux entrées sont entrées dans la liste chaînée.
Pour l'exemple ci-dessus, le chaînage séparé est représenté ci-dessous.
Le diagramme ci-dessus représente le chaînage. Ici, nous utilisons la fonction mod (%). Nous voyons que lorsque deux valeurs clés correspondent au même code de hachage, nous lions ces éléments à ce code de hachage à l'aide d'une liste liée.
Si les clés sont uniformément réparties dans la table de hachage, le coût moyen de recherche de la clé particulière dépend du nombre moyen de clés dans cette liste liée. Ainsi, le chaînage séparé reste efficace même en cas d'augmentation du nombre d'entrées par rapport aux créneaux.
Le pire des cas pour un chaînage séparé est lorsque toutes les clés correspondent au même code de hachage et sont donc insérées dans une seule liste chaînée. Par conséquent, nous devons rechercher toutes les entrées dans la table de hachage et le coût qui sont proportionnels au nombre de clés dans la table.
Palpage linéaire (adressage ouvert / hachage fermé)
Dans la technique d'adressage ouvert ou de détection linéaire, tous les enregistrements d'entrée sont stockés dans la table de hachage elle-même. Lorsque la valeur-clé correspond à un code de hachage et que la position pointée par le code de hachage est inoccupée, la valeur de clé est insérée à cet emplacement.
Si la position est déjà occupée, à l'aide d'une séquence de détection, la valeur de clé est insérée dans la position suivante qui est inoccupée dans la table de hachage.
Pour le sondage linéaire, la fonction de hachage peut changer comme indiqué ci-dessous:
hash = hash% hashTableSize
hash = (hachage + 1)% hashTableSize
hash = (hachage + 2)% hashTableSize
hash = (hachage + 3)% hashTableSize
On voit qu'en cas de palpage linéaire, l'intervalle entre les créneaux ou les sondes successives est constant, c'est-à-dire 1.
Dans le diagramme ci-dessus, nous voyons que dans le 0elocation, nous entrons 10 en utilisant la fonction de hachage «hash = hash% hash_tableSize».
Maintenant, l'élément 70 équivaut également à l'emplacement 0 dans la table de hachage. Mais cet emplacement est déjà occupé. Par conséquent, en utilisant un sondage linéaire, nous trouverons l'emplacement suivant qui est 1. Comme cet emplacement est inoccupé, nous plaçons la clé 70 à cet emplacement comme indiqué à l'aide d'une flèche.
La table de hachage résultante est indiquée ci-dessous.
Le sondage linéaire peut souffrir du problème du «clustering primaire» dans lequel il y a une chance que les cellules continues soient occupées et la probabilité d'insérer un nouvel élément est réduite.
De plus, si deux éléments obtiennent la même valeur à la première fonction de hachage, ces deux éléments suivront la même séquence de sonde.
Sondage quadratique
Le palpage quadratique est le même que le palpage linéaire, la seule différence étant l'intervalle utilisé pour le palpage. Comme son nom l'indique, cette technique utilise une distance non linéaire ou quadratique pour occuper des créneaux lorsqu'une collision se produit au lieu de la distance linéaire.
Dans le sondage quadratique, l'intervalle entre les intervalles est calculé en ajoutant une valeur polynomiale arbitraire à l'index déjà haché. Cette technique réduit le clustering primaire dans une mesure significative mais ne s'améliore pas lors du clustering secondaire.
Double hachage
La technique du double hachage est similaire au sondage linéaire. La seule différence entre le double hachage et le sondage linéaire est que dans la technique du double hachage, l'intervalle utilisé pour le sondage est calculé à l'aide de deux fonctions de hachage. Étant donné que nous appliquons la fonction de hachage à la clé l'une après l'autre, cela élimine le clustering principal ainsi que le clustering secondaire.
Différence entre le chaînage (hachage ouvert) et le palpage linéaire (adressage ouvert)
| Chaînage (hachage ouvert) | Palpage linéaire (adressage ouvert) |
|---|---|
| Les valeurs de clé peuvent être stockées en dehors de la table à l'aide d'une liste chaînée distincte. | Les valeurs de clé doivent être stockées uniquement dans la table. |
| Le nombre d'éléments dans la table de hachage peut dépasser la taille de la table de hachage. | Le nombre d'éléments présents dans la table de hachage ne dépassera pas le nombre d'indices de la table de hachage. |
| La suppression est efficace dans la technique de chaînage. | La suppression peut être fastidieuse. Peut être évité s'il n'est pas nécessaire. |
| Puisqu'une liste chaînée distincte est conservée pour chaque emplacement, l'espace occupé est important. | Étant donné que toutes les entrées sont hébergées dans la même table, l'espace occupé est moindre. |
Implémentation de table de hachage C ++
Nous pouvons implémenter le hachage en utilisant des tableaux ou des listes liées pour programmer les tables de hachage. En C ++, nous avons également une fonctionnalité appelée «table de hachage» qui est une structure similaire à une table de hachage, mais chaque entrée est une paire clé-valeur. En C ++, il s'appelle hash map ou simplement une map. La carte de hachage en C ++ n'est généralement pas ordonnée.
Il existe un en-tête défini dans la bibliothèque de modèles standard (STL) de C ++ qui implémente la fonctionnalité des cartes. Nous avons couvert Cartes STL en détail dans notre tutoriel sur STL.
L'implémentation suivante est pour le hachage en utilisant les listes liées comme structure de données pour la table de hachage. Nous utilisons également le «chaînage» comme technique de résolution de collision dans cette implémentation.
#include #include using namespace std; class Hashing { int hash_bucket; // No. of buckets // Pointer to an array containing buckets list *hashtable; public: Hashing(int V); // Constructor // inserts a key into hash table void insert_key(int val); // deletes a key from hash table void delete_key(int key); // hash function to map values to key int hashFunction(int x) { return (x % hash_bucket); } void displayHash(); }; Hashing::Hashing(int b) { this->hash_bucket = b; hashtable = new list (hash_bucket); } //insert to hash table void Hashing::insert_key(int key) { int index = hashFunction(key); hashtable(index).push_back(key); } void Hashing::delete_key(int key) { // get the hash index for key int index = hashFunction(key); // find the key in (inex)th list list :: iterator i; for (i = hashtable(index).begin(); i != hashtable(index).end(); i++) { if (*i == key) break; } // if key is found in hash table, remove it if (i != hashtable(index).end()) hashtable(index).erase(i); } // display the hash table void Hashing::displayHash() { for (int i = 0; i ' << x; cout << endl; } } // main program int main() { // array that contains keys to be mapped int hash_array() = {11,12,21, 14, 15}; int n = sizeof(hash_array)/sizeof(hash_array(0)); Hashing h(7); // Number of buckets = 7 //insert the keys into the hash table for (int i = 0; i < n; i++) h.insert_key(hash_array(i)); // display the Hash table cout<<'Hash table created:'< Production:
Table de hachage créée:
0 -> 21 -> 14
1 -> 15
deux
3
4 -> 11
5 -> 12
6
Table de hachage après suppression de la clé 12:
0 -> 21 -> 14
1 -> 15
deux
3
4 -> 11
5
6
La sortie montre une table de hachage créée de taille 7. Nous utilisons le chaînage pour résoudre les collisions. Nous affichons la table de hachage après avoir supprimé l'une des clés.
Applications de hachage
# 1) Vérification des mots de passe: La vérification des mots de passe est généralement effectuée à l'aide de fonctions de hachage cryptographique. Lorsque le mot de passe est entré, le système calcule le hachage du mot de passe et est ensuite envoyé au serveur pour vérification. Sur le serveur, les valeurs de hachage des mots de passe d'origine sont stockées.
# 2) Structures de données: Différentes structures de données comme unordered_set et unordered_map en C ++, les dictionnaires en python ou C #, HashSet et hash map en Java utilisent tous une paire clé-valeur dans laquelle les clés sont des valeurs uniques. Les valeurs peuvent être les mêmes pour différentes clés. Le hachage est utilisé pour implémenter ces structures de données.
# 3) Résumé du message: Ceci est encore une autre application qui utilise un hachage cryptographique. Dans les résumés de messages, nous calculons un hachage pour les données envoyées et reçues ou même pour les fichiers et les comparons avec les valeurs stockées pour garantir que les fichiers de données ne sont pas falsifiés. L'algorithme le plus courant ici est «SHA 256».
# 4) Fonctionnement du compilateur: Lorsque le compilateur compile un programme, les mots-clés du langage de programmation sont stockés différemment des autres identifiants. Le compilateur utilise une table de hachage pour stocker ces mots-clés.
# 5) Indexation de la base de données: Les tables de hachage sont utilisées pour l'indexation de la base de données et les structures de données sur disque.
# 6) Tableaux associatifs: Les tableaux associatifs sont des tableaux dont les indices sont d'un type de données autre que des chaînes de type entier ou d'autres types d'objets. Les tables de hachage peuvent être utilisées pour implémenter des tableaux associatifs.
Conclusion
Le hachage est la structure de données la plus largement utilisée car il faut un temps constant O (1) pour les opérations d'insertion, de suppression et de recherche. Le hachage est principalement implémenté à l'aide d'une fonction de hachage qui calcule une valeur de clé unique plus petite pour les entrées de données volumineuses. Nous pouvons implémenter le hachage à l'aide de tableaux et de listes liées.
Chaque fois qu'une ou plusieurs entrées de données correspondent aux mêmes valeurs de clés, il en résulte une collision. Nous avons vu diverses techniques de résolution de collision, y compris le sondage linéaire, le chaînage, etc. Nous avons également vu l'implémentation du hachage en C ++.
Pour conclure, nous pouvons dire que le hachage est de loin la structure de données la plus efficace dans le monde de la programmation.
=> Recherchez la série complète de formations C ++ ici.
lecture recommandée
- Comment rédiger des scénarios de test de logique métier complexes à l'aide de la technique de table de décision
- Table de validation sur le terrain (FVT): une technique de conception de test pour la validation sur le terrain
- Tutoriel QTP n ° 15 - Utilisation des points de contrôle de zone de texte, de tableau et de page dans QTP
- CARTES DANS STL
- Tout sur les routeurs: types de routeurs, table de routage et routage IP
- Top 40 des meilleures questions et réponses d'entretien MySQL (questions 2021)
- Top 90 des questions et réponses d'entretien SQL (DERNIERES)
- Commandes des programmes Unix Utilities: Which, Man, Find Su, Sudo (Part D)