A hash table's famous average O(1) performance isn't automatic — it depends on keeping the table from getting too crowded. The metric that tracks this is called the load factor, and the mechanism that keeps it in check is called rehashing.

What Load Factor Measures

Load factor is simply the ratio of stored entries to the number of available buckets:

load_factor = number_of_entries / number_of_buckets

# Example: 12 entries stored across 16 buckets
load_factor = 12 / 16
print(load_factor)

Output:

0.75

A load factor of 0.75 means the table is 75% full on average. Most hash table implementations target a maximum load factor somewhere between 0.6 and 0.75 before taking action.

Why a High Load Factor Hurts Performance

As more entries pack into the same number of buckets, collisions become more frequent — with chaining, buckets grow longer linked lists to scan through; with open addressing, probe sequences get longer as free slots become scarce. In the extreme case where the load factor approaches or exceeds 1.0, average lookup time starts drifting from O(1) toward O(n) — the table has effectively degraded into a slow linear search.

Rehashing: Growing the Table

To prevent that degradation, a hash table monitors its load factor on every insert, and once it crosses the threshold, it rehashes: allocate a new, larger underlying array (commonly double the previous size), then reinsert every existing entry by re-running the hash function against the new, larger bucket count (since the index formula depends on the bucket count, every entry's index can change).

# Conceptual sketch of what happens during a resize
def rehash(old_buckets, new_size):
    new_buckets = [[] for _ in range(new_size)]
    for bucket in old_buckets:
        for key, value in bucket:
            new_index = hash(key) % new_size
            new_buckets[new_index].append((key, value))
    return new_buckets

# Doubling from 8 buckets to 16 lowers the load factor by half
old = [[("a", 1)], [], [("b", 2), ("c", 3)], [], [], [], [], []]
new = rehash(old, 16)
print(len(new))

Output:

16

Why This Is Still Considered O(1) Average

A single rehash is an expensive O(n) operation — every entry has to be touched. But because it only happens occasionally (each resize roughly doubles capacity, so resizes become exponentially less frequent as the table grows), the cost spreads out to an amortized O(1) per insert when averaged across all operations over time. This is the same amortized-cost reasoning behind why dynamic arrays can claim O(1) append despite occasionally needing to resize and copy everything.

In practice, you almost never write this resizing logic yourself — every mainstream language's built-in hash table (Python's dict, Java's HashMap, and so on) handles load factor monitoring and rehashing automatically behind the scenes.