Target Duration: 2–4 minutes (~300–450 spoken words)
Focus: Pointwise verbal delivery covering fixed-size hash table slots, power-of-two masking, load factor triggers, dual-table incremental migration (k_rehashing_work = 128), and double-pointer deletion mechanics.
Opening & Scope:
"In standard hash tables like std::unordered_map, growing the table requires a 'stop-the-world' rehashing step where all entries are reallocated and reinserted at once. In a low-latency database with millions of keys, this causes multi-millisecond pauses. To eliminate this, I engineered a dual-table progressive rehashing engine called HMap."
Step 1: Power-of-Two Masking and Separate Chaining:
"First, the underlying hash table HTab allocates an array of slot pointers whose capacity is strictly a power of two, configured in h_init() (hashtable.cpp:7-13) and defined in struct HTab (hashtable.h:14-18). This allows the bucket index to be calculated using a lightning-fast bitwise AND (hcode & mask) instead of an expensive integer modulo instruction. Hash collisions are resolved using separate chaining through intrusive singly-linked HNode structures."
Step 2: Dual-Table Architecture (newer and older):
"Second, struct HMap (hashtable.h:22-27) maintains two distinct tables: newer and older, along with a cursor called migrate_pos. In normal operation without resizing, older.tab is null and all operations hit newer. The database computes 64-bit hashes using the FNV-1a hashing algorithm, which provides strong bit dispersion with negligible CPU cost."
Step 3: Load Factor Triggering Dynamic Growth:
"Third, during insertions, if hmap->newer.size exceeds its capacity multiplied by k_max_load_factor (set to 8 in hashtable.cpp:48), and no rehash is currently active, hm_trigger_rehashing() (hashtable.cpp:72-78) initiates migration. It swaps newer into older, allocates a fresh newer table with double the slot capacity, and resets migrate_pos to 0."
Step 4: Bounded Constant-Work Migration (hm_help_rehashing):
"Fourth, rather than migrating all keys immediately, every subsequent lookup, insertion, or deletion calls hm_help_rehashing() (hashtable.cpp:52-70). This function migrates a strictly bounded batch of up to 128 non-empty slots (k_rehashing_work = 128 in hashtable.cpp:49) from older to newer. It moves entire nodes by unlinking them from older and inserting them into newer without allocating new memory. Once older.size drops to zero, the old slot array is freed. This distributes the resize cost evenly, guaranteeing strict $O(1)$ amortized latency."
Step 5: Double-Pointer Indirect Lookup & Deletion:
"Finally, for node search and deletion, h_lookup() (hashtable.cpp:32-38) returns a pointer-to-pointer (HNode **). This pointer represents the incoming memory location pointing to the target—which could be a slot in the table array or the next pointer of a preceding node. In h_detach() (hashtable.cpp:40-46), we update *from = node->next in a single assignment. This completely eliminates edge-case checks for bucket heads versus chained list nodes."
| Step | What Was Done | How It Works | Why This Mechanism / Order | Code Reference |
|---|---|---|---|---|
| 1. Fast Indexing | Used power-of-two table capacity | Computes slot index as pos = hcode & mask where mask = capacity - 1. |
Bitwise AND executes in 1 clock cycle; avoids multi-cycle integer division. | hashtable.h:14-18hashtable.cpp:7-13 |
| 2. Dual-Table Model | Structured HMap with newer and older |
Directs queries to both tables while migration is active. | Allows the server to remain fully operational while migrating keys in the background. | hashtable.h:22-27 |
| 3. Rehash Trigger | Checked load_factor >= 8 on insert |
Promotes newer to older; allocates doubled newer table. |
Prevents excessive chain lengths that would degrade lookup performance to $O(N)$. | hashtable.cpp:48, 72-78 |
| 4. Incremental Step | Migrated $\le 128$ slots per operation | Moves linked nodes from older to newer on every user query. |
Bounds execution time per request, completely eliminating stop-the-world latency spikes. | hashtable.cpp:49, 52-70 |
| 5. Pointer-to-Pointer | Returned HNode ** in h_lookup |
Dereferences incoming address to splice node out: *from = node->next. |
Achieves branchless, symmetric deletion whether node is bucket head or chained interior. | hashtable.cpp:32-46 |
std::unordered_map?Answer:
std::unordered_mapperforms a synchronous "stop-the-world" rehash when its load factor threshold is breached. For a database holding 5 million keys, allocating a doubled bucket array and re-inserting all 5 million items freezes the event loop for 50–150 milliseconds, violating low-latency SLOs and causing TCP client timeouts. OurHMapsplits the work across client requests, migrating at most 128 non-empty buckets per query (hm_help_rehashing), bounding each step to sub-microsecond latency and achieving smooth $O(1)$ amortized cost.
Answer: During migration, keys exist across both
newerandolder. If queries searched only one table, keys would appear missing.hm_lookupsearchesnewerfirst; if absent, it checksolder. For insertions, new keys are always inserted intonewer, ensuringoldermonotonically drains and never grows. For deletions,hm_deletesearches both tables and uses double-pointer unlinking (h_detach). Most importantly, every operation runs a boundedhm_help_rehashingstep before searching, guaranteeing forward progress on migration even under heavy read loads.
h_lookup return a double-pointer (HNode **) and how does it prevent pointer-chasing bugs?Answer: In separate chaining with singly-linked lists, unlinking a node requires modifying the pointer that addresses it. That pointer is either a slot entry in the bucket array (
&htab->tab[pos]) or thenextmember of a predecessor node (&prev->next). ReturningHNode **fromprovides the exact memory location of that incoming pointer. Detaching the node is a branchless, single instruction:*from = (*from)->next. This eliminates conditional branches for head-of-bucket vs interior nodes, preventing dangling pointer corruptions and redundant traversals.