Hash Table And Rehashing Practice

An old key may be found in the old table, a new insert goes to the new table, and a missing key must be checked against both tables.

All lookups go to the new table first and never touch the old one, since the old table is read-only while rehashing.

Every key is checked in both tables and the two results merged, doubling the cost of all operations until rehashing ends.

Old keys are found through a forwarding pointer left behind in the old table after each entry migrates, the same trick virtual memory uses for relocated pages.

Incremental rehashing is both simpler and faster overall; the only cost it pays is temporary extra memory.

Incremental rehashing is more complex, but it spreads migration across many operations so one resize does not create a large latency spike.

It trades correctness for speed, accepting a small window where a key can be missed during the migration, a risk considered acceptable because resizes are rare events.

It avoids latency spikes by running the whole migration on a background thread, away from the event loop.

Inserts go to the old table so it remains authoritative, then migrate together with everything else.

Inserts go to whichever table the key's hash selects, keeping the load balanced between the two.

Inserts are buffered in a queue and applied once rehashing completes, so neither table changes mid-migration.

New inserts should go into the new table while rehashing continues, so the old table only drains.

The event loop owns the hash function, so the dictionary cannot compute bucket indexes without it.

Rehashing must pause the event loop entirely, so the connection exists to schedule that pause safely, ideally during a quiet period when few clients are connected.

Rehashing connects to the event loop because migration work must be budgeted around command latency and timer or operation-driven progress.

The connection is only for observability, letting the loop publish rehash progress metrics to monitoring.

Nothing goes wrong, because deletes that miss the new table fail fast and the caller simply retries after the rehash.

Deletes that check only the new table can leave old-table keys visible, duplicated, or undeleted until migration happens.

The new table becomes corrupted, because delete tombstones have nowhere to migrate when their bucket moves.

Memory leaks but lookups stay correct, since lookups never consult the old table either.