stl · advanced

STL: unordered_map Internals — Hash Table, Chaining, Rehash, Custom Hash

std::unordered_map is a hash table with separate chaining. Structure: vector of N buckets; each bucket = linked list of (key, value) pairs. Insert/find: hash(key) % N → bucket index; search/prepend to that bucket's list. Load factor = n/N. Rehash when load > max_load_factor (default 1.0, tune with max_load_factor()). Rehash: allocate 2N buckets, re-insert all elements — O(n) work, amortized O(1) per insert. All iterators are invalidated on rehash — store keys, not iterators, if container may grow. Worst case O(n): all keys hash to same bucket (hash DoS attack — use randomized seed in production). Custom types: specialize std::hash<T> with field combination (XOR + magic constant); provide operator==. reserve(n): pre-size to avoid rehashes. vs std::map: unordered_map O(1) avg, no ordering, no range query; map O(log n) always, sorted, lower_bound.

The code

// std::unordered_map — hash table with separate chaining
// Structure: array of N buckets; each bucket = linked list
// hash(key) % N → bucket index → search/insert in that list

unordered_map<string, int> m;
m.reserve(16);         // avoid rehash; sets bucket count
m.max_load_factor(0.7);// rehash threshold (default 1.0)

m["alice"] = 42;        // hash("alice") % N → bucket 3
m["bob"]   = 7;         // hash("bob")   % N → bucket 7
m["carol"] = 99;        // hash("carol") % N → bucket 3 (collision!)

// Lookup: O(1) avg
auto it = m.find("alice");  // hash → bucket → linear search chain
if (it != m.end())           // never use m[key] just to check — inserts!
    cout << it->second;

// Rehash when load_factor > max_load_factor:
// 1. allocate 2N new buckets
// 2. re-hash every element into new buckets
// 3. all iterators invalidated!
// Amortized: O(n) total, O(1) per insert

// Iteration order is UNDEFINED (unlike map)
for (auto& [k,v] : m)  // order depends on hash values
    cout << k;          // not sorted!

// Avoid worst case: use a good hash function
// DoS attack: all keys hash to same bucket → O(n) lookup
// std::hash<string> is deterministic — use randomized hash in untrusted input

What this lesson walks through

1. 01Hash table structure — bucket array + chaining
2. 02Insert 'alice' → hash → bucket 3
3. 03Insert 'bob' → different bucket → no collision
4. 04Insert 'carol' → collision with 'alice' in bucket 3
5. 05Lookup 'carol' — hash → chain search
6. 06Custom hash + hash table vs map — when to use each

std::unordered_map is an array of N buckets. Each bucket holds a linked list of (key, value) pairs (separate chaining). To find or insert a key: hash(key) % N gives the bucket index. Then search the chain. Average chain length = load_factor = n/N. When load_factor exceeds max_load_factor (default 1.0), rehash doubles N.