How it works
Load factor is entries divided by buckets, and rising load predicts more collisions. Implementations resize past a threshold, rehashing every key.
Explain resizing as an amortised cost: occasional linear work spread across many insertions.
Common error
Ignoring load factor when reasoning about performance, which makes the constant-time claim unfalsifiable.
Worked example
Example
Entries: 6
Buckets: 8
Load factor: 6 / 8 = 0.75
After expanding to 16 buckets: entries remain 6Load factor compares the number of entries with table capacity. Changing capacity changes bucket calculations, so entries generally need to be redistributed. Load factor is not a guarantee of a collision-free table.
Exercises
5.4.1 · Explain
Find the load factor for 9 entries in 12 buckets, then after expansion to 24 buckets.
Show solution
The load factors are 9/12 = 0.75 and 9/24 = 0.375.
5.4.2 · Explain
Why is copying entries to the same numeric indices insufficient when a table changes capacity?
Show solution
Bucket assignment depends on capacity. Recompute the destination under the new table size so lookup and insertion remain consistent.