Unordered Associative Containers (unordered_map, unordered_set)
In modern C++, we never guess what the compiler does. We look directly at byte offsets, CPU registers, and object ownership lifetimes.
It is implemented as a bucket array of singly-linked list nodes (Separate Chaining). The main object owns a dynamically allocated array of raw bucket pointers (__node_base* _M_buckets). When an element is inserted, hash(key) % bucket_count selects the bucket. Elements are allocated on the heap as __hash_node structures containing a next* pointer, a cached 64-bit hash code (in GCC libstdc++ to speed up rehash and comparisons), and std::pair<const Key, Val>. Collisions are resolved by chaining nodes into the bucket's linked list.
When load_factor() > max_load_factor(), rehash(new_buckets) allocates a new bucket pointer array (usually selecting the next prime number from an internal table). It iterates through all existing nodes, recalculates hash % new_bucket_count, and relinks the nodes into the new buckets.
- Iterator Invalidation: All iterators into the container are invalidated because the bucket structure and traversal sequence change.
- Reference / Pointer Invalidation: Pointers and references to existing elements remain 100% valid because the nodes themselves are not reallocated or moved in memory—only their
nextpointers are updated.
XOR is commutative ($a \oplus b == b \oplus a) and self-canceling (a \oplus a == 0$). For composite keys (like pair<int, int>), pairs with swapped values ((1, 2) and (2, 1)) produce identical hashes, and any pair where x == y always hashes to 0 regardless of magnitude. This causes severe hash collisions. The standard fix is the Boost golden ratio formula:
seed ^= hash(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2)
which introduces non-linear bit shifts and an irrational multiplier (the golden ratio fractional part $\approx 2^{32} / \phi$) to spread entropy across all bits.
Interviewer's lens
Unordered containers (std::unordered_map, std::unordered_set) reveal whether a candidate understands real-world memory access or merely repeats textbook Big-O:
- Textbook trap: Claiming lookups are 'always O(1)', unaware that bad hashes cause catastrophic O(N) collision degradation and resizing triggers sudden O(N) rehash latency pauses.
- Hardware reality: Standard library hash tables use Separate Chaining. Collisions turn into linked lists of scattered heap nodes, penalizing CPU cache lines.
- Senior skills expected: Knowing how
bucket_countscales along prime numbers, why rehashing invalidates iterators while element pointers stay 100% valid, writing collision-resistant multi-fieldhash_combineformulas with the golden ratio constant (0x9e3779b9), and locking down latency withreserve(N).
Under the hood & memory layout
Think of std::unordered_map as an array of numbered mailboxes, each holding a chain of hanging envelopes:
- Bucket Array Table: The container header points to a contiguous heap array of bucket heads (
_M_buckets), sized along prime numbers (13, 29, 59...) to disperse keys evenly. - Hanging Nodes (Separate Chaining): Every element is an isolated heap node (
__hash_node) holdingnext*(8 bytes), a cached 64-bit hash code (8 bytes), andstd::pair<const K, V>. - Load Factor Threshold: $\alpha = size() / bucket_count(). When \alpha > 1.0$, the mailbox rack is overstuffed.
- The Rehash Migration: The container allocates a brand new bucket array, computes
hash % new_bucketsfor each node, and re-hooks the chain pointers. Node memory never moves, so element references survive, but all iterators die.
A contiguous array of raw 8-byte pointers on the heap (__node_base** _M_buckets). Stored sizes typically follow a prime number sequence (e.g. 1, 13, 29, 61, 127, 257...) to minimize modulo clustering for low-entropy hashes.
Each element occupies its own heap block: __node_base* _M_next (8B), size_t _M_hash_code (8B cached hash), and std::pair<const K, V> payload. Memory overhead is at least 16 bytes per node plus allocator chunk headers.
Tracks ratio size() / bucket_count(). When an insertion exceeds max_load_factor(), rehash() expands the bucket array and redistributes node pointers, eliminating long collision chains.
Unlike std::vector, insertions that trigger rehash() do NOT move or reallocate existing nodes. Therefore, pointers and references to existing elements remain 100% valid across rehashes; only iterators (which track bucket traversal) are invalidated.
Core concepts & syntax traps
Bucket Array, Separate Chaining & Cached Hash Codes
Bucket Array, Separate Chaining & Cached Hash Codes
std::unordered_map resolves collisions using Separate Chaining—a bucket array of singly linked lists.
When evaluating map.find(key), the engine follows a 4-step path:
- Hash Calculation: Calls
hasher(key)to produce a 64-bit integer hash codeh. - Bucket Slotting: Computes
bucket_index = h % bucket_countto pick the target bucket. - Chain Crawl with Cached Hash: Walks the singly linked list at that bucket. Before comparing keys, it checks the cached 64-bit hash code stored in each node. If hash codes differ, it skips comparing immediately without invoking expensive key comparisons (e.g. string equality).
- Key Verification: When hash codes match, it invokes
key_equal(node.key, key)to confirm the exact key match.
Cache Locality Cost: Because each node is a separate heap allocation, traversing collision chains means chasing pointers across RAM, frequently causing L1/L2 cache misses.
std::unordered_map<int, std::string> m;
m[10] = "Apple";
// Inspect which bucket key 10 landed in:
size_t b = m.bucket(10);
size_t chain_len = m.bucket_size(b);
// chain_len is the number of collided elements in bucket bSeparate chaining stores collisions in singly-linked lists; average lookup is O(1) only if the hash function distributes keys evenly.
Load Factor, max_load_factor & O(N) Rehash Spikes
Load Factor, max_load_factor & O(N) Rehash Spikes
The Load Factor measures container crowding: $\alpha = \frac{size()}{bucket_count()}$.
- The Threshold: Standard library implementations set
max_load_factor()to1.0by default. - The Rehash Event: When an insertion pushes $\alpha > 1.0$,
rehash()runs a 3-step migration:- Allocates a larger bucket pointer array (scaled up by a prime number sequence in GCC libstdc++).
- Walks every existing node in the old buckets, re-indexes it (
hash % new_count), and rewires its pointer into the new array. - Deallocates the old bucket pointer table.
The Latency Spike Trap: Rehashing is an O(N) operation. In real-time trading engines or 60 FPS game loops, an unexpected rehash halts execution for milliseconds.
- The Cure: Call
m.reserve(expected_count)upfront. This sets enough bucket capacity so the table never rehashes during your workload.
std::unordered_map<int, int> m;
m.max_load_factor(0.75f); // Rehash earlier to maintain shorter collision chains
// Pre-allocate buckets for 100,000 items upfront:
m.reserve(100000); // Sets bucket_count such that 100,000 / bucket_count <= max_load_factor
// Guaranteed ZERO rehashes for the next 100,000 insertions!Always call reserve(N) before bulk-inserting into an unordered container to eliminate O(N) rehash latency spikes.
The O(N) Hash Collision Worst-Case & HashDoS Attacks
The O(N) Hash Collision Worst-Case & HashDoS Attacks
Hash tables are only average-case O(1). When keys collide, performance collapses to a linear crawl:
- The Worst Case (O(N) Degeneration): If N keys land in the same bucket, lookups must walk an N-node linked list calling
operator==at every node, degradingfind()to O(N). - The O(N^2) Insertion Freeze: Inserting N colliding keys forces the container to traverse the existing chain on every insertion to verify uniqueness, exploding total insertion time to O(N^2).
- The HashDoS Threat: Because standard library
std::hashimplementations are deterministic and unseeded (e.g.std::hash<int>{}(x) == x), attackers can craft inputs that all hash to the same bucket, stalling servers with 100% CPU usage. - The Defense: Use high-entropy bit mixers (like SplitMix64) or keyed randomized hashes (like SipHash) for untrusted user inputs.
struct BadHash {
// Pathological hasher: guarantees all keys collide into bucket 0!
std::size_t operator()(int) const noexcept { return 0; }
};
std::unordered_map<int, int, BadHash> dos_table;
for (int i = 0; i < 10000; ++i) dos_table[i] = i; // Takes seconds instead of microseconds!Use high-entropy bit mixers (like SplitMix64) and avoid predictable linear hashes for untrusted external inputs.
Custom Structs as Keys: Hash Functor & operator== Requirements
Custom Structs as Keys: Hash Functor & operator== Requirements
To use a custom struct as a key in std::unordered_map, you must provide 2 distinct tools:
- Equality (
operator==): Resolves collisions inside a bucket to determine if two keys are truly identical. - Hash Functor: Computes a 64-bit
std::size_tfrom the object's fields.
The XOR Hash Disaster:
Never combine multi-field hashes using plain XOR (h1 ^ h2):
- Symmetry bug:
Point{1, 2}andPoint{2, 1}yield the exact same hash! - Cancellation bug: Any diagonal point where
x == yevaluates to0, collapsing thousands of points into bucket 0.
The Production Fix (Golden Ratio Mixer): Use the standard 64-bit bit-mixing formula ($2^{64} / \phi \approx 0x9e3779b9$): $$seed \oplus= hash(v) + \mathtt{0x9e3779b9} + (seed \ll 6) + (seed \gg 2)$$ This scrambles bits evenly across all 64 bits and prevents symmetrical clustering.
struct Point {
int x, y;
bool operator==(const Point& o) const noexcept = default; // C++20
};
struct PointHash {
std::size_t operator()(const Point& p) const noexcept {
std::size_t seed = 0;
auto combine = [](std::size_t& s, int v) {
s ^= std::hash<int>{}(v) + 0x9e3779b9 + (s << 6) + (s >> 2);
};
combine(seed, p.x);
combine(seed, p.y);
return seed;
}
};
std::unordered_map<Point, std::string, PointHash> map;Never simply XOR multi-field hashes; use the golden ratio hash_combine formula with operator== to avoid catastrophic diagonal collisions.
std::unordered_map vs std::map Architectural Trade-Offs
std::unordered_map vs std::map Architectural Trade-Offs
Deciding between std::unordered_map and std::map comes down to 3 architectural questions:
- Ordering vs Point Lookups: Do you need range queries (
lower_bound) or sorted traversal? Usestd::map. For single-key point lookups, usestd::unordered_map. - Latency Guarantees: Does your system tolerate occasional O(N) rehash spikes or worst-case collision attacks? If strict bounded latency is required,
std::mapguarantees O(log N) worst-case. - Memory Footprint: Both containers suffer from node overhead (32 bytes per node for
std::map, 16–24 bytes per node + bucket table forstd::unordered_map).
| Feature | std::unordered_map | std::map |
|---|---|---|
| Underlying Data Structure | Bucket Array + Singly Linked Lists | Self-Balancing Red-Black Tree |
| Average Time Complexity | O(1) search, insert, delete | O(log N) search, insert, delete |
| Worst-Case Time Complexity | O(N) (hash collision / DoS) | Guaranteed O(log N) strict bound |
| Element Ordering | Arbitrary / unpredictable | Strictly sorted by key |
| Range Queries | Unsupported (requires O(N) full scan) | O(log N) via lower_bound/upper_bound |
| Memory Allocation | Contiguous bucket array + isolated nodes | 1 node per element (32B overhead) |
| Cache Locality | Poor (bucket pointer + node hop) | Poor (pointer chasing through nodes) |
// Choose std::unordered_map for fast single-point lookups with known bounds:
std::unordered_map<std::string, int> fast_id_table;
fast_id_table.reserve(10000);
// Choose std::map when order, range queries, or guaranteed worst-case bounds matter:
std::map<int, Order> order_book_by_price;Use std::unordered_map for O(1) single-key lookup; use std::map when you need sorted traversal, range queries, or guaranteed worst-case latency.
Unlock Live Implementation & Interview Scenarios
The C++23 production code, live coding steps, scenario twist solutions, and common UB traps are part of Brute2Best Pro. Module 1 is completely free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.