Comment implémenter une table de hachage en C : guide pratique avec exemples

Dans la programmation en C, les tables de hachage jouent un rôle crucial dans l’indexation rapide et efficace des données. Elles permettent de stocker et de récupérer des informations en temps quasi constant, ce qui en fait un outil indispensable dans de nombreuses applications, telles que les bases de données, les compilateurs et les systèmes de fichiers.

Le principe d’une table de hachage repose sur l’utilisation d’une fonction de hachage, qui transforme une clé en un indice dans un tableau. Cette approche garantit une recherche rapide, même lorsque le volume de données est important.

Cependant, l’implémentation d’une table de hachage en C nécessite une compréhension approfondie des structures de données et des techniques pour gérer des problèmes tels que les collisions. Dans cet article, nous explorerons les bases des tables de hachage, leur fonctionnement, et nous fournirons un guide pratique pour les implémenter en C, avec des exemples concrets.

Sommaire

Qu’est-ce qu’une table de hachage ?

Une table de hachage est une structure de données qui associe des clés uniques à des valeurs, permettant ainsi un accès rapide aux données grâce à une fonction de hachage. Cette fonction transforme chaque clé en un indice dans un tableau, où la valeur correspondante est stockée.

Pourquoi utiliser une table de hachage ?

Les tables de hachage sont largement utilisées pour leur capacité à effectuer des recherches, des insertions et des suppressions en temps quasi constant. Cela en fait un choix idéal pour gérer des ensembles de données volumineux dans des domaines où la performance est critique, comme :

Les dictionnaires, pour associer des mots à leurs définitions.
Les caches, pour accéder rapidement à des résultats pré-calculés.
Les systèmes de fichiers, pour localiser des fichiers à partir de leur nom.

Avantages des tables de hachage

Rapidité : Les opérations sur les tables de hachage s’exécutent souvent en temps O(1), ce qui est très efficace.
Flexibilité : Elles peuvent gérer différents types de clés, qu’il s’agisse de nombres, de chaînes ou d’autres types de données.
Simplicité d’utilisation : Une fois implémentée, leur manipulation est simple et directe.

Inconvénients potentiels

Collisions : Lorsque deux clés différentes produisent le même indice, des mécanismes de gestion des collisions sont nécessaires, ce qui peut ralentir l’accès.
Dépendance à la fonction de hachage : Une mauvaise fonction de hachage peut entraîner une répartition déséquilibrée des clés et nuire aux performances.

En résumé, une table de hachage est une solution élégante pour gérer des données avec un accès rapide, à condition de maîtriser ses principes et ses limites.

Principe de fonctionnement d’une table de hachage

Une table de hachage repose sur le concept clé d’une fonction de hachage qui mappe des clés uniques à des indices dans un tableau. Voici une explication détaillée de son fonctionnement :

Étapes fondamentales du fonctionnement

1. Fonction de hachage

La fonction de hachage prend une clé en entrée (par exemple, un entier ou une chaîne de caractères) et génère un indice, qui est utilisé pour localiser la valeur correspondante dans le tableau. Une bonne fonction de hachage doit être :

Rapide à exécuter.
Uniforme, pour répartir les clés de manière équilibrée.
Déterministe, afin que la même clé produise toujours le même indice.

Exemple en pseudo-code :

int hash_function(int key, int table_size) {
    return key % table_size; // Utilisation du modulo
}

2. Stockage des données

Les valeurs sont stockées dans un tableau à l’indice généré par la fonction de hachage. Par exemple, si une clé produit l’indice 3, la valeur associée est placée à cet emplacement dans le tableau.

3. Recherche d’une valeur

Pour récupérer une valeur, la clé est passée à la fonction de hachage, qui renvoie l’indice où la valeur est située. Si les données sont correctement hachées, cette opération s’effectue rapidement.

Gestion des collisions

Une collision se produit lorsque deux clés différentes génèrent le même indice. Les techniques suivantes permettent de gérer ce problème :

1. Chaînage (chaining)

Les collisions sont résolues en stockant plusieurs éléments dans une liste liée à chaque indice. Si une collision se produit, la nouvelle valeur est ajoutée à la liste.

Exemple :

Indice	Liste associée
0	Valeur1 → Valeur2
1	Valeur3

2. Probing linéaire (linear probing)

Si une collision se produit, l’algorithme recherche la prochaine case vide dans le tableau et y stocke la valeur.

3. Double hachage (double hashing)

Une seconde fonction de hachage est utilisée pour déterminer un pas de recherche, ce qui réduit les risques de collisions.

Complexité des opérations

Insertion : O(1) en moyenne, O(n) dans le pire des cas (si toutes les clés se hachent au même indice).
Recherche : O(1) en moyenne, O(n) dans le pire des cas avec des collisions mal gérées.

En comprenant et en appliquant ces principes, il est possible de concevoir des tables de hachage performantes adaptées à de nombreux cas d’utilisation.

Structure de données en C pour une table de hachage

Dans le langage C, une table de hachage peut être implémentée à l’aide de structures adaptées, comme des tableaux et des listes chaînées. Cette section détaille les éléments nécessaires pour construire une table de hachage efficace.

Définir les structures de base

Pour stocker les clés et les valeurs, ainsi que pour gérer les collisions, il est courant d’utiliser des listes chaînées. Voici un exemple de définition de ces structures en C :

#include <stdlib.h>
#include <string.h>

// Structure pour un nœud d'une liste chaînée
typedef struct HashNode {
    char *key;               // Clé
    char *value;             // Valeur associée
    struct HashNode *next;   // Pointeur vers le nœud suivant (pour le chaînage)
} HashNode;

// Structure pour la table de hachage
typedef struct HashTable {
    HashNode **buckets;      // Tableau de pointeurs vers les nœuds
    int size;                // Taille du tableau (nombre de "seaux")
} HashTable;

Initialiser une table de hachage

Avant d’utiliser une table de hachage, il faut allouer de la mémoire et initialiser ses seaux à NULL. Voici un exemple d’implémentation :

HashTable *create_hash_table(int size) {
    HashTable *table = (HashTable *)malloc(sizeof(HashTable));
    if (!table) return NULL;

    table->size = size;
    table->buckets = (HashNode **)malloc(size * sizeof(HashNode *));
    if (!table->buckets) {
        free(table);
        return NULL;
    }

    for (int i = 0; i < size; i++) {
        table->buckets[i] = NULL;
    }

    return table;
}

Fonction de hachage

Une fonction de hachage simple et efficace peut être basée sur la somme des valeurs ASCII des caractères de la clé, combinée avec l’opération modulo pour éviter les dépassements :

int hash_function(const char *key, int table_size) {
    int hash = 0;
    while (*key) {
        hash += *key++;
    }
    return hash % table_size;
}

Insérer une paire clé-valeur

Lors de l’insertion, la clé est hachée pour déterminer l’indice dans le tableau. Ensuite, un nouveau nœud est ajouté à la liste chaînée si une collision survient :

void insert(HashTable *table, const char *key, const char *value) {
    int index = hash_function(key, table->size);

    // Créer un nouveau nœud
    HashNode *new_node = (HashNode *)malloc(sizeof(HashNode));
    new_node->key = strdup(key);
    new_node->value = strdup(value);
    new_node->next = table->buckets[index];

    // Insérer au début de la liste chaînée
    table->buckets[index] = new_node;
}

Rechercher une valeur

Pour rechercher une valeur, on hache la clé, puis on parcourt la liste chaînée à cet indice pour trouver la clé correspondante :

char *search(HashTable *table, const char *key) {
    int index = hash_function(key, table->size);
    HashNode *current = table->buckets[index];

    while (current) {
        if (strcmp(current->key, key) == 0) {
            return current->value;
        }
        current = current->next;
    }

    return NULL; // Clé introuvable
}

Supprimer une clé

La suppression implique de rechercher la clé, de la supprimer de la liste chaînée et de libérer la mémoire :

void delete_key(HashTable *table, const char *key) {
    int index = hash_function(key, table->size);
    HashNode *current = table->buckets[index];
    HashNode *prev = NULL;

    while (current) {
        if (strcmp(current->key, key) == 0) {
            if (prev) {
                prev->next = current->next;
            } else {
                table->buckets[index] = current->next;
            }
            free(current->key);
            free(current->value);
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    }
}

Conclusion

Ces structures de données et fonctions de base forment le fondement d’une implémentation de table de hachage en C. Une fois maîtrisées, elles permettent de gérer efficacement les données tout en assurant des performances élevées.

Implémentation étape par étape d’une table de hachage en C

Voici une approche détaillée pour coder une table de hachage complète en C, incluant toutes les fonctionnalités principales : insertion, recherche, et suppression. Chaque étape est accompagnée d’exemples concrets pour illustrer le processus.

1. Initialisation de la table de hachage

La première étape consiste à définir et initialiser la table de hachage, comme présenté précédemment.

HashTable *create_hash_table(int size) {
    HashTable *table = (HashTable *)malloc(sizeof(HashTable));
    if (!table) return NULL;

    table->size = size;
    table->buckets = (HashNode **)malloc(size * sizeof(HashNode *));
    if (!table->buckets) {
        free(table);
        return NULL;
    }

    for (int i = 0; i < size; i++) {
        table->buckets[i] = NULL;
    }

    return table;
}

2. Fonction de hachage

Une fonction de hachage efficace est cruciale pour garantir une répartition uniforme des clés.

int hash_function(const char *key, int table_size) {
    int hash = 0;
    while (*key) {
        hash = (hash + *key) % table_size; // Somme ASCII mod table_size
        key++;
    }
    return hash;
}

3. Insertion dans la table de hachage

Lors de l’insertion d’une clé-valeur, la clé est hachée pour déterminer le seau, et le nouvel élément est inséré.

void insert(HashTable *table, const char *key, const char *value) {
    int index = hash_function(key, table->size);

    // Créer un nouveau nœud
    HashNode *new_node = (HashNode *)malloc(sizeof(HashNode));
    new_node->key = strdup(key);
    new_node->value = strdup(value);
    new_node->next = table->buckets[index];

    // Insérer au début de la liste chaînée
    table->buckets[index] = new_node;
}

Exemple d’utilisation :

HashTable *table = create_hash_table(10);
insert(table, "name", "Alice");
insert(table, "age", "25");

4. Recherche dans la table de hachage

Pour rechercher une valeur, la clé est utilisée pour parcourir la liste chaînée à l’indice haché.

char *search(HashTable *table, const char *key) {
    int index = hash_function(key, table->size);
    HashNode *current = table->buckets[index];

    while (current) {
        if (strcmp(current->key, key) == 0) {
            return current->value;
        }
        current = current->next;
    }

    return NULL; // Clé introuvable
}

Exemple d’utilisation :

char *value = search(table, "name");
if (value) {
    printf("La valeur associée à 'name' est : %s\n", value);
} else {
    printf("Clé non trouvée.\n");
}

5. Suppression d’une clé

La suppression nécessite de parcourir la liste chaînée pour détacher le nœud correspondant et libérer la mémoire.

void delete_key(HashTable *table, const char *key) {
    int index = hash_function(key, table->size);
    HashNode *current = table->buckets[index];
    HashNode *prev = NULL;

    while (current) {
        if (strcmp(current->key, key) == 0) {
            if (prev) {
                prev->next = current->next;
            } else {
                table->buckets[index] = current->next;
            }
            free(current->key);
            free(current->value);
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    }
}

Exemple d’utilisation :

delete_key(table, "age");

6. Nettoyage de la table de hachage

Pour éviter les fuites de mémoire, il est important de libérer tous les nœuds et la mémoire associée à la table :

void free_hash_table(HashTable *table) {
    for (int i = 0; i < table->size; i++) {
        HashNode *current = table->buckets[i];
        while (current) {
            HashNode *temp = current;
            current = current->next;
            free(temp->key);
            free(temp->value);
            free(temp);
        }
    }
    free(table->buckets);
    free(table);
}

Exemple complet

Voici un programme complet pour insérer, rechercher, supprimer et nettoyer une table de hachage :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Définitions et fonctions comme décrit précédemment...

int main() {
    HashTable *table = create_hash_table(10);

    insert(table, "name", "Alice");
    insert(table, "age", "25");
    insert(table, "city", "Paris");

    printf("Recherche de 'name' : %s\n", search(table, "name"));
    printf("Recherche de 'age' : %s\n", search(table, "age"));

    delete_key(table, "age");
    printf("Recherche après suppression de 'age' : %s\n", search(table, "age"));

    free_hash_table(table);

    return 0;
}

Conclusion

Ce guide fournit une implémentation pratique et robuste d’une table de hachage en C. Avec cette base, vous pouvez personnaliser et étendre les fonctionnalités pour répondre à des besoins spécifiques, comme le traitement de grands ensembles de données ou l’optimisation des performances.

Cas pratiques et optimisations

Les tables de hachage sont largement utilisées dans divers domaines où la rapidité d’accès aux données est essentielle. Cette section présente des cas d’utilisation réels, ainsi que des stratégies pour optimiser leurs performances.

1. Cas pratiques d’utilisation

1.1 Gestion des dictionnaires

Un dictionnaire stocke des associations clé-valeur, comme des mots et leurs définitions. Une table de hachage permet un accès rapide aux définitions grâce à leurs clés uniques (les mots).
Exemple :

Application : Vérificateur orthographique.
Fonctionnement : Chaque mot du dictionnaire est une clé, et sa définition ou son orthographe correcte est la valeur.

1.2 Mise en cache

Les systèmes de cache utilisent des tables de hachage pour stocker des données fréquemment consultées, minimisant ainsi les temps d’accès aux données d’origine.
Exemple :

Application : Mémorisation des résultats d’une API.
Fonctionnement : Une clé (requête) correspond au résultat (valeur). Si la requête est répétée, le système retourne rapidement la valeur mise en cache.

1.3 Gestion des utilisateurs

Les tables de hachage sont utilisées pour associer des identifiants d’utilisateur uniques (clés) aux données utilisateur correspondantes.
Exemple :

Application : Stockage des sessions utilisateur dans une application web.
Fonctionnement : La clé est un identifiant unique de session, et la valeur contient les données de session.

2. Techniques d’optimisation

2.1 Choix d’une bonne fonction de hachage

Une fonction de hachage efficace est essentielle pour éviter les collisions et améliorer les performances.
Caractéristiques d’une bonne fonction :

Distribution uniforme des clés.
Rapidité d’exécution.
Exemple : Utilisation de la méthode de hachage de Jenkins ou de MurmurHash pour des clés plus complexes.

2.2 Gestion efficace des collisions

Chaînage amélioré : Utiliser des arbres rouges-noirs au lieu de listes chaînées pour réduire le temps d’accès dans les cas extrêmes.
Probing linéaire : Combiner probing linéaire avec un taux de remplissage (load factor) adapté pour éviter les collisions fréquentes.

2.3 Ajustement de la taille de la table

La taille de la table de hachage doit être ajustée dynamiquement pour maintenir un équilibre entre la mémoire utilisée et les performances.
Exemple :

Lorsque le taux de remplissage dépasse 70 %, doubler la taille de la table et ré-hasher les clés.

2.4 Prévention des chaînes longues

Dans le chaînage, éviter les longues listes liées en optimisant la répartition des clés avec une fonction de hachage plus performante et en limitant le taux de remplissage.

3. Exemples de cas optimisés

3.1 Optimisation des recherches par hachage double

Utiliser deux fonctions de hachage pour réduire les risques de collision.
Exemple de double hachage :

int hash_function2(const char *key, int table_size) {
    int hash = 0;
    while (*key) {
        hash = (hash * 33) ^ *key++;
    }
    return (hash % (table_size - 1)) + 1;
}

3.2 Utilisation de tables de hachage en C++ ou en Java

Dans les projets nécessitant une implémentation avancée, les tables de hachage prédéfinies (comme std::unordered_map en C++ ou HashMap en Java) intègrent déjà des optimisations pour éviter les collisions et ajuster dynamiquement la taille de la table.

4. Analyse des performances

Méthode	Complexité moyenne	Complexité pire cas
Recherche simple (sans collision)	O(1)	O(1)
Recherche avec chaînage	O(1)	O(n)
Recherche avec probing	O(1)	O(n)

Les optimisations décrites permettent de minimiser les risques de collisions et d’assurer des performances constantes même avec un grand nombre de données.

Conclusion

Les tables de hachage, lorsqu’elles sont correctement optimisées, constituent un outil puissant pour des applications allant des dictionnaires aux systèmes de cache. En combinant une fonction de hachage efficace, une gestion dynamique de la taille et des techniques avancées comme le double hachage ou le chaînage amélioré, elles peuvent atteindre des performances quasi optimales, même dans des cas d’utilisation exigeants.

Conclusion

Dans cet article, nous avons exploré les principes fondamentaux des tables de hachage, leur fonctionnement, ainsi que leur implémentation en C. Nous avons vu comment elles permettent une indexation rapide des données grâce à une fonction de hachage efficace, tout en comprenant les défis liés aux collisions et les solutions pour les surmonter, comme le chaînage ou le probing linéaire.

Les cas pratiques démontrent la puissance des tables de hachage dans des domaines tels que la gestion des dictionnaires, les systèmes de cache et les bases de données. De plus, les optimisations, comme le choix d’une bonne fonction de hachage et l’ajustement dynamique de la taille de la table, garantissent des performances constantes, même avec des volumes importants de données.

Une implémentation réussie d’une table de hachage en C exige une maîtrise des structures de données et des techniques d’optimisation. Avec les outils et les exemples fournis, vous êtes désormais équipé pour intégrer cette structure de données essentielle dans vos projets.