Load Factor and Rehash

The load factor is n / capacity. If it exceeds a threshold, the table reallocates (rehash): new capacity, redistribute entries.

Rehash is amortized $O(n)$, but keeps the expected bucket length small.

$$\alpha = n/m$$

Where used

Capacity planning for caches and maps: being too full means long chains and rehash pauses. In services, visible GC/latency phases occur when growing large maps.

Depth

The load factor is the ratio of stored entries to the number of table slots. As it increases, the local collections grow on average in chaining; in open addressing, free slots become harder to reach. Implementations therefore define a threshold for resizing.

After the increase, all entries must be re-sorted based on the new capacity. This is a single expensive operation, but it occurs only occasionally. Spread out over many insertions, the amortized costs remain low, provided the capacity grows geometrically.

Difficulty levels

1. Calculate the load factor from the number of entries and capacity.
2. Justify why simply copying to the same indices is wrong.
3. Explain the amortized costs of geometric growth.

Pitfalls

A stored table index is not a permanent property of a key. When the capacity changes, the index mapping usually changes as well. Increasing the capacity by just one slot at a time also leads to too many complete rebuilds.