Prestatieoverwegingen
Buckets en loadfactor
Prestatieoverwegingen is een gratis C++ Academy-les op CoddyKit. Dit is les 4 van 4. Je kunt 3 lessen uit dit leerpad gratis volledig lezen — daarna ontgrendelt CoddyKit PRO alle lessen, plus praktische oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject C++ Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus C++ Academy bevat in totaal 4 lessen.
Hoe hashtabellen gegevens opslaan
Een ongeordende container bevat een reeks buckets. De hash van een sleutel kiest een bucket; meerdere sleutels in één bucket vormen een keten die lineair wordt doorzocht.
#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;
}Welke bucket?
bucket(key) vertelt je naar welke bucketindex een sleutel op dit moment verwijst.
#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;
}Vulfactor
De vulfactor is size / bucket_count. Een hogere vulfactor betekent langere ketens en langzamere zoekopdrachten.
#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;
}Maximale vulfactor
max_load_factor() is de drempelwaarde. Wanneer de vulfactor deze overschrijdt, wordt de tabel opnieuw gehasht met meer 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;
}Opnieuw hashen
Opnieuw hashen bouwt de tabel opnieuw op met meer buckets en is duur. Het gebeurt automatisch wanneer de vulfactor wordt overschreden.
#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;
}reserve gebruiken om opnieuw hashen te voorkomen
Als je de grootte vooraf kent, roep je reserve(n) aan om vooraf buckets toe te wijzen en herhaald opnieuw hashen te voorkomen.
#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;
}Rechtstreeks rehash gebruiken
rehash(n) stelt het aantal buckets in op ten minste n. Gebruik reserve voor aantallen elementen en rehash voor aantallen 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;
}Bucketgroottes bekijken
bucket_size(i) laat zien hoeveel elementen bucket i delen. Dat is nuttig om botsingen op te sporen.
#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;
}Slechtste geval is O(n)
Bij een slechte hash met veel botsingen worden alle sleutels in één bucket aan elkaar gekoppeld en verslechteren bewerkingen tot lineaire tijd. Een goede hash houdt ze op 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;
}Maximale vulfactor verlagen
Een lagere max_load_factor instellen ruilt geheugen in voor snelheid: minder botsingen, maar meer 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;
}Ongeldigheid van iterators
Opnieuw hashen maakt iterators ongeldig, maar houdt verwijzingen en aanwijzers naar elementen geldig. Plan je lussen hierop.
#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;
}Snelle controle
Test je begrip van de prestaties van hashtabellen.
Samenvatting
Je hebt de interne werking van hashtabellen geleerd:
- sleutels worden aan buckets gekoppeld; botsingen vormen ketens
- vullingsfactor = size / bucket_count; als deze groter wordt dan
max_load_factor, wordt opnieuw gehasht - gebruik
reserveom opnieuw hashen te voorkomen; opnieuw hashen maakt iterators ongeldig, maar niet verwijzingen
Volgende cursus: bestanden lezen en schrijven met fstream.
Leer C++ met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 51
- Lessen
- 203
Veelgestelde vragen
Is de les “Prestatieoverwegingen” gratis?
Ja — je kunt hier op het web alle 3 lessen van het leerpad C++ Academy, waaronder “Prestatieoverwegingen”, gratis volledig lezen. Daarna ontgrendelt CoddyKit PRO alle lessen, plus interactieve oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. De cursus C++ Academy bevat in totaal 4 lessen.
Wat leer ik in “Prestatieoverwegingen”?
Buckets en loadfactor Je oefent met C++ Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met C++ Academy te beginnen?
Ervaring vooraf is niet nodig. C++ Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Prestatieoverwegingen”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over C++ Academy?
Ja. Elke les over C++ Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- std::unordered_map
- unordered_set
- Aangepaste hashfuncties
- Prestatieoverwegingen