How hash tables work
Hash functions, buckets, collisions, chaining and load factor, the ideas behind std::unordered_map.
A hash table turns a key into a number with a hash function, then uses that number to pick a bucket. Looking up the key means hashing it again and checking only that bucket, which is why lookups are O(1) on average.
Two keys can land in the same bucket (a collision). With chaining, each bucket holds a small list. The load factor (items divided by buckets) is kept low by growing the table and rehashing everything when it gets too full.
A bad hash function that sends many keys to one bucket turns lookups into O(n) scans.
Example
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> counts;
for (std::string w : {"red", "blue", "red", "green", "red"}) counts[w]++;
std::cout << counts["red"] << " " << counts.size() << " " << (counts.load_factor() <= counts.max_load_factor()) << "\n";
return 0;
}
Output:
3 3 1