Table des matières
Implémentation d’une table de hachage d’exemple en C/C++
Introduction
Une table de hachage est une structure de données qui associe des clés à des valeurs. Elle est optimisée pour une recherche rapide et efficace, en calculant un index (le hachage) à partir de la clé et en stockant la valeur à cet index. Cela permet d’accéder directement à la valeur sans avoir à parcourir l’ensemble de la table. Les tables de hachage sont essentielles dans diverses applications telles que les bases de données, les compilateurs et les systèmes de cache.
Structure de données
Une table de hachage est généralement implémentée à l’aide d’un tableau de « buckets » ou « emplacements ». Chaque bucket est un conteneur qui stocke les paires clé-valeur. Le hachage de la clé détermine le bucket auquel la paire est attribuée.
Fonction de hachage
La fonction de hachage est une fonction qui convertit une clé en un index dans le tableau des buckets. Une bonne fonction de hachage doit répartir uniformément les clés sur les buckets, minimisant ainsi les collisions (lorsque deux clés ont le même hachage). Les fonctions de hachage courantes incluent la fonction modulo, la multiplication par un nombre premier et le hachage MD5.
Gestion des collisions
Les collisions peuvent se produire lorsque deux clés différentes ont le même hachage. Il existe plusieurs stratégies pour gérer les collisions :
– Chaînage fermé: Stocke les paires en collision dans une liste chaînée à l’intérieur du bucket.
– Chaînage ouvert: Crée une table de hachage secondaire pour les paires en collision.
– adressage ouvert: Sonde les buckets voisins jusqu’à trouver un emplacement vide.
Implémentation en C
c
#include <stdlib.h>
typedef struct bucket {
char *key;
void *value;
struct bucket *next;
} Bucket;
struct hashtable {
Bucket **buckets;
int num_buckets;
};
Hashtable *hashtable_create(int num_buckets) {
Hashtable *table = malloc(sizeof(Hashtable));
table->buckets = malloc(sizeof(Bucket ) num_buckets);
table->num_buckets = num_buckets;
return table;
}
void hashtable_insert(Hashtable table, char *key, void value) {
int index = hash_function(key) % table->num_buckets;
Bucket *new_bucket = malloc(sizeof(Bucket));
new_bucket->key = key;
new_bucket->value = value;
new_bucket->next = table->buckets[index];
table->buckets[index] = new_bucket;
}
void hashtable_get(Hashtable *table, char key) {
int index = hash_function(key) % table->num_buckets;
Bucket *bucket = table->buckets[index];
while (bucket != NULL) {
if (strcmp(bucket->key, key) == 0) {
return bucket->value;
}
bucket = bucket->next;
}
return NULL;
}
void hashtable_delete(Hashtable *table) {
for (int i = 0; i < table->num_buckets; i++) {
Bucket *bucket = table->buckets[i];
while (bucket != NULL) {
Bucket *next = bucket->next;
free(bucket->key);
free(bucket);
bucket = next;
}
}
free(table->buckets);
free(table);
}
Implémentation en C++
cpp
#include <unordered_map>
class HashTable {
private:
std::unordered_map<std::string, int> table;
public:
void insert(std::string key, int value) {
table[key] = value;
}
int get(std::string key) {
if (table.find(key) != table.end()) {
return table[key];
}
return -1;
}
};
Conclusion
Les tables de hachage sont des structures de données puissantes qui permettent une recherche rapide et efficace. En choisissant soigneusement une fonction de hachage et en gérant adéquatement les collisions, vous pouvez optimiser les performances de votre application dans les cas où vous devez rechercher fréquemment des valeurs par clé. L’utilisation de bibliothèques existantes peut également simplifier la mise en œuvre et garantir la fiabilité. En comprenant les concepts de base des tables de hachage, vous pouvez exploiter leur potentiel pour améliorer considérablement vos applications.
FAQ
1. Qu’est-ce qui détermine la performance d’une table de hachage ?
La performance dépend de la fonction de hachage, de la gestion des collisions et de la taille de la table.
2. Quelle est la différence entre les tables de hachage linéaires et non linéaires ?
Les tables de hachage linéaires utilisent une fonction de hachage qui calcule directement l’index du bucket. Les tables de hachage non linéaires appliquent une transformation supplémentaire à la sortie de hachage pour déterminer l’index.
3. Quand utiliser une table de hachage par rapport à un arbre de recherche binaire ?
Les tables de hachage sont préférées pour les recherches rapides et efficaces, tandis que les arbres de recherche binaire sont plus adaptés pour les tris et les traversées.
4. Quelles sont les applications courantes des tables de hachage ?
Les bases de données, les compilateurs et les systèmes de cache utilisent souvent des tables de hachage.
5. Comment choisir une bonne fonction de hachage ?
Une bonne fonction de hachage doit disperser uniformément les clés sur tous les buckets, minimisant ainsi les collisions.
6. Comment gérer les collisions dans une table de hachage ?
Les collisions peuvent être gérées par le chaînage fermé, le chaînage ouvert ou l’adressage ouvert.
7. Quelle est la complexité temporelle de l’insertion et de la recherche dans une table de hachage ?
Avec une bonne fonction de hachage, la complexité temporelle moyenne pour l’insertion et la recherche est O(1), mais elle peut être supérieure en cas de collisions.
8. Quelles sont les limites des tables de hachage ?
Les tables de hachage peuvent devenir inefficaces si la taille de la table est trop petite ou si la fonction de hachage est partiale.