Load factor and resizing

Why does a hash map grow?

More entries in a fixed-size table usually mean more entries competing for the same buckets. Longer bucket lists make lookup slower. A growing hash map adds buckets so that it can continue spreading entries out.

Load factor describes how crowded a table is on average. It is the number of entries divided by the number of buckets: n / m. Six entries and eight buckets give 6 / 8 = 0.75. This does not mean every bucket is 75% full. In separate chaining, buckets can hold several pairs, so load factor can even exceed 1.

Resizing allocates a bigger bucket array and places every existing pair according to the new capacity. A runtime chooses when to resize. The number 0.75 is an example, not a rule every dictionary uses. Our teaching lab resizes only when you explicitly call resize.

How does it work?

1. Measure how many entries share the available buckets.

   Count n entries and m buckets. Compute n / m. As the average number of entries per bucket grows, expected comparisons usually grow too.

2. Create a larger array of empty buckets.

   For example, change the capacity from 8 to 16. Six entries now have load factor 6 / 16 = 0.375.

3. Recalculate a bucket for every stored pair.

   Use key % 16 instead of key % 8 in this model. Key 10 moves from bucket 2 to bucket 10. Key 18 stays at bucket 2. Reinsert both with their original values.

4. Use the new rule for all future operations.

   Lookup must now use the new capacity too. Copying entries into their old bucket positions would leave some keys unreachable.

Work through an example

Before resizing, eight buckets put both 10 → "Maya" and 18 → "Ravi" in bucket 2. Their load factor is 2 / 8 = 0.25. After resizing to sixteen buckets, 10 % 16 = 10 and 18 % 16 = 2. The two pairs no longer collide; the load factor is 2 / 16 = 0.125.

Notice that growth changes a bucket index, not a student ID. Student 10 is still key 10 and still maps to "Maya". Its pair now lives in bucket 10. To read this value, calculate the new bucket index.

Doubling capacity occasionally is more efficient than adding just one bucket after every insertion. Geometric growth leaves room for many future entries before the next rebuild. It does not fix a hash function that sends every key to the same bucket, however.

Time and space complexity

A resize must scan the old buckets, visit all n stored pairs, and allocate the new buckets. In the lab, each existing pair is placed directly into its new bucket: its key is already unique, so there is no need to search for a duplicate. The total work is O(n + old capacity + new capacity), including allocation and amortized list-appends. When both capacities are proportional to n, this is O(n).

With geometric growth and good hash distribution, expected insertion cost averaged across a sequence of inserts is O(1), or expected amortized O(1). One particular insertion that grows the table can still take O(n).

The table occupies O(n) space when capacity is proportional to n. During resizing, old and new arrays may exist together, using O(n) temporary space under the same capacity assumption.

Why it works

After resizing, every existing pair is placed using the new capacity, and lookup uses that capacity too. The set of keys and each key’s value stay the same. Only internal storage locations change.

Common mistakes

• Do not copy a pair into the old bucket number without recalculating it for the new capacity.
• A low load factor is an average. Several keys can still collide in one bucket.
• Do not promise every insertion is O(1): resizing is an occasional larger operation.

Chapter lab · Python implementation

The code below builds the same teaching table shown above: eight buckets, integer keys, and a list of pairs in each bucket. make_table creates the buckets; put inserts or updates; get finds a value; remove deletes one pair; resize moves pairs into a new table. This is separate chaining, one possible hash-table implementation. Its simple key % capacity rule makes collisions visible; Python’s real dict uses its own hashing and storage rules. This small table does not resize automatically. Run the assertions to see that two colliding keys stay separate and that updates do not create duplicates. The final two functions apply Python dictionaries to Two Sum and frequency counting.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def make_table(capacity=8):
    if capacity <= 0:
        raise ValueError("capacity must be positive")
    return [[] for _ in range(capacity)]


def put(table, key, value):
    bucket = table[key % len(table)]
    for position, (stored_key, stored_value) in enumerate(bucket):
        if stored_key == key:
            bucket[position] = (key, value)  # Update this key.
            return
    bucket.append((key, value))  # A new key, even if its bucket is used.


def get(table, key):
    bucket = table[key % len(table)]
    for stored_key, value in bucket:
        if stored_key == key:
            return value
    raise KeyError(key)  # No matching key in this bucket.


def remove(table, key):
    bucket = table[key % len(table)]
    for position, (stored_key, value) in enumerate(bucket):
        if stored_key == key:
            bucket.pop(position)
            return value
    raise KeyError(key)


def resize(table, capacity):
    new_table = make_table(capacity)
    for bucket in table:
        for key, value in bucket:
            # Existing keys are unique, so no duplicate-key scan is needed.
            new_table[key % capacity].append((key, value))
    return new_table


def two_sum(values, target):
    seen = {}
    for index, value in enumerate(values):
        needed = target - value
        if needed in seen:
            return seen[needed], index
        seen[value] = index
    return None


def count_values(values):
    counts = {}
    for value in values:
        counts[value] = counts.get(value, 0) + 1
    return counts

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

table = make_table()
put(table, 10, "Maya")
put(table, 18, "Ravi")
assert table[2] == [(10, "Maya"), (18, "Ravi")]
assert get(table, 10) == "Maya"
assert get(table, 18) == "Ravi"

put(table, 18, "Ravi Kumar")
assert get(table, 18) == "Ravi Kumar"
assert sum(len(bucket) for bucket in table) == 2

larger = resize(table, 16)
assert larger[10] == [(10, "Maya")]
assert larger[2] == [(18, "Ravi Kumar")]
assert get(larger, 10) == "Maya"
assert get(larger, 18) == "Ravi Kumar"
assert remove(table, 10) == "Maya"
assert get(table, 18) == "Ravi Kumar"
assert table[2] == [(18, "Ravi Kumar")]

try:
    get(table, 26)  # Same bucket, but this key was never inserted.
    raise AssertionError("missing keys must not return another value")
except KeyError:
    pass

try:
    remove(table, 10)  # Already removed.
    raise AssertionError("a missing key cannot be removed")
except KeyError:
    pass

try:
    make_table(0)
    raise AssertionError("zero buckets cannot hold a table")
except ValueError:
    pass

assert two_sum([2, 7, 11, 15], 9) == (0, 1)
assert two_sum([3, 3], 6) == (0, 1)
assert two_sum([3], 6) is None
assert count_values([1, 2, 1]) == {1: 2, 2: 1}
assert count_values([]) == {}