Structures de données en C/C++

La table de hachage (hash table) en C et C++

Dans cette leçon, vous allez compter le nombre d'apparitions de chaque mot avec une table de hachage écrite à la main en C et avec std::unordered_map en C++.

Introduction

Une table de hachage (hash table) utilise une fonction de hachage (hash function) pour transformer chaque clé en indice d'une case de stockage (bucket), ce qui rend la recherche, l'insertion et la suppression très rapides. Quand deux clés différentes tombent dans la même case, on parle de collision, et la table doit la gérer par chaînage (chaining) ou par adressage ouvert (open addressing).

Points importants

Définissez les conditions qui doivent toujours être vraies (invariants) avant d'écrire les opérations.
Traitez les cas de structure vide, pleine et d'échec d'allocation mémoire.
Évaluez ensemble la complexité et la gestion mémoire de chaque opération.

Voir comment ça marche

Tapez une clé puis enregistrez-la ou cherchez-la. La clé est hachée en un numéro de case, donc le programme va directement à la bonne case.

Exemples de code C et C++

Exécuter →

main.c

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

typedef struct Item {
    const char *key;
    int count;
    struct Item *next;
} Item;

unsigned hash(const char *text) {
    unsigned value = 5381;
    while (*text) {
        value = value * 33u ^ (unsigned char)*text++;
    }
    return value % 5;
}

int main(void) {
    const char *words[] = {"c", "cpp", "c"};
    Item items[2] = {{"c", 0, NULL}, {"cpp", 0, NULL}};
    Item *buckets[5] = {0};

    for (int index = 0; index < 2; ++index) {
        unsigned bucket = hash(items[index].key);
        items[index].next = buckets[bucket];
        buckets[bucket] = &items[index];
    }
    for (int index = 0; index < 3; ++index) {
        Item *item = buckets[hash(words[index])];
        for (; item; item = item->next) {
            if (strcmp(item->key, words[index]) == 0) {
                ++item->count;
                break;
            }
        }
    }
    printf("c=%d cpp=%d\n", items[0].count, items[1].count);
}

Résultat de l’exécution

c=2 cpp=1

C++

Exécuter →

main.cpp

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> counts;
    for (const std::string word : {"c", "cpp", "c"}) {
        ++counts[word];
    }
    std::cout << "c=" << counts["c"]
              << " cpp=" << counts["cpp"] << '\n';
}

Résultat de l’exécution

c=2 cpp=1

Comparaison entre C et C++

La fonction hash en C calcule une valeur à partir des caractères de la chaîne, puis prend le reste de la division par 5 pour choisir l'un des 5 buckets. Chaque bucket est une liste chaînée, les mots en collision sont donc enchaînés dans le même bucket. L'exemple C n'utilise que quelques mots fixes pour se concentrer sur le mécanisme des buckets. En C++, std::unordered_map gère lui-même les nœuds, s'agrandit si besoin et accepte n'importe quelle chaîne comme clé.

Les données (struct) et les opérations sont séparées, et la mémoire est allouée et libérée à la main.

C++

Les classes et les conteneurs protègent la cohérence des données et gèrent eux-mêmes leurs ressources.

Exercices d'approfondissement

Exécutez les deux versions, puis modifiez le code pour observer la différence de sécurité qu'apporte chaque langage.

Ajoutez des tests pour l'état vide et pour le moment où la capacité maximale est atteinte.
Écrivez la libération de la mémoire et vérifiez qu'il n'y a pas de fuite.
Comparez la complexité avec celle du conteneur équivalent de la bibliothèque standard.

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis