TechCodeview

Introduction au hachage dans la structure des données :

Le hachage est une technique populaire en informatique qui consiste à mapper de grands ensembles de données sur des valeurs de longueur fixe. Il s'agit d'un processus de conversion d'un ensemble de données de taille variable en un ensemble de données de taille fixe. La capacité d’effectuer des opérations de recherche efficaces fait du hachage un concept essentiel dans les structures de données.

Qu’est-ce que le hachage ?

Un algorithme de hachage est utilisé pour convertir une entrée (telle qu'une chaîne ou un entier) en une sortie de taille fixe (appelée code de hachage ou valeur de hachage). Les données sont ensuite stockées et récupérées en utilisant cette valeur de hachage comme index dans un tableau ou une table de hachage. La fonction de hachage doit être déterministe, ce qui garantit qu'elle donnera toujours le même résultat pour une entrée donnée.

Le hachage est couramment utilisé pour créer un identifiant unique pour une donnée, qui peut être utilisé pour rechercher rapidement ces données dans un grand ensemble de données. Par exemple, un navigateur Web peut utiliser le hachage pour stocker les mots de passe de sites Web en toute sécurité. Lorsqu'un utilisateur saisit son mot de passe, le navigateur le convertit en valeur de hachage et le compare à la valeur de hachage stockée pour authentifier l'utilisateur.

Qu'est-ce qu'une clé de hachage ?

Dans le contexte du hachage, une clé de hachage (également appelée valeur de hachage ou code de hachage) est une représentation numérique ou alphanumérique de taille fixe générée par un algorithme de hachage. Il est dérivé des données d'entrée, telles qu'une chaîne de texte ou un fichier, via un processus appelé hachage.

Le hachage implique l'application d'une fonction mathématique spécifique aux données d'entrée, qui produit une clé de hachage unique, généralement de longueur fixe, quelle que soit la taille de l'entrée. La clé de hachage résultante est essentiellement une empreinte numérique des données originales.

La clé de hachage sert à plusieurs fins. Il est couramment utilisé pour les contrôles d’intégrité des données, car même un petit changement dans les données d’entrée produira une clé de hachage sensiblement différente. Les clés de hachage sont également utilisées pour une récupération et un stockage efficaces des données dans des tables de hachage ou des structures de données, car elles permettent des opérations de recherche et de comparaison rapides.

monflixr

Comment fonctionne le hachage ?

Le processus de hachage peut être décomposé en trois étapes :

• Entrée : les données à hacher sont entrées dans l'algorithme de hachage.
• Fonction de hachage : l'algorithme de hachage prend les données d'entrée et applique une fonction mathématique pour générer une valeur de hachage de taille fixe. La fonction de hachage doit être conçue de manière à ce que différentes valeurs d'entrée produisent différentes valeurs de hachage et que de petits changements dans l'entrée produisent de grands changements dans la sortie.
• Sortie : la valeur de hachage est renvoyée, qui est utilisée comme index pour stocker ou récupérer des données dans une structure de données.

Algorithmes de hachage :

Il existe de nombreux algorithmes de hachage, chacun présentant des avantages et des inconvénients distincts. Les algorithmes les plus populaires sont les suivants :

• MD5 : un algorithme de hachage largement utilisé qui produit une valeur de hachage de 128 bits.
• SHA-1 : un algorithme de hachage populaire qui produit une valeur de hachage de 160 bits.
• SHA-256 : un algorithme de hachage plus sécurisé qui produit une valeur de hachage de 256 bits.

Fonction de hachage :

Fonction de hachage : une fonction de hachage est un type d'opération mathématique qui prend une entrée (ou une clé) et génère un résultat de taille fixe appelé code de hachage ou valeur de hachage. La fonction de hachage doit toujours produire le même code de hachage pour la même entrée afin d'être déterministe. De plus, la fonction de hachage doit produire un code de hachage unique pour chaque entrée, appelé propriété de hachage.

Il existe différents types de fonctions de hachage, notamment :

Méthode de division :

Cette méthode consiste à diviser la clé par la taille de la table et à prendre le reste comme valeur de hachage. Par exemple, si la taille de la table est de 10 et la clé de 23, la valeur de hachage serait de 3 (23 % 10 = 3).

Méthode de multiplication :

Cette méthode consiste à multiplier la clé par une constante et à prendre la partie fractionnaire du produit comme valeur de hachage. Par exemple, si la clé est 23 et la constante est 0,618, la valeur de hachage serait 2 (floor(10*(0.61823 - floor(0.61823))) = floor(2.236) = 2).

Hachage universel :

Cette méthode consiste à utiliser une fonction de hachage aléatoire issue d’une famille de fonctions de hachage. Cela garantit que la fonction de hachage n’est pas orientée vers une entrée particulière et résiste aux attaques.

Résolution des collisions

L’un des principaux défis du hachage est la gestion des collisions, qui se produisent lorsque deux ou plusieurs valeurs d’entrée produisent la même valeur de hachage. Il existe diverses techniques utilisées pour résoudre les collisions, notamment :

• Chaînage : dans cette technique, chaque emplacement de table de hachage contient une liste chaînée de toutes les valeurs qui ont la même valeur de hachage. Cette technique est simple et facile à mettre en œuvre, mais elle peut conduire à de mauvaises performances lorsque les listes chaînées deviennent trop longues.
• Adressage ouvert : Dans cette technique, lorsqu'une collision se produit, l'algorithme recherche un emplacement vide dans la table de hachage en sondant les emplacements successifs jusqu'à ce qu'un emplacement vide soit trouvé. Cette technique peut être plus efficace que le chaînage lorsque le facteur de charge est faible, mais elle peut conduire à un clustering et à de mauvaises performances lorsque le facteur de charge est élevé.
• Double hachage : il s'agit d'une variante de l'adressage ouvert qui utilise une deuxième fonction de hachage pour déterminer le prochain emplacement à sonder lorsqu'une collision se produit. Cette technique peut aider à réduire le clustering et à améliorer les performances.

Exemple de résolution de collision

Continuons avec notre exemple de table de hachage d'une taille de 5. Nous souhaitons stocker les paires clé-valeur 'John : 123456' et 'Mary : 987654' dans la table de hachage. Les deux clés produisent le même code de hachage de 4, donc une collision se produit.

Nous pouvons utiliser le chaînage pour résoudre la collision. Nous créons une liste chaînée à l'index 4 et ajoutons les paires clé-valeur à la liste. La table de hachage ressemble maintenant à ceci :

0 :

1:

2 :

3 :

4 : Jean : 123456 -> Marie : 987654

5 :

Table de hachage :

Une table de hachage est une structure de données qui stocke des données dans un tableau. En règle générale, une taille de tableau sélectionnée est supérieure au nombre d'éléments pouvant tenir dans la table de hachage. Une clé est mappée à un index du tableau à l'aide de la fonction de hachage.

La fonction de hachage est utilisée pour localiser l'index où un élément doit être inséré dans la table de hachage afin d'ajouter un nouvel élément. L'élément est ajouté à cet index s'il n'y a pas de collision. En cas de collision, la méthode de résolution de collision est utilisée pour trouver le prochain emplacement disponible dans le tableau.

La fonction de hachage est utilisée pour localiser l'index dans lequel l'élément est stocké afin de le récupérer de la table de hachage. Si l'élément n'est pas trouvé à cet index, la méthode de résolution de collision est utilisée pour rechercher l'élément dans la liste chaînée (si le chaînage est utilisé) ou dans le prochain emplacement disponible (si l'adressage ouvert est utilisé).

Opérations sur les tables de hachage

Plusieurs opérations peuvent être effectuées sur une table de hachage, notamment :

• Insertion : insertion d'une nouvelle paire clé-valeur dans la table de hachage.
• Suppression : suppression d'une paire clé-valeur de la table de hachage.
• Rechercher : recherche d'une paire clé-valeur dans la table de hachage.

Création d'une table de hachage :

Le hachage est fréquemment utilisé pour créer des tables de hachage, qui sont des structures de données permettant une insertion, une suppression et une récupération rapides des données. Une ou plusieurs paires clé-valeur peuvent être stockées dans chacun des tableaux de compartiments qui composent une table de hachage.

Pour créer une table de hachage, nous devons d'abord définir une fonction de hachage qui mappe chaque clé à un index unique du tableau. Une fonction de hachage simple pourrait consister à prendre la somme des valeurs ASCII des caractères de la clé et à utiliser le reste lorsqu'il est divisé par la taille du tableau. Cependant, cette fonction de hachage est inefficace et peut conduire à des collisions (deux clés mappées sur le même index).

Pour éviter les collisions, nous pouvons utiliser des fonctions de hachage plus avancées qui produisent une répartition plus uniforme des valeurs de hachage dans le tableau. Un algorithme populaire est la fonction de hachage djb2, qui utilise des opérations au niveau du bit pour générer une valeur de hachage :

 unsigned long hash(char* str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = ((hash << 5) + hash) + c; } return hash; } 

Cette fonction de hachage prend une chaîne en entrée et renvoie une valeur de hachage entière longue non signée. La fonction initialise une valeur de hachage de 5 381, puis parcourt chaque caractère de la chaîne, en utilisant des opérations au niveau du bit pour générer une nouvelle valeur de hachage. La valeur de hachage finale est renvoyée.

Tables de hachage en C++

En C++, la bibliothèque standard fournit une classe conteneur de table de hachage appelée unordered_map. Le conteneur unordered_map est implémenté à l'aide d'une table de hachage et fournit un accès rapide aux paires clé-valeur. Le conteneur unordered_map utilise une fonction de hachage pour calculer le code de hachage des clés, puis utilise l'adressage ouvert pour résoudre les collisions.

Pour utiliser le conteneur unordered_map en C++, vous devez inclure le fichier d'en-tête. Voici un exemple de création d'un conteneur unordered_map en C++ :

 #include #include int main() { // create an unordered_map container std::unordered_map my_map; // insert some key-value pairs into the map my_map['apple'] = 10; my_map['banana'] = 20; my_map['orange'] = 30; // print the value associated with the 'banana' key std::cout << my_map['banana'] << std::endl; return 0; } 

Explication:

• Ce programme démontre l'utilisation du conteneur unordered_map en C++, qui est implémenté à l'aide d'une table de hachage et fournit un accès rapide aux paires clé-valeur.
• Tout d'abord, le programme comprend les fichiers d'en-tête nécessaires : et.
• Ensuite, le programme crée un conteneur unordered_map vide appelé my_map, qui contient des clés de chaîne et des valeurs entières. Cela se fait en utilisant la syntaxe std::unordered_map my_map;
• Ensuite, le programme insère trois paires clé-valeur dans le conteneur my_map à l'aide de l'opérateur [] : « pomme » avec une valeur de 10, « banane » avec une valeur de 20 et « orange » avec une valeur de 30.
• Cela se fait en utilisant la syntaxe my_map['apple'] = 10;, my_map['banana'] = 20; et my_map['orange'] = 30; respectivement.
• Enfin, le programme imprime la valeur associée à la clé 'banane' à l'aide de l'opérateur [] et de l'objet std::cout.

Sortie du programme :

Insertion de données dans une table de hachage

Pour insérer une paire clé-valeur dans une table de hachage, nous devons d'abord créer un index dans le tableau pour stocker la paire clé-valeur. Si une autre clé correspond au même index, nous avons une collision et devons la gérer de manière appropriée. Une méthode courante consiste à utiliser le chaînage, où chaque compartiment du tableau contient une liste chaînée de paires clé-valeur ayant la même valeur de hachage.

Voici un exemple de la façon d'insérer une paire clé-valeur dans une table de hachage à l'aide du chaînage :

 typedef struct node { char* key; int value; struct node* next; } node; node* hash_table[100]; void insert(char* key, int value) { unsigned long hash_value = hash(key) % 100; node* new_node = (node*) malloc(sizeof(node)); new_node->key = key; new_node->value = value; new_node->next = NULL; if (hash_table[hash_value] == NULL) { hash_table[hash_value] = new_node; } else { node* curr_node = hash_table[hash_value]; while (curr_node->next != NULL) { curr_node = curr_node->next; } curr_node->next = new_node; } } 

Explication:

• Tout d’abord, une structure appelée node est définie, qui représente un seul nœud dans la table de hachage.
• Chaque nœud comporte trois membres : une clé char* pour stocker la clé, une valeur int pour stocker la valeur associée et un pointeur vers un autre nœud appelé next pour gérer les collisions dans la table de hachage à l'aide d'une liste chaînée.
• Un tableau de pointeurs de nœuds appelé hash_table est déclaré avec une taille de 100. Ce tableau servira à stocker les éléments de la table de hachage.
• La fonction insert prend une clé char* et une valeur int comme paramètres.
• Cela commence par calculer la valeur de hachage pour la clé donnée à l'aide de la fonction de hachage, qui est supposée être définie ailleurs dans le programme.
• La valeur de hachage est ensuite réduite pour s'adapter à la taille du tableau hash_table à l'aide de l'opérateur de module % 100.
• Un nouveau nœud est créé à l'aide d'une allocation de mémoire dynamique (malloc(sizeof(node))) et ses membres (clé, valeur et suivant) se voient attribuer respectivement la clé, la valeur et NULL fournies.
• Si l'emplacement correspondant dans le tableau hash_table est vide (NULL), indiquant qu'aucune collision ne s'est produite, le nouveau nœud est directement affecté à cet emplacement (hash_table[hash_value] = new_node).

Cependant, s'il existe déjà un nœud présent à cet index dans le tableau hash_table, la fonction doit gérer la collision. Il parcourt la liste chaînée à partir du nœud actuel (hash_table[hash_value]) et se déplace vers le nœud suivant jusqu'à ce qu'il atteigne la fin (curr_node->next != NULL). Une fois la fin de la liste atteinte, le nouveau nœud est ajouté comme nœud suivant (curr_node->next = new_node).

Implémentation du Hachage en C++ :

Voyons une implémentation du hachage en C++ utilisant l'adressage ouvert et le sondage linéaire pour la résolution des collisions. Nous allons implémenter une table de hachage qui stocke les entiers.

 #include using namespace std; const int SIZE = 10; class HashTable { private: int arr[SIZE]; public: HashTable() { for (int i = 0; i <size; i++) { arr[i]="-1;" } int hashfunction(int key) return key % size; void insert(int index="hashFunction(key);" i="0;" while (arr[(index + i) size] !="-1" && arr[(index i++; if cout << 'element already exists in the hash table' endl; else remove(int deleted from return; not found display() for (int < (arr[i]="=" -1 || -2) continue; 'index ' ': }; main() hashtable ht; ht.insert(5); ht.insert(15); ht.insert(25); ht.insert(35); ht.insert(45); ht.display(); ht.remove(15); ht.remove(10); ht.insert(55); 0; pre> <p> <strong>Explanation:</strong> </p> <ul> <li>This program implements a hash table data structure using linear probing to handle collisions.</li> <li>A hash table is a data structure that stores data in key-value pairs, where the keys are hashed using a hash function to generate an index in an array. This allows for constant-time average-case complexity for inserting, searching, and deleting elements from the hash table.</li> <li>The HashTable class has a private integer array arr of size SIZE, which is initialized to -1 in the constructor. The hash function method takes an integer key and returns the hash value of the key, which is simply the remainder of the key when divided by SIZE.</li> <li>The insert method takes an integer key and uses the hash function to get the index where the key should be inserted.</li> <li>If the index is already occupied by another key, linear probing is used to find the next available index in the array. Linear probing checks the next index in the array until it finds an empty slot or the key itself.</li> <li>If the key is already in the hash table, the method displays a message saying that the element already exists. Otherwise, it inserts the key at the calculated index.</li> <li>The remove method takes an integer key and uses the hash function to get the index where the key is located.</li> <li>If the key is not in the calculated index, linear probing is used to search for the key in the next indices in the array. Once the key is found, it is deleted by setting its value to -2.</li> <li>If the key is not found in the hash table, the method displays a message saying that the element is not found.</li> <li>The display method simply iterates through the array and prints out all non-empty key-value pairs.</li> <li>In the main function, an instance of the HashTable class is created, and several integers are inserted into the hash table using the insert method.</li> <li>Then, the display method is called to show the contents of the hash table. The remove method is called twice, first to remove an element that exists in the hash table and then to remove an element that does not exist.</li> <li>The display method is called after each remove method call to show the updated contents of the hash table.</li> <li>Finally, another integer is inserted into the hash table, and the display method is called again to show the final contents of the hash table.</li> </ul> <p> <strong>Program Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/hashing-data-structure-3.webp" alt="Hashing in Data Structure"> <h2>Applications of Hashing</h2> <p>Hashing has many applications in computer science, including:</p> <ul> <li>Databases: Hashing is used to index and search large databases efficiently.</li> <li>Cryptography: Hash functions are used to generate message digests, which are used to verify the integrity of data and protect against tampering.</li> <li>Caching: Hash tables are used in caching systems to store frequently accessed data and improve performance.</li> <li>Spell checking: Hashing is used in spell checkers to quickly search for words in a dictionary.</li> <li>Network routing: Hashing is used in load balancing and routing algorithms to distribute network traffic across multiple servers.</li> </ul> <h2>Advantages of Hashing:</h2> <ul> <li>Fast Access: Hashing provides constant time access to data, making it faster than other data structures like linked lists and arrays.</li> <li>Efficient Search: Hashing allows for quick search operations, making it an ideal data structure for applications that require frequent search operations.</li> <li>Space-Efficient: Hashing can be more space-efficient than other data structures, as it only requires a fixed amount of memory to store the hash table.</li> </ul> <h2>Limitations of Hashing:</h2> <ul> <li>Hash Collisions: Hashing can produce the same hash value for different keys, leading to hash collisions. To handle collisions, we need to use collision resolution techniques like chaining or open addressing.</li> <li>Hash Function Quality: The quality of the hash function determines the efficiency of the hashing algorithm. A poor-quality hash function can lead to more collisions, reducing the performance of the hashing algorithm.</li> </ul> <h2>Conclusion:</h2> <p>In conclusion, hashing is a widely used technique in a data structure that provides efficient access to data. It involves mapping a large amount of data to a smaller hash table using a hash function, which reduces the amount of time needed to search for specific data elements. The hash function ensures that data is stored in a unique location within the hash table and allows for easy retrieval of data when needed.</p> <p>Hashing has several advantages over other data structure techniques, such as faster retrieval times, efficient use of memory, and reduced collisions due to the use of a good hash function. However, it also has some limitations, including the possibility of hash collisions and the need for a good hash function that can distribute data evenly across the hash table.</p> <p>Overall, hashing is a powerful technique that is used in many applications, including database indexing, spell-checking, and password storage. By using a good hash function and implementing appropriate collision resolution techniques, developers can optimize the performance of their applications and provide users with a seamless experience.</p> <hr></size;>