C Academy · Leçon

Gestion des collisions

Chaînage et sondage

Gestion des collisions est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C Academy comprend 4 leçons au total.

Le problème des collisions

Une collision se produit lorsque deux clés distinctes sont hachées vers le même compartiment. Les collisions étant inévitables, toute table de hachage doit disposer d’une stratégie pour stocker plusieurs clés dans un même emplacement.

Les deux grandes familles sont le chaînage et l’adressage ouvert.

Chaînage séparé

Avec le chaînage séparé, chaque compartiment contient une liste chaînée d’entrées. En cas de collision, il vous suffit d’ajouter l’entrée à la fin (ou au début) de la liste de ce compartiment.

Les compartiments stockent les têtes de liste
Les recherches parcourent une seule petite liste

Structure d’un nœud de chaînage

Chaque nœud stocke une clé, une valeur et un pointeur next. La table est un tableau de pointeurs vers des nœuds.

#include <stdio.h>

typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;

int main(void) {
    Node *buckets[8] = {0};
    printf("slots = %zu\n", sizeof buckets / sizeof buckets[0]);
    return 0;
}

Insérer avec le chaînage

Ajouter un élément au début de la liste d’un compartiment s’effectue en O(1). Ici, nous construisons manuellement une petite chaîne et l’affichons.

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

typedef struct Node { int key; struct Node *next; } Node;

Node *prepend(Node *head, int key) {
    Node *n = malloc(sizeof *n);
    n->key = key; n->next = head;
    return n;
}

int main(void) {
    Node *bucket = NULL;
    bucket = prepend(bucket, 10);
    bucket = prepend(bucket, 26); /* same bucket as 10 mod 8 */
    for (Node *p = bucket; p; p = p->next)
        printf("%d ", p->key);
    printf("\n");
    return 0;
}

Adressage ouvert

Avec l’adressage ouvert, chaque entrée se trouve directement dans le tableau des compartiments. En cas de collision, vous sondez d’autres emplacements libres en suivant une séquence fixe.

Aucun nœud supplémentaire n’est alloué, ce qui favorise l’utilisation du cache.

Sondage linéaire

Le sondage linéaire vérifie l’emplacement suivant, puis le suivant, en revenant au début si nécessaire : (h + i) % capacity.

Cette méthode est simple et favorise l’utilisation du cache, mais elle souffre du regroupement.

#include <stdio.h>

int main(void) {
    int slots[8] = {0,0,1,0,0,0,0,0}; /* slot 2 taken */
    unsigned h = 2, cap = 8;
    for (unsigned i = 0; i < cap; i++) {
        unsigned idx = (h + i) % cap;
        if (!slots[idx]) { printf("insert at %u\n", idx); break; }
    }
    return 0;
}

Sondage quadratique

Le sondage quadratique utilise (h + i*i) % capacity pour mieux répartir les sondages et réduire le regroupement primaire.

#include <stdio.h>

int main(void) {
    unsigned h = 3, cap = 8;
    for (unsigned i = 0; i < 4; i++)
        printf("probe %u -> slot %u\n", i, (h + i*i) % cap);
    return 0;
}

Double hachage

Le double hachage utilise un second hachage pour déterminer le pas : (h1 + i*h2) % capacity. Chaque clé dispose ainsi de sa propre séquence de sondage, ce qui offre la meilleure répartition des trois méthodes.

#include <stdio.h>

int main(void) {
    unsigned h1 = 3, h2 = 5, cap = 8;
    for (unsigned i = 0; i < 4; i++)
        printf("probe %u -> slot %u\n", i, (h1 + i*h2) % cap);
    return 0;
}

Suppression avec l’adressage ouvert

Vous ne pouvez pas simplement vider un emplacement avec l’adressage ouvert, car cela romprait les chaînes de sondage d’autres clés. Marquez-le plutôt comme une case supprimée, afin que les recherches continuent à sonder au-delà.

Chaînage ou adressage ouvert

Compromis :

Chaînage : gère les facteurs de charge élevés et permet des suppressions simples, mais utilise des pointeurs et des allocations
Adressage ouvert : favorise l’utilisation du cache et n’effectue aucune allocation par entrée, mais se dégrade fortement lorsque la table est presque pleine et nécessite des cases supprimées

Démonstration du nombre de sondages

Le sondage linéaire peut nécessiter plusieurs étapes lorsque les emplacements sont regroupés. Ici, nous comptons les sondages nécessaires pour trouver un emplacement libre.

#include <stdio.h>

int main(void) {
    int slots[8] = {1,1,1,0,0,0,0,0};
    unsigned h = 0, cap = 8, probes = 0;
    for (unsigned i = 0; i < cap; i++) {
        probes++;
        if (!slots[(h + i) % cap]) break;
    }
    printf("probes used = %u\n", probes);
    return 0;
}

Vérification rapide

Testez vos connaissances sur la gestion des collisions.

Récapitulatif

Vous avez étudié la manière dont les tables de hachage résolvent les collisions.

Le chaînage stocke une liste chaînée par compartiment
L’adressage ouvert sonde les emplacements à la recherche d’une case libre
Variantes du sondage : linéaire, quadratique et double hachage
L’adressage ouvert nécessite des cases supprimées pour les suppressions

Questions Fréquemment Posées

La leçon « Gestion des collisions » est-elle gratuite ?

Oui — le texte complet de « Gestion des collisions » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C Academy, passe à CoddyKit PRO. Le cours C Academy comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Gestion des collisions » ?

Chaînage et sondage Tu pratiques C Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer C Academy ?

Aucune expérience préalable n'est requise. C Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.

Combien de temps prend la leçon « Gestion des collisions » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon C Academy ?

Oui. Chaque leçon C Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

← Retour à C Academy