Resizing and load factor

The load factor

The load factor of a hash table is the number of entries divided by the number of slots, usually written α (alpha). Eight entries in 16 slots is a load factor of 0.5; twelve entries in 16 slots is 0.75.

The load factor is the best single predictor of how fast a table is. The previous lesson showed why: with linear probing, a lookup for a missing key checks about 2.5 slots at α = 0.5 and about 50 at α = 0.9. Chaining degrades more gently, but its lists grow with α as well, since the average list holds α entries. Either way, a fuller table is a slower table.

So every hash table picks a maximum load factor and keeps itself below it:

The limits differ because the designs differ. Rust's table checks 16 slots at once with a single vector instruction, so it can tolerate longer probe sequences and run fuller. Java's chaining pays for list nodes either way, and Python keeps more room so that its probe sequences stay short.

Growing means moving everything

When an insert would push the table past its limit, the table allocates a new array, usually twice as large, and moves every entry into it. It can't simply copy the old array across: a key's slot depends on the capacity, so with a new capacity most keys belong somewhere else.

The trace above shows this with a 4-slot table holding "eve", "bob" and "amy" at a load factor of 0.75. After doubling to 8 slots, "eve" moves from slot 0 to slot 4, "bob" moves from slot 1 to slot 5, and "amy" still collides with "bob" and probes to slot 6. The new load factor is 3 / 8 = 0.375, and the old array is freed.

There is a neat pattern in those moves. Doubling the capacity adds one bit to the mask, from 3 (binary 11) to 7 (binary 111). So each key's new home slot is either its old home slot or its old home slot plus the old capacity, depending only on that one extra bit of its hash: "eve" went from 0 to 0 + 4, and "bob" from 1 to 1 + 4. Java's HashMap uses exactly this fact to split each old bucket into two new ones. It also stores each key's hash inside the entry, so that a resize never has to call hashCode() again.

Why inserts stay fast on average

A resize copies every entry, so the insert that triggers it is slow. For a table of a million entries, one insert moves a million entries. Doesn't that break the promise of constant-time inserts?

It doesn't, thanks to the doubling. Follow a table that starts with 8 slots and doubles whenever it fills. By the time it holds n entries, it has resized at 8, 16, 32 and so on up to n, so it has moved about 8 + 16 + 32 + … + n entries in total. That sum is less than 2n. Spread over the n inserts, it is fewer than two moves per insert: a constant. Averaging an occasional expensive step over many cheap ones like this is called amortized analysis, and the Expert level of this track covers it in depth.

The doubling is essential. If the table grew by a fixed amount instead, say 8 slots at a time, it would resize every few inserts and copy everything each time, and the average insert would cost O(n).

An amortized constant is still not a constant for every single insert. A program that cares about its worst case, such as a server answering requests, sees an occasional slow request whenever a large table resizes. Redis avoids this by resizing incrementally: it keeps the old and the new tables side by side and moves a few buckets on every operation until the old table is empty.

Shrinking and sizing up front

Most tables grow but never shrink on their own. Java's HashMap keeps its large array even after you remove almost everything from it; to give the memory back, you copy the remaining entries into a new map.

The other side of the coin is sizing a table up front. If you know a table will hold a million keys, say so when you create it. It will allocate a large enough array once, instead of resizing more than fifteen times on the way up:

Java   HashMap.newHashMap(1_000_000)    // Java 19 and later
Go     make(map[string]int, 1_000_000)
Rust   HashMap::with_capacity(1_000_000)
C++    table.reserve(1'000'000);

Check what the number means before you rely on it. In all four lines above it is the number of entries you expect, and the table works out how many slots that needs. Java's older constructor is a trap: new HashMap<>(1_000_000) takes a number of slots, so it creates 1,048,576 of them, passes its 0.75 limit at 786,432 entries, and resizes once anyway.

Resizing is the last piece of the structure itself. The final lesson of this module looks at the hash maps your language already gives you, and at the mistakes that make them misbehave.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Resizing and load factor from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

function two_sum_hash(nums, target):
    seen = empty_hash_map()
    for i from 0 to length(nums) - 1:
        need = target - nums[i]
        if need in seen:
            return (seen[need], i)
        seen[nums[i]] = i
    return (-1, -1)

#include <vector>
#include <unordered_map>
 
std::pair<int, int> twoSumHash(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> seen;
    seen.reserve(nums.size() * 2);
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        int need = target - nums[i];
        auto it = seen.find(need);
        if (it != seen.end()) return {it->second, i};
        seen[nums[i]] = i;
    }
    return {-1, -1};
}

import java.util.*;
 
public class HashSolver {
    public static int[] twoSumHash(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>(nums.length * 2);
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (seen.containsKey(need)) return new int[]{seen.get(need), i};
            seen.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }
}

def two_sum_hash(nums: list[int], target: int) -> tuple[int, int]:
    seen: dict[int, int] = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return seen[need], i
        seen[x] = i
    return -1, -1

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.