Performance Considerations
Buckets and load factor.
Performance Considerations is a free C++ Academy lesson on CoddyKit. This is lesson 4 of 4. Any 3 lessons of this learning path are free to read in full — after that, CoddyKit PRO unlocks every lesson, plus hands-on practice with a built-in code editor and a 24/7 AI tutor. It is part of the C++ Academy learning path, and your progress syncs across the web and the CoddyKit app. The C++ Academy course includes 4 lessons in total.
How Hash Tables Store Data
An unordered container holds an array of buckets. The hash of a key picks a bucket; multiple keys in one bucket form a chain that is searched linearly.
#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;
}Which Bucket?
bucket(key) tells you which bucket index a key maps to right now.
#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;
}Load Factor
The load factor is size / bucket_count. A higher load means longer chains and slower lookups.
#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;
}Max Load Factor
max_load_factor() is the threshold. When the load factor exceeds it, the table rehashes into more 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;
}Rehashing
Rehashing rebuilds the table with more buckets and is expensive. It happens automatically when the load factor is exceeded.
#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 to Avoid Rehashes
If you know the size ahead of time, call reserve(n) to pre-allocate buckets and avoid repeated rehashing.
#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 Directly
rehash(n) sets the bucket count to at least n. Use reserve for element counts and rehash for bucket counts.
#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;
}Inspecting Bucket Sizes
bucket_size(i) reveals how many elements share bucket i, useful for diagnosing 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;
}Worst Case Is O(n)
With a bad hash that collides heavily, all keys chain in one bucket and operations degrade to linear time. A good hash keeps things 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;
}Lowering Max Load Factor
Setting a lower max_load_factor trades memory for speed: fewer collisions, but more 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;
}Iterator Invalidation
A rehash invalidates iterators but keeps references and pointers to elements valid. Plan loops accordingly.
#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;
}Quick Check
Test your understanding of hash table performance.
Recap
You learned hash table internals:
- keys map to buckets; collisions form chains
- load factor = size / bucket_count; exceeding
max_load_factortriggers a rehash - use
reserveto avoid rehashing; a rehash invalidates iterators but not references
Next course: reading and writing files with fstream.
Learn C++ with an AI tutor — free
Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.
- Courses
- 51
- Lessons
- 203
Frequently Asked Questions
Is the “Performance Considerations” lesson free?
Yes — any 3 lessons of the C++ Academy learning path, including “Performance Considerations”, are free to read in full here on the web. After that, CoddyKit PRO unlocks every lesson, plus interactive practice with a built-in code editor and a 24/7 AI tutor. The C++ Academy course includes 4 lessons in total.
What will I learn in “Performance Considerations”?
Buckets and load factor. You practise C++ Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start C++ Academy?
No prior experience is required. C++ Academy on CoddyKit is structured for beginners through advanced learners, so you can start here or from the beginning and move at your own pace. This is lesson 4 of 4.
How long does the “Performance Considerations” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this C++ Academy lesson?
Yes. Every C++ Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- std::unordered_map
- unordered_set
- Custom Hash Functions
- Performance Considerations