Performance Considerations
Buckets and load factor.
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;
}All lessons in this course
- std::unordered_map
- unordered_set
- Custom Hash Functions
- Performance Considerations