unordered_map & unordered_set — hash internals
Scenario
You write a blazing fast O(1) hash map solution. It passes 99% of the test cases. On the last test case, it times out. You realize the system specifically fed your map keys that all evaluated to the same hash.
How can an O(1) hash map suddenly degrade to O(N) performance?
Mental model
A Hash Table is like a mailroom with 100 buckets. A hash function looks at an envelope's name and assigns it a bucket number. If the hash function is good, mail is spread evenly (O(1) to find it). If the hash function is terrible and puts every envelope in Bucket #7, you have to dig through Bucket #7 one by one (O(N)).
`std::unordered_map` and `std::unordered_set` are implemented as Hash Tables. They provide O(1) average time complexity for lookups, insertions, and deletions. However, understanding how they resolve collisions via "chaining" is critical for avoiding Worst-Case O(N) scenarios.
Explanation
**How it works:**
When you insert a key, `std::hash` runs on the key to produce an integer. This integer is modulo'd by the number of "buckets" in the table to determine where the data lives.
**Collisions & Chaining:**
Because there are infinite possible keys but a finite number of buckets, two different keys will inevitably hash to the same bucket. C++ resolves this using *chaining*: each bucket is actually a linked list. If a bucket has 5 items in it, the map must traverse that linked list to find the exact key. If all your keys collide into the same bucket, the map degenerates into a single linked list, resulting in O(N) performance.
**Rehashing:**
As the map grows, the "Load Factor" (number of elements / number of buckets) increases. When the load factor exceeds a threshold (typically 1.0), the map automatically allocates a much larger bucket array and recalculates the bucket index for every single element. This "rehash" is an expensive O(N) operation and invalidates all iterators.
**Custom Keys:**
To use a custom struct as a key, you must provide two things: an `operator==` (so the map can check if two colliding items in a bucket are actually identical) and a custom hash function injected into `std::hash`. Note that C++ does **not** provide default `std::hash` specializations for common containers like `std::vector` or `std::pair`, meaning they cannot be used as keys out-of-the-box without writing your own hash function.
**Real-world Engineering:** Custom hash functions are commonly needed when caching expensive computations (Memoization), such as caching 2D grid pathfinding results where the key is a `std::pair<int, int>` coordinate.
Code examples
Custom Hash Functions
#include <iostream>
#include <unordered_set>
struct Point {
int x, y;
// 1. Must define equality so the map can resolve collisions
bool operator==(const Point& other) const {
return x == other.x && y == other.y;
}
};
// 2. Must define a custom hash function in the std namespace
namespace std {
template <>
struct hash<Point> {
size_t operator()(const Point& p) const {
// Combine the hashes of x and y.
// Using bitwise XOR (^) is a simple way to combine hashes.
return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
}
};
}
int main() {
std::unordered_set<Point> points;
points.insert({1, 2});
points.insert({3, 4});
return 0;
}Because C++ does not automatically know how to hash a `Point`, you must explicitly tell it how to combine the hashes of its fundamental components.
Key points
- O(1) Average, O(N) Worst: Hash tables are lightning fast, but bad hashes or malicious inputs can degrade them to linear time.
- Rehashing invalidates iterators: Like vectors, unordered maps reallocate memory (for buckets) as they grow, completely invalidating existing iterators.
Common mistakes
- Assuming unordered_map is always strictly O(1): In competitive programming (like Codeforces), malicious test cases are designed specifically to cause hash collisions in C++'s default `std::hash`, forcing your `unordered_map` into worst-case O(N) performance and causing a Time Limit Exceeded (TLE) error. CPers often write custom, randomized hash functions to prevent this.
Recall questions
- What happens when two different keys in an `unordered_map` hash to the same bucket?
- What two things are required to use a custom class/struct as a key in an `unordered_map`?
- What triggers an `unordered_map` to rehash all its elements?
Questions & answers
A developer writes an `unordered_map` where the hash function simply returns `1` for every single key. The equality operator `==` works perfectly. What is the time complexity of a lookup?
O(N). Because every key returns the hash `1`, every element is placed into the exact same bucket. The map degrades into a single linked list, forcing a linear scan for every lookup.
Approach: Understand the consequences of hash collisions on time complexity.
A team decides to use a `std::unordered_map<std::vector<int>, int>` to memoize the results of a complex graph traversal. The code refuses to compile. Why, and how can it be fixed?
It fails to compile because C++ does not provide a default `std::hash` specialization for `std::vector` (unlike Python's tuples). You must either write a custom hash function that hashes and combines the elements of the vector, or use a `std::map` instead, which only requires the `operator<` (which `std::vector` already provides).
Approach: Recognize that STL containers don't have default hash functions in C++.