Step 2 of 5

Load factor and rehashing

With a fixed 16 buckets, a million keys means about 62,500 per bucket, and "O(1)" becomes a slow linear search. The load factor is size / bucket_count. When it passes a threshold (0.75 is common; std::unordered_map uses 1.0), the table rehashes: it allocates about twice as many buckets and reinserts every key, because each key's bucket depends on the bucket count.

Rehashing is O(n), but it happens so rarely (each time the size doubles) that insertion stays O(1) amortized, the same argument as std::vector growth.

Your turn: extend IntSet so that after an insert makes size > 0.75 * bucket_count, it rehashes into twice as many buckets. The test inserts 200,000 keys, which is only fast if the table grows.

Previous: Buckets and chaining Next: A string-keyed map with erase