Structure de données - Table de hachage
Une table de hachage est une structure de données qui associe des clés à des positions spécifiques dans un tableau via une fonction de hachage, permettant ainsi d'atteindre une complexité temporelle moyenne de O(1) pour les opérations de recherche, d'insertion et de suppression.
Fonction de hachage et collision de hachage
Case rouge = collision ! key=1 et key=11 correspondent à la même position
Fonction de hachageL'objectif de conception de la fonction de hachage est de convertir une entrée arbitraire (clés) en un entier (indice de tableau) dans une plage fixe.
Une bonne fonction de hachage doit avoir un calcul rapide et des résultats uniformément distribués.
Cependant, comme la capacité d'une table de hachage est toujours limitée,les collisions de hachage—deux clés différentes mappées à la même position—sont un phénomène inévitable.
Méthodes de résolution des collisions
Chaînage
Chaque emplacement stocke une liste chaînée ; les clés en collision sont ajoutées
Avantages : implémentation simple, suppression facile
Inconvénients : surcoût des pointeurs, défavorable au cache
Le facteur de charge peut dépasser 1.0
Adressage ouvert
En cas de collision, sonder l'emplacement vide suivant
Avantages : pas de pointeurs, adapté au cache
Inconvénients : la suppression nécessite un marquage différé
Le facteur de charge doit être ≤ 0.7
| Méthode | Principe | Avantages | Inconvénients |
|---|---|---|---|
| Chaînage | Chaque emplacement stocke une liste chaînée ; les clés en collision sont ajoutées à la liste chaînée | Mise en œuvre simple, suppression facile, le facteur de charge peut être supérieur à 1 | Surcoût supplémentaire dû aux pointeurs, non adapté au cache |
| Adressage ouvert | En cas de collision, trouver le prochain emplacement vide du tableau selon les règles de sondage | Aucun pointeur nécessaire, adapté au cache | Suppression complexe (nécessite une suppression différée), le facteur de charge doit être contrôlé |
En adressage ouvert, lors de la suppression d'un élément, vous ne pouvez pas simplement vider l'emplacement, sinon cela brisera la chaîne de recherche pour les éléments suivants. L'approche habituelle consiste à utiliser « suppression différée » — marquer la position comme « supprimée » plutôt que comme « vide ».
Implémentation par chaînage
Exemple
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10 /* capacité de la table de hachage */
/* nœud de table de hachage */
struct HashNode {
int key;
int value;
struct HashNode* next; /* pointeur vers le nœud suivant dans le même emplacement */
};
/* fonction de hachage : méthode modulo simple */
int hashFunc(int key) {
return key % TABLE_SIZE;
}
/* Insérer une paire clé-valeur (chaînage)
Complexité temporelle : O(1) en moyenne, O(n) dans le pire des cas (toutes les clés correspondent au même emplacement) */
void insert(struct HashNode* table[], int key, int value) {
int index = hashFunc(key);
struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
newNode->key = key;
newNode->value = value;
newNode->next = table[index]; /* Insertion en tête */
table[index] = newNode;
}
/* Recherche : obtenir la valeur par clé
Calculez d'abord la valeur de hachage pour localiser l'emplacement, puis parcourez la liste chaînée pour trouver la clé correspondante */
int search(struct HashNode* table[], int key) {
int index = hashFunc(key);
struct HashNode* cur = table[index];
while (cur != NULL) {
if (cur->key == key) {
return cur->value; /* Trouvé */
}
cur = cur->next;
}
return -1; /* Non trouvé */
}
int main() {
struct HashNode* table[TABLE_SIZE] = {NULL}; /* Initialiser tous les emplacements à vide */
insert(table, 1, 100); /* clé=1, valeur=100, index=1 */
insert(table, 2, 200); /* clé=2, valeur=200, index=2 */
insert(table, 11, 300); /* clé=11, valeur=300, index=1 — entre en collision avec clé=1 ! */
printf("key=1 → %d\n", search(table, 1)); /* Sortie : 100 */
printf("key=2 → %d\n", search(table, 2)); /* Sortie : 200 */
printf("key=11 → %d\n", search(table, 11)); /* Sortie : 300 (le chaînage a correctement géré la collision) */
printf("key=99 → %d\n", search(table, 99)); /* Sortie : -1 (non trouvé) */
return 0;
}
Scénarios d'application
| Scénario | Description |
|---|---|
| Dictionnaire/Map | Stockage et recherche rapide de paires clé-valeur, par ex. le dict de Python, le HashMap de Java |
| Systèmes de cache | Implémentation sous-jacente de systèmes de cache tels que LRU Cache |
| Indexation de base de données | L'indexation par hachage permet une recherche en O(1) pour les requêtes d'égalité |
| Table des symboles du compilateur | Enregistre la correspondance entre les noms de variables, les noms de fonctions et leurs types |