Incremental Rehashing: Spreading a Resize Across Operations

Geometric growth makes insertion amortized constant time by charging the occasional full rehash against the many cheap insertions that preceded it. The accounting is correct and the pause is still real. A table with ten million entries that doubles its bucket array must reinsert ten million keys in a single operation, and any request that arrives during that operation waits. For a batch job the pause is irrelevant; for a server holding a latency budget it is the largest cost in the system.

Incremental rehashing removes the pause without changing the asymptotic total work. The idea is to keep both the old and the new bucket array alive during a migration and move a bounded number of entries per operation, so that no single call does more than constant extra work.

Two arrays, one cursor

The structure holds two table pointers, old and new, plus an integer cursor that records how far the migration has progressed. While old is non-null the table is in a rehashing state; when the cursor passes the last bucket of old, the old array is freed and the table returns to its normal state.

Growth is triggered when the load factor crosses its threshold. The new array is allocated at the larger size and left empty, and the cursor is set to zero. Nothing is moved at that moment. The insertion that triggered the growth proceeds into the new array, and the migration begins on the next operation.

Each subsequent lookup or insertion performs a fixed amount of migration work, typically one bucket or a small constant number of them. Migrating a bucket means walking the chain described in separate chaining (or the probe cluster of an open-addressed table) anchored there in the old array and inserting each entry into the new array using the new modulus. The cursor advances by one bucket, and buckets already migrated are marked so they are never visited twice.

The choice of how much to migrate per operation sets the migration rate. If one bucket is migrated per operation, the migration completes after m_old operations, and during that window both arrays are live. The table must therefore be able to absorb m_old further insertions without needing another resize, which constrains the growth factor: doubling from m to 2m leaves room for m new entries at the same load factor, exactly the window the migration needs.

Lookup while the table is split

A lookup must consult both arrays, and the order matters for correctness only in that a key present in both must resolve to the same value. In practice the new array is checked first, because keys migrate into it and a recently inserted key is there.

struct entry *dict_find(struct dict *d, const char *key)
{
    if (d->rehash_idx >= 0) {                  /* migration in progress */
        dict_rehash_step(d);                   /* bounded work: one bucket */
    }

    struct entry *e = bucket_find(d->new, key);
    if (e)
        return e;

    /* A non-null old table may be finished by the step above, so re-read the flag.
       The key is either in old, or it never existed; putting a migrated entry
       there is the rehash step's job, not the lookup's. */
    if (d->rehash_idx >= 0)
        e = bucket_find(d->old, key);
    return e;
}

The ordering is a correctness requirement rather than an optimization. dict_rehash_step can complete the migration and free the old array; a lookup that consulted old after the step without re-checking the flag would follow a dangling pointer. Checking new first also lets the lookup skip the old array entirely once the migration has finished, so the cost during migration is at most twice the normal cost and closer to once for keys that have already moved.

Deletion is the operation with the sharpest edge. A key may be in the old array, the new array, or neither. Removing it from whichever array holds it is safe and does not require migrating the bucket. What must not happen is a delete that frees an entry while a migration step still holds a pointer to it, which is why the migration step and the delete must be ordered within the same critical section in any implementation that is not lock-free.

Why the migration must be driven by every operation, not a timer

A background thread that migrates the table would also remove the pause, and it is the wrong design for most libraries because it requires synchronization on every access. Driving the migration from the operations themselves keeps the table single-threaded from the caller’s point of view: no locks, no atomics, no memory ordering questions. The work is charged to whoever touches the table next, which is fair in the amortized sense and requires no scheduler.

The consequence is that a table which stops receiving operations also stops migrating, and stays split indefinitely. That is usually harmless: a split table is correct, only slower by the bounded factor above. Implementations that care can expose a maintenance call that finishes the migration, or can migrate the remainder during iteration, which already walks every entry.

Iteration over a split table is the operation most likely to be implemented incorrectly. A naive iterator walks the old array and the new array separately and yields each key once, but a key that migrates during the iteration could be seen twice or missed. The standard fix is to complete the migration at the start of iteration, or to snapshot the entry set, or to forbid mutation during iteration as the language’s collection contract allows. The C++ standard’s iterator invalidation rules for unordered containers exist precisely because an interleaved rehash can invalidate a position.

Growth factors and the memory plateau

Doubling is the common choice because it charges a bounded number of additional moves per live entry. An entry is moved once at every doubling it survives, and the sizes it survives grow geometrically, so the total work to reach n entries stays proportional to n rather than n log n; the constant is larger than a single copy but does not depend on the final size. A growth factor of 1.5 lowers peak memory, since the new array is only half again as large as the old one, at the price of more doublings over the table’s life and therefore a larger total migration.

Small factors have a second cost that is easy to miss. The migration window is m_new - m_old = m_old(g-1) insertions, which for g = 1.5 is only half the old table, so a table that receives a burst of insertions can exhaust the window before the migration finishes. Most implementations avoid the problem by refusing to grow while a migration is in progress and letting the load factor rise temporarily.

Shrinking needs a separate policy with hysteresis. Growing at α = 0.75 and shrinking at α = 0.25 means a table that oscillates around a threshold does not thrash, because the two thresholds are far apart. A single threshold, or shrinking at the same load factor that triggers growth, produces repeated resizes on alternating insert and delete, each one costing a full migration. The hysteresis band is what prevents that.

When the pause cannot be amortized away

Incremental rehashing does not eliminate the total work; it redistributes it. That is enough for a server, and it is not enough for a real-time system with a hard deadline per operation, because even the bounded per-operation migration adds work to an operation that may already be at its limit.

The alternative for those systems is to pre-size the table to the known maximum and never resize, or to use a structure with a different growth strategy entirely, such as a chained table whose buckets are allocated in blocks. Pre-sizing is exact when the key set is known in advance and impossible when it is not, which is the usual case.

A second alternative is to rehash in place using a scheme that does not need a second array, which saves the peak memory of holding both. The migration still has to visit every entry, so the work is unchanged; only the space is saved. Implementations that hold very large tables, where doubling would temporarily require fifty percent more memory than the table itself, choose this when they can.

The mechanism is worth understanding even for code that never implements it, because the same two-array pattern appears in any structure that must change its layout without a pause: dynamic arrays that grow in place by remapping, B-trees that split a node, and log-structured indexes that compact in the background. The pattern is always the same three parts: a cursor, a rule for consulting both layouts, and a bound on how much work any single operation may do.