C Academy · Leçon

Redimensionnement et facteur de charge

Réglage des performances

Redimensionnement et facteur de charge est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 4 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.

Qu’est-ce que le facteur de charge

Le facteur de charge est le rapport entre le nombre d’entrées stockées et le nombre de compartiments : alpha = size / capacity. Il mesure le degré de remplissage de la table et influence directement ses performances.

Pourquoi le facteur de charge est important

À mesure que le facteur de charge augmente, les compartiments contiennent des chaînes plus longues (ou les sondages se regroupent), ce qui ralentit les opérations.

Alpha faible : rapide, mais gaspille de la mémoire
Alpha élevé : compact, mais lent

Pour le chaînage, une valeur cible courante est 0,75.

Calculer le facteur de charge

Calculez-le comme un rapport en virgule flottante afin de pouvoir le comparer à un seuil.

#include <stdio.h>

int main(void) {
    unsigned size = 12, capacity = 16;
    double alpha = (double)size / capacity;
    printf("load factor = %.2f\n", alpha);
    return 0;
}

Quand redimensionner

Après chaque insertion, vérifiez si le facteur de charge dépasse le seuil. Si c’est le cas, agrandissez la table (en doublant généralement sa capacité), puis effectuez un nouveau hachage.

#include <stdio.h>

int should_grow(unsigned size, unsigned cap) {
    return (double)size / cap > 0.75;
}

int main(void) {
    printf("%d\n", should_grow(13, 16)); /* 0.8125 -> 1 */
    printf("%d\n", should_grow(10, 16)); /* 0.625  -> 0 */
    return 0;
}

Explication du nouveau hachage

Vous ne pouvez pas copier les compartiments sans réflexion, car l’indice de chaque clé dépend de la capacité. Le nouveau hachage recalcule le compartiment de chaque clé avec la nouvelle capacité, puis la réinsère.

Une fonction de redimensionnement

Allouez un tableau de compartiments plus grand, parcourez chaque ancien nœud et déplacez-le dans le nouveau tableau en utilisant la nouvelle capacité, puis échangez les tableaux. Voici le recalcul essentiel de l’indice.

#include <stdio.h>

unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}

int main(void) {
    const char *key = "session";
    unsigned old_cap = 8, new_cap = 16;
    printf("old slot = %lu\n", djb2(key) % old_cap);
    printf("new slot = %lu\n", djb2(key) % new_cap);
    return 0;
}

Déplacer les nœuds sans les réallouer

Avec le chaînage, vous pouvez déplacer les nœuds existants dans le nouveau tableau au lieu d’en allouer de nouveaux. Détachez chaque nœud, recalculez son compartiment, puis ajoutez-le au début.

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

typedef struct Node { char *key; struct Node *next; } Node;
unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}

int main(void) {
    Node *old[2] = {0};
    Node *a = malloc(sizeof *a); a->key = strdup("x"); a->next = NULL; old[0] = a;
    Node *new_b[4] = {0};
    /* move node a */
    unsigned i = djb2(a->key) % 4;
    a->next = new_b[i]; new_b[i] = a;
    printf("moved to slot %u\n", i);
    return 0;
}

Stratégie d’agrandissement

Doubler la capacité maintient le coût amorti d’une insertion à O(1) : bien qu’un redimensionnement coûte O(n), il survient suffisamment rarement pour que le coût moyen par insertion reste constant.

Les puissances de deux permettent également d’utiliser le masque AND rapide.

#include <stdio.h>

int main(void) {
    unsigned cap = 8;
    for (int i = 0; i < 4; i++) {
        printf("capacity = %u\n", cap);
        cap *= 2;
    }
    return 0;
}

Réduire la taille

Vous pouvez réduire la table lorsque le facteur de charge devient trop faible (par exemple sous 0,1) après de nombreuses suppressions. Cette réduction récupère de la mémoire, mais ajoute le coût d’un nouveau hachage ; effectuez-la donc avec prudence pour éviter les redimensionnements incessants.

Adressage ouvert et facteur de charge

Les tables à adressage ouvert sont beaucoup plus sensibles au facteur de charge. Les performances s’effondrent lorsque alpha approche de 1 ; elles sont donc généralement redimensionnées entre 0,5 et 0,7, une valeur inférieure à 0,75 pour le chaînage.

Démonstration du coût amorti

Simulez des insertions qui doublent la capacité à 0,75 et comptez le travail total, afin de montrer que la moyenne reste faible.

#include <stdio.h>

int main(void) {
    unsigned cap = 4, size = 0;
    long work = 0;
    for (int i = 0; i < 100; i++) {
        size++; work++; /* the insert */
        if ((double)size / cap > 0.75) { work += size; cap *= 2; } /* rehash */
    }
    printf("inserts=%u total_work=%ld avg=%.2f\n", size, work, (double)work/size);
    return 0;
}

Vérification rapide

Testez votre compréhension du redimensionnement.

Récapitulatif

Vous avez appris à régler les performances des tables de hachage.

Facteur de charge = taille / capacité
Redimensionnez lorsque le facteur dépasse un seuil (environ 0,75 pour le chaînage)
Effectuez un nouveau hachage, car les indices dépendent de la capacité
Le doublement assure des insertions en O(1) amorti

Questions Fréquemment Posées

La leçon « Redimensionnement et facteur de charge » est-elle gratuite ?

Oui — le texte complet de « Redimensionnement et facteur de charge » 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 « Redimensionnement et facteur de charge » ?

Réglage des performances 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 4 sur 4.

Combien de temps prend la leçon « Redimensionnement et facteur de charge » ?

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