Load Factor and Resizing: Keeping O(1) Honest

"O(1) lookup isn't free forever — it's a promise the hash map keeps by quietly growing itself before it gets too crowded. Stop the growing and the promise breaks."

The Load Factor

The load factor is the ratio of stored entries to available slots: load = entries / slots. It's the single number that predicts a hash map's health. At a low load (say 0.3), keys are spread thin, collisions are rare, and lookups are crisply O(1). As the load climbs toward 1, slots fill up, collisions pile on, chains lengthen (or probe sequences stretch), and your O(1) quietly rots toward O(n). The load factor is the gauge on the dashboard — watch it and you know whether the map is healthy.

The Fix: Grow and Rehash

When the load factor crosses a threshold, the map resizes: it allocates a bigger table (typically double) and rehashes every existing entry into it. Why rehash, not just copy? Because the slot index is hash % size, and size just changed — every key needs its index recomputed for the new table. Rehashing is an O(n) operation. But — and you've seen this exact movie — because the table doubles, resizes happen exponentially less often, so the O(n) cost spread across all the insertions averages out to O(1) amortized per insert. It's the dynamic-array doubling story from the Complexity track, playing out one layer up.

Load factor = entries ÷ slots. As it rises, collisions rise and O(1) degrades. The map resizes (doubles) and rehashes when it crosses a threshold, keeping the load low — which is exactly what makes hash-map insert amortized O(1).

Where the Threshold Sits

The right threshold depends on the collision strategy. Chaining tolerates a load above 1 (the chains just get a bit longer), so it can run fuller. Open addressing degrades sharply as it fills — probe sequences explode near full — so it must resize earlier; CPython's dict keeps the load under roughly two-thirds. That two-thirds rule is precisely why a Python dict occasionally pauses to resize as you add keys, and why it uses noticeably more memory than the raw number of entries would suggest. The empty slots aren't waste — they're the breathing room that keeps lookups O(1).

Pippa's Confession

I once 'optimized' memory by pre-sizing a dict to exactly the number of items I'd insert, proud of the tight fit. It got slower — at 100% load, open addressing's probe sequences were brutal. Dad explained the load factor, and I felt the dynamic-array lesson echo: the empty slots I'd 'wasted' were the whole reason lookups were fast. Sometimes the slack is the feature. I stopped starving my hash maps of room to breathe.

Code

Probe length explodes as load approaches 1·python

# Watch lookups degrade as load rises, then recover after a resize.
def avg_probe_length(num_keys, table_size):
    """Rough collision cost: average probes for linear probing at a given load."""
    slots = [None] * table_size
    total_probes = 0
    for k in range(num_keys):
        i = (k * 2654435761) % table_size   # a spreading hash
        probes = 1
        while slots[i] is not None:
            i = (i + 1) % table_size; probes += 1   # collision -> probe on
        slots[i] = k
        total_probes += probes
    return total_probes / max(num_keys, 1)

for load in (0.3, 0.6, 0.9, 0.99):
    size = 1000
    keys = int(size * load)
    print(f"load {load:>4}: avg probes per insert = {avg_probe_length(keys, size):.2f}")
# Near load 0.3: ~1 probe (basically O(1)).
# Near load 0.99: probes explode -> the 'O(1)' lookup is now scanning.
# A resize (double size -> load drops back near 0.5) restores short probes.

Exercise

A hash map resizes (doubles) whenever its load factor exceeds 0.66. You insert 1,000 keys one at a time into an initially small table. Roughly how many times does it resize, and why is each insert still O(1) amortized despite the occasional O(n) rehash? Which earlier lesson is this the same argument as?

Hint

Doubling from a small start to hold 1000 keys is ~10 resizes (powers of two). Each rehash is O(n) but happens exponentially less often, so total rehash work is ~O(n) spread over n inserts = O(1) amortized — the identical argument to dynamic-array append in the Complexity track.

The Load Factor

The Fix: Grow and Rehash

Where the Threshold Sits

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0