 Hash table resizing

Changing the number of hash buckets and reassigning stored records using the new bucket-index hash function. Amortized analysis of rebuilding and expected value bounds for subsequent lookup address different costs.

Rebuild the balanced example from load factor of a hash table with $m^{\prime }=16$ while keeping exactly the same twelve records. Under $h_m(k)=k\mathrm{mod}m$, keys $0,\dots ,7$ retain their indices, whereas keys $8,9,10,11$ move from hash buckets $0,1,2,3$ to hash buckets $8,9,10,11$. The new chain lengths are twelve ones followed by four zeros; ${\alpha }^{\prime }=12/16=3/4$. Copying the old eight chain heads and adding eight empty heads would leave those four moved keys unreachable by the new lookup rule.

For a short algorithm correctness outline, allocate the new array, visit every old record once, compute its new bucket index, and link it into that hash bucket. At every step, each transferred record is stored exactly once at the index prescribed by the new hash function. Finishing the visit therefore preserves every key-value association and makes the new lookup rule valid. Direct transfer can skip duplicate searches because the old one-value-per-key map already established distinct equivalence classes; rebuilding is not twelve new user insertions.

Under constant-cost hashing, linking and slot initialization, separate chaining rebuilding takes $O(n+m+m^{\prime })$ time complexity: initialize $m^{\prime }$ new heads, examine $m$ old heads, and transfer $n$ records. For doubling, $m^{\prime }=2m$, this is $O(n+m)$ in Big O notation. It is $O(n)$ when the resize policy makes $m$ proportional to $n$, but an enormous mostly empty old array can make scanning its heads dominate. Growing capacity can lower $\alpha$ without shortening a particular chain: the concentrated keys $0,16,\dots ,176$ all remain in hash bucket $0$ after growth from eight to sixteen.

For an insertion-only sequence starting empty, choose initial capacity $m_0=8$ and double before a genuinely new key would make $n>m$. The first three growths occur before inserting records $9,17,33$ and transfer $8,16,32$ existing records. If $N=33$ distinct records are inserted, the transfer count is $8+16+32=56$. More generally, the transferred old capacities form a geometric series; if the last is $M<N$, their sum is $2M-m_0<2N$. Initializing and scanning these geometrically growing arrays also costs $O(N)$ in total, giving $O(1)$ amortized rebuilding overhead per insertion. A triggering insertion still pays for its whole rebuild.^[ref]

The illustrative twelve-record resize above is an explicitly requested rebuild, not a growth triggered by this threshold policy. Checking for an equal key before growing also prevents a value replacement from triggering unnecessary growth. To combine resizing overhead with expected constant insertion time complexity, separately impose the collision and constant-cost assumptions in load factor of a hash table. Amortized analysis distributes rebuilding costs over operations; it does not randomize a poor hash function or bound a single operation's latency. With deletions, separate the grow and shrink thresholds; for example, growing when full and halving at one-quarter live occupancy leaves room for many operations between opposite rebuilds.^[ref]

// Target: computer-science.bigb