Load Factor and Resizing

The Load Factor

The load factor $\alpha = n/m$ measures how full a hash table is, where $n$ is the number of stored pairs and $m$ is the table size (number of slots).

As $\alpha$ increases:

• For chaining: average chain length grows, so search and insert expected time grows as $O(1 + \alpha)$.
• For open addressing: the probability of finding an occupied slot increases sharply, and the expected number of probes grows as $\frac{1}{1-\alpha}$ (unsuccessful search) or $\frac{1}{\alpha}\ln\frac{1}{1-\alpha}$ (successful search).

Why Resizing Is Necessary

A hash table with fixed capacity $m$ will eventually become overloaded if $n$ grows. Without resizing:

• Chaining: chain lengths grow linearly with $n$, degrading to $O(n)$ per operation.
• Open addressing: the table fills completely, and insertions fail (or probe sequences become impractically long before that).

Resizing is the operation of creating a new, larger table and rehashing all existing keys into it.

Resizing Strategy

When the load factor exceeds a threshold, double the table size (or increase to the next suitable prime):

1. Allocate a new table of size $m' \approx 2m$.
2. For each key in the old table, compute $h'(k) \bmod m'$ and insert into the new table.
3. Replace the old table with the new one.

Thresholds: typically $0.75$ for chaining (some implementations use $1.0$) and $0.5$ for open addressing (the expected probe count at $\alpha = 0.5$ is only 2 for unsuccessful search).

Amortised Analysis of Resizing

A single resize costs $\Theta(n)$ because every key must be rehashed. If this happened on every insert, the insert cost would be $\Theta(n)$, defeating the purpose.

However, resizing happens infrequently. If the table doubles each time:

• After $m$ inserts (from size $m/2$ to $m$), one resize costs $\Theta(m)$.
• The $m/2$ inserts since the last resize each get charged an amortised $\Theta(1)$ for the resize cost, plus their own $\Theta(1)$ insert cost.

This is identical to the amortised analysis of dynamic arrays: the total cost of $n$ inserts starting from an empty table is $\Theta(n)$, so the amortised cost per insert is $\Theta(1)$.

Downsizing

If many deletions reduce $n$ significantly (e.g. $\alpha < 0.25$), the table can be downsized to reclaim memory. The same amortised argument applies: periodic downsizing adds $\Theta(1)$ amortised cost per deletion.

Avoid aggressive downsizing (e.g. at $\alpha = 0.5$), which could cause thrashing: a sequence of insert-delete-insert oscillating around the threshold, triggering repeated $O(n)$ resizes.

Example: Resizing in Practice

Start with $m = 4$, threshold $= 0.75$.

Insert 1: n=1, α=0.25, table=[1,_,_,_]
Insert 2: n=2, α=0.50, table=[1,2,_,_]
Insert 3: n=3, α=0.75, table=[1,2,3,_]
Insert 4: n=4, α=1.00 > 0.75 → RESIZE to m=8
           Rehash all 4 existing keys into new table.
           Total cost: Θ(4) for resize + Θ(1) for insert 4.

After resize, $\alpha = 4/8 = 0.50$, well within the threshold.

Performance of Open Addressing with Resizing

With open addressing, tombstones also consume slots. When the fraction of tombstones becomes large, searches probe through many dead entries. A rehash into a same-size (or larger) table clears tombstones and restores performance. Maintain $n_k$ (live keys) and $n_m$ (tombstones); trigger rehash when $n_k + n_m$ exceeds threshold.

Summary

Quantity	Meaning
$\alpha = n/m$	Load factor
Chaining threshold	Typically $0.75$—$1.0$
Open addressing threshold	Typically $0.5$
Resize cost	$\Theta(n)$ (rehash all keys)
Amortised insert cost	$\Theta(1)$ (same analysis as dynamic arrays)
Resize trigger	$\alpha$ exceeds threshold (or too many tombstones)
Downsizing	Reclaim memory when $\alpha$ becomes very small