stl · advanced

Open Addressing — Cache-Friendly Hash Maps

std::unordered_map uses separate chaining — a bucket array whose buckets point to linked lists of heap-allocated nodes — so lookups chase pointers across the heap (cache-unfriendly) with an allocation per element. Open addressing instead stores all entries directly in a single contiguous array and, on a collision, probes nearby slots in that same array, eliminating per-node allocation and giving excellent cache locality, which is why high-performance maps such as abseil's flat_hash_map and folly's F14 use it. The probe sequence can be linear (h, h+1, h+2 — most cache-friendly but prone to clustering), quadratic, or double hashing (which spread entries to reduce clustering); deletions cannot simply empty a slot because that would break probe chains, so they mark a tombstone, and the table must keep its load factor below roughly 0.7 and rehash (grow and reinsert) beyond it, since performance degrades sharply as it fills (Robin Hood hashing evens out probe lengths to cut worst-case variance). The decisive trade-off: open addressing is faster for small, trivially-copyable keys and high-throughput lookups, but it degrades near full, requires tombstones, and provides no reference or iterator stability because a rehash physically moves elements — whereas std::unordered_map guarantees a node's address stays stable across rehashes. Choose open addressing for raw speed and chaining when you need stable references, very high load factors, or large stored values.

The code

// std::unordered_map = CHAINING: array of buckets -> linked nodes
//   each element is a separate heap node -> pointer chasing (cache miss)

// OPEN ADDRESSING: all entries live in ONE contiguous array
//   collision? probe the next slot(s) in the SAME array
//   linear:    h, h+1, h+2, ...        (cache-friendly)
//   quadratic: h, h+1, h+4, h+9, ...   (less clustering)
//   robin hood / swiss table (abseil flat_hash_map, folly F14)

What this lesson walks through

1. 01Chaining vs open addressing
2. 02Probing, load factor, tombstones
3. 03Gotcha — deletion needs tombstones; watch the load factor
4. 04Trade-offs — and unordered_map's guarantee

std::unordered_map uses separate chaining: a bucket array where each bucket points to a linked list of heap-allocated nodes. Lookups chase pointers across the heap — cache-unfriendly, with an allocation per element. Open addressing stores all entries directly in one contiguous array; on a collision it probes nearby slots in that same array. No per-node allocation and excellent cache locality, which is why high-performance maps (abseil flat_hash_map, folly F14) use it.