C++ Academy · Lektion

Überlegungen zur Performance

Buckets und Load Factor

Überlegungen zur Performance ist eine kostenlose C++ Academy-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C++ Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C++ Academy-Kurs umfasst insgesamt 4 Lektionen.

So speichern Hash-Tabellen Daten

Ein ungeordneter Container enthält ein Array aus Buckets. Der Hash eines Schlüssels wählt einen Bucket aus. Mehrere Schlüssel in einem Bucket bilden eine Kette, die linear durchsucht wird.

#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;
}

Welcher Bucket?

bucket(key) gibt an, auf welchen Bucket-Index ein Schlüssel derzeit abgebildet wird.

#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;
}

Auslastungsfaktor

Der Auslastungsfaktor ist size / bucket_count. Eine höhere Auslastung bedeutet längere Ketten und langsamere Suchen.

#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;
}

Maximaler Auslastungsfaktor

max_load_factor() ist der Schwellenwert. Sobald der Auslastungsfaktor diesen überschreitet, führt die Tabelle ein Rehashing in weitere Buckets durch.

#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;
}

Rehashing

Beim Rehashing wird die Tabelle mit mehr Buckets neu aufgebaut, was aufwendig ist. Es erfolgt automatisch, sobald der Auslastungsfaktor überschritten wird.

#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;
}

Rehashing mit reserve vermeiden

Wenn Sie die Größe im Voraus kennen, rufen Sie reserve(n) auf, um Buckets vorab zu reservieren und wiederholtes Rehashing zu vermeiden.

#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 direkt verwenden

rehash(n) setzt die Anzahl der Buckets auf mindestens n. Verwenden Sie reserve für die Anzahl der Elemente und rehash für die Anzahl der 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;
}

Bucket-Größen untersuchen

bucket_size(i) zeigt, wie viele Elemente sich Bucket i teilen. Das ist nützlich, um Kollisionen zu untersuchen.

#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;
}

Der Worst Case ist O(n)

Bei einem schlechten Hash mit vielen Kollisionen werden alle Schlüssel in einem Bucket verkettet, und die Operationen verschlechtern sich auf lineare Zeit. Ein guter Hash hält sie bei 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;
}

Maximalen Auslastungsfaktor senken

Ein niedrigerer max_load_factor tauscht Speicher gegen Geschwindigkeit: Es gibt weniger Kollisionen, aber mehr 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;
}

Ungültigwerden von Iteratoren

Ein Rehashing macht Iteratoren ungültig, erhält aber Referenzen und Zeiger auf Elemente gültig. Planen Sie Schleifen entsprechend.

#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;
}

Kurztest

Testen Sie Ihr Verständnis der Leistungsfähigkeit von Hash-Tabellen.

Zusammenfassung

Sie haben die Interna von Hash-Tabellen kennengelernt:

Schlüssel werden auf Buckets abgebildet; Kollisionen bilden Ketten
Lastfaktor = size / bucket_count; beim Überschreiten von max_load_factor wird ein Rehashing ausgelöst
Verwenden Sie reserve, um Rehashing zu vermeiden; ein Rehashing macht Iteratoren ungültig, aber keine Referenzen

Nächster Kurs: Lesen und Schreiben von Dateien mit fstream.

Häufig gestellte Fragen

Ist die Lektion „Überlegungen zur Performance“ kostenlos?

Ja — der vollständige Text von „Überlegungen zur Performance“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C++ Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C++ Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Überlegungen zur Performance“?

Buckets und Load Factor Du übst C++ Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um C++ Academy zu starten?

Keine Vorkenntnisse erforderlich. C++ Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.

Wie lange dauert die Lektion „Überlegungen zur Performance“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser C++ Academy-Lektion Code schreiben und ausführen?

Ja. Jede C++ Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

← Zurück zu C++ Academy