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 load factor crosses an implementation-chosen threshold, a hash table allocates more capacity and relocates entries. That O(n) event is rare enough to preserve amortized O(1) insertion. The exact threshold and growth factor depend on the collision strategy and implementation; neither two-thirds nor exact doubling is a language contract.

Load factor influences collision work. Implementations preserve spare capacity and occasionally rebuild the table, yielding expected lookup and amortized insertion bounds without promising one universal threshold or growth factor.

Where the Threshold Sits

Chaining can operate above load factor 1 at the cost of longer chains, while open addressing needs empty slots to keep probes short. CPython's exact policy may change across versions. Remember the invariant—spare capacity controls expected probe length—not one magic fraction.

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 that adds ample spare capacity restores short expected probes.

Exercise

Suppose a teaching hash map 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

In this hypothetical doubling policy, growth to hold 1,000 keys takes logarithmically many resizes. The geometric series of rehash work is O(n), so insertion is amortized O(1). Real implementations choose their own thresholds and growth factors.

The Load Factor

The Fix: Grow and Rehash

Where the Threshold Sits

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0