Step 2 of 5

Load factor and rehashing

A hash table's speed depends on keeping the buckets short. 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, the average number of keys per bucket. 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. Every key has to move, because its bucket, hash % bucket_count, depends on the bucket count.

You can watch std::unordered_set do exactly this:

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> s;
    std::size_t start = s.bucket_count();
    int rehashes = 0;
    std::size_t last = start;
    for (int i = 0; i < 1000; i++) {
        s.insert(i);
        if (s.bucket_count() != last) {
            rehashes++;
            last = s.bucket_count();
        }
    }
    std::cout << "grew several times: " << (rehashes >= 3) << "\n";
    std::cout << "at least one bucket per key: " << (s.bucket_count() >= s.size()) << "\n";
    std::cout << "load factor within the limit: " << (s.load_factor() <= s.max_load_factor()) << "\n";
}

grew several times: 1
at least one bucket per key: 1
load factor within the limit: 1

The exact bucket counts differ between standard library implementations (some use prime numbers, some powers of two), so the example checks the rules rather than printing the sizes. With GCC's library, the set grows to 13, 29, 59, 127 buckets and so on, roughly doubling each time, and never lets the load factor pass 1.0.

Why growing keeps inserts O(1)

A rehash costs O(n), since every key moves. But it only happens when the size doubles. Add up all the rehash work while inserting n keys: n/2 + n/4 + n/8 + ... which is less than n. Spread over n inserts, that's O(1) extra per insert: O(1) amortized, the same argument as std::vector growth.

Your task

After inserting, check size_ > 0.75 * buckets_.size(). If so:

1. Create a new vector of lists with twice as many buckets.
2. Move every key from every old bucket into its new bucket, computed with the new bucket count.
3. Replace buckets_ with the new vector.

Since bucket_of uses buckets_.size(), compute the new bucket index directly with the new size while moving (or swap first and then reinsert from the old table).

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