C++ Academy · Leçon

Considérations de performance

Buckets et facteur de charge

Considérations de performance 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.

Comment les tables de hachage stockent les données

Un conteneur non ordonné contient un tableau de buckets. Le hachage d’une clé sélectionne un bucket ; plusieurs clés dans un même bucket forment une chaîne parcourue linéairement.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 1}, {2, 2}, {3, 3}};
    std::cout << "bucket count: " << m.bucket_count() << '\n';
    return 0;
}

Dans quel bucket ?

bucket(key) vous indique l’indice du bucket auquel une clé est actuellement associée.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{10, 1}, {20, 2}, {30, 3}};
    std::cout << "key 20 in bucket " << m.bucket(20) << '\n';
    return 0;
}

Facteur de charge

Le facteur de charge est égal à size / bucket_count. Une charge plus élevée signifie des chaînes plus longues et des recherches plus lentes.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 1}, {2, 2}};
    std::cout << "load factor: " << m.load_factor() << '\n';
    return 0;
}

Facteur de charge maximal

max_load_factor() définit le seuil. Lorsque le facteur de charge le dépasse, la table effectue un rehash dans un plus grand nombre de buckets.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    std::cout << "default max load: " << m.max_load_factor() << '\n';
    return 0;
}

Réhachage

Le réhachage reconstruit la table avec davantage de buckets et coûte cher. Il se produit automatiquement lorsque le facteur de charge est dépassé.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    std::size_t before = m.bucket_count();
    for (int i = 0; i < 100; ++i) m[i] = i;
    std::cout << before << " -> " << m.bucket_count() << " buckets\n";
    return 0;
}

Réserver pour éviter les réhachages

Si vous connaissez à l’avance la taille nécessaire, appelez reserve(n) pour préallouer les buckets et éviter les réhachages répétés.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.reserve(1000);
    std::cout << "buckets reserved: " << (m.bucket_count() >= 1000 ? "yes" : "no") << '\n';
    return 0;
}

rehash directement

rehash(n) définit le nombre de buckets à une valeur au moins égale à n. Utilisez reserve pour le nombre d’éléments et rehash pour le nombre de buckets.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.rehash(64);
    std::cout << "buckets >= 64: " << (m.bucket_count() >= 64 ? "yes" : "no") << '\n';
    return 0;
}

Examiner la taille des buckets

bucket_size(i) indique combien d’éléments partagent le bucket i, ce qui est utile pour diagnostiquer les collisions.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    for (int i = 0; i < 10; ++i) m[i] = i;
    std::cout << "bucket 0 holds " << m.bucket_size(0) << " elements\n";
    return 0;
}

Le pire cas est O(n)

Avec un mauvais hachage qui provoque de nombreuses collisions, toutes les clés s’enchaînent dans un seul bucket et les opérations se dégradent jusqu’à un temps linéaire. Un bon hachage maintient les opérations en O(1).

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    for (int i = 0; i < 5; ++i) m[i] = i * i;
    std::cout << "avg lookups stay fast with good hashing\n";
    std::cout << "load: " << m.load_factor() << '\n';
    return 0;
}

Réduire le facteur de charge maximal

Définir un max_load_factor plus faible échange de la mémoire contre de la vitesse : moins de collisions, mais davantage de buckets.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.max_load_factor(0.5f);
    std::cout << "new max load: " << m.max_load_factor() << '\n';
    return 0;
}

Invalidation des itérateurs

Un réhachage invalide les itérateurs, mais conserve la validité des références et des pointeurs vers les éléments. Organisez vos boucles en conséquence.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 100}};
    int& ref = m[1];
    m.reserve(500);
    std::cout << "reference still valid: " << ref << '\n';
    return 0;
}

Vérification rapide

Évaluez votre compréhension des performances des tables de hachage.

Récapitulatif

Vous avez étudié le fonctionnement interne des tables de hachage :

les clés sont associées à des compartiments ; les collisions forment des chaînes
facteur de charge = taille / bucket_count ; son dépassement de max_load_factor déclenche un nouveau hachage
utilisez reserve pour éviter un nouveau hachage ; celui-ci invalide les itérateurs, mais pas les références

Prochain cours : lire et écrire des fichiers avec fstream.

Questions Fréquemment Posées

La leçon « Considérations de performance » est-elle gratuite ?

Oui — le texte complet de « Considérations de performance » 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 « Considérations de performance » ?

Buckets et facteur de charge 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 « Considérations de performance » ?

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