Implement Your Own Hash Map (MyHashMap<K, V>)
In modern C++, we never guess what the compiler does. We look directly at byte offsets, CPU registers, and object ownership lifetimes.
The C++ standard requires that references and pointers to elements in std::unordered_map remain valid across rehashing and insertions (iterator invalidation only happens on rehash, but references to elements are never invalidated). Open Addressing stores elements directly in a contiguous vector, so rehashing or insertion reallocations would invalidate all references and pointers to stored values.
In standard Linear Probing, new keys probe until they find an empty/tombstone slot, causing 'unlucky' keys to suffer long probe sequences. In Robin Hood Hashing, each key tracks its probe distance (age). When inserting a key whose current probe count exceeds the resident key's probe count, the algorithm steals from the rich and gives to the poor: it swaps the keys and continues inserting the resident key. This dramatically lowers the variance of lookup times.
When capacity $M = 2^k$, the expensive modulo operator hash % M can be replaced with a single CPU instruction bitwise AND: hash & (M - 1). The security drawback is that it only inspects the lowest k bits of the hash code. If keys share identical low-order bits, they all collide in the same buckets, enabling HashDoS algorithmic attacks unless a randomized hash seed (like SipHash) is used.
Interviewer's lens
Implementing a hash map live on the whiteboard or in an IDE is the ultimate test of whether a candidate understands hashing mechanics, collision resolution strategies, and CPU cache realities. Weak candidates treat std::unordered_map like magic, get tangled in bucket index modulo arithmetic, or write an open-addressing delete method that sets slots to Empty—instantly corrupting future lookups for colliding keys. Senior candidates immediately compare Separate Chaining versus Open Addressing with Linear Probing, calculate the exact load factor threshold (0.75) for geometric 2× rehashing, and demonstrate how Tombstones preserve probe chains while permitting slot reuse.
Under the hood & memory layout
At its core, a hash map maps arbitrary keys into fixed table indices via index = Hash{}(key) % bucket_count. In Separate Chaining (the default model of std::unordered_map), the table consists of an array of bucket heads, each pointing to a linked list of key-value nodes. When collisions occur, elements chain together in O(K) lookup time (where K is chain length). When load_factor = size / buckets exceeds 0.75, an amortized O(N) rehash(2 * bucket_count) allocates a new array, recomputes bucket indices, and transfers nodes. In Open Addressing (Linear Probing), all entries reside in a single contiguous buffer (std::vector<Slot>). This delivers massive CPU cache prefetching benefits because adjacent slots lie in the same 64-byte L1 cache line. However, deleting an entry requires a tri-state slot flag (Empty, Occupied, Tombstone): marking an erased slot Empty prematurely breaks linear probe chains for subsequent keys, whereas marking it Tombstone keeps the search path intact while allowing future insertions to reclaim the slot.
Vector of bucket list heads (std::vector<std::list<Entry>>). Incurs pointer indirection and node allocation overhead, but iterators and pointers to elements remain valid across rehashes.
Flat array of Slot { SlotState state; K key; V value; }. Maximizes hardware L1/L2 cache spatial locality by avoiding pointer chasing, but primary clustering requires low load factors (<= 0.70).
The mathematical equilibrium between memory usage and collision probability. At load factor 0.75, expected probe length in linear probing is ~2.5, preserving average O(1) operations.
Distinguishes 'never occupied' (Empty) from 'previously occupied' (Tombstone). Search stops only on Empty, guaranteeing lookups probe past deleted slots without early false negatives.
Core concepts & syntax traps
Separate Chaining: Bucket Modulo, Collision Lists & Amortized O(1)
Separate Chaining: Bucket Modulo, Collision Lists & Amortized O(1)
In Separate Chaining, the table maintains an array of M buckets. When inserting a key k, we compute idx = Hash{}(k) % M. If another key has already mapped to idx, we append (k, v) to the bucket's collision list. A lookup simply traverses buckets_[idx] and compares keys using KeyEqual{}.
While worst-case lookup degenerates to O(N) when all keys hash to the same bucket (a hash collision denial-of-service attack), a uniform distribution produces average chain lengths of $\alpha = N / M (the load factor). Keeping \alpha ≤ 0.75$ guarantees average lookup time of O(1 + \alpha) \approx O(1).
std::size_t idx = hasher_(key) % buckets_.size();
for (auto& entry : buckets_[idx]) {
if (equal_(entry.key, key)) {
entry.value = value; // Key exists: update value
return;
}
}
buckets_[idx].push_back(Entry{key, value}); // Insert new key
++size_;Separate Chaining isolates collisions into small independent lists, providing simple and robust collision handling.
Geometric Resizing & The Amortized Cost of rehash(2 * N)
Geometric Resizing & The Amortized Cost of rehash(2 * N)
As elements accumulate, the load factor rises and collision chains lengthen. When (size_ + 1) / buckets_.size() > 0.75, we trigger rehash(buckets_.size() * 2).
A critical trap in implementing rehash is attempting to copy bucket lists directly: because the modulo divisor has doubled from M to 2M, every element's bucket index changes! We must allocate the new bucket array and recompute hasher_(key) % new_capacity for every existing node. Because the capacity doubles geometrically (2×), each element is copied O(1) times on average across all insertions, yielding amortized O(1) insertion cost.
void rehash(std::size_t new_capacity) {
std::vector<std::list<Entry>> new_buckets(new_capacity);
for (auto& bucket : buckets_) {
for (auto& entry : bucket) {
// Recompute index with new capacity!
std::size_t idx = hasher_(entry.key) % new_capacity;
new_buckets[idx].push_back(std::move(entry));
}
}
buckets_ = std::move(new_buckets);
}Always recompute bucket indices against the new capacity during rehash; geometric 2x growth guarantees amortized O(1).
Open Addressing with Linear Probing: Cache Locality vs Primary Clustering
Open Addressing with Linear Probing: Cache Locality vs Primary Clustering
Instead of scattering heap nodes across memory, Open Addressing stores all keys directly in a contiguous std::vector<Slot>. If slot hash(k) % M is occupied, Linear Probing checks (idx + 1) % M, (idx + 2) % M, and so on.
Because adjacent vector elements share the same 64-byte CPU cache lines, sequential probing produces virtually zero cache misses compared to pointer-chasing in linked lists. However, open addressing suffers from primary clustering: contiguous runs of occupied slots merge into giant blocks, degrading probe lengths as the load factor approaches 1.0.
std::size_t start_idx = hasher_(key) % slots_.size();
for (std::size_t step = 0; step < slots_.size(); ++step) {
std::size_t idx = (start_idx + step) % slots_.size();
if (slots_[idx].state == SlotState::Empty) {
// Unoccupied slot found; stop searching
break;
}
}Linear probing offers unmatched hardware cache locality but requires keeping load factor below 0.70 to prevent clustering.
The Tombstone Deletion Trap: Why Setting Empty Corrupts Lookups
The Tombstone Deletion Trap: Why Setting Empty Corrupts Lookups
In linear probing, a lookup stops probing the instant it encounters an Empty slot, because any key inserted into this table would have taken that empty slot rather than probing beyond it.
Now consider keys A, B, and C that all hash to slot 2. A occupies slot 2, B occupies slot 3, and C occupies slot 4. If we delete B by resetting slot 3 to Empty, a future lookup for C will start at slot 2, probe slot 3, observe Empty, and stop—falsely reporting that C does not exist!
To solve this, deletion must mark slot 3 as Tombstone (Deleted). A lookup treats Tombstone as a signal to keep probing, while an insertion can reclaim the Tombstone slot to store new data.
// CORRECT ERASE: mark as Tombstone, NOT Empty
if (slot.state == SlotState::Occupied && slot.key == key) {
slot.state = SlotState::Tombstone;
slot.key = K{};
slot.value = V{};
--size_;
return true;
}Never mark erased slots as Empty in open addressing; use Tombstone to preserve subsequent probe chains.
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.