skip to content

What do load_factor, max_load_factor, rehash and reserve mean for a C++ std::unordered_map, and when should you call reserve?

level: middleimportance: should knowfreq 50%

answer

  1. elements per bucket
  2. 1.0 by default
  3. buckets versus elements
  4. ceil(n / max_load_factor())

basics

~20 s

load_factor() is size() divided by bucket_count(); when an insert would exceed max_load_factor(), 1.0 by default, the table rehashes into more buckets. rehash(n) asks for at least n buckets; reserve(n) makes room for n elements. Reserve before a known bulk insert.

solid answer

~40 s

A `std::unordered_map` keeps its elements in **buckets**. `load_factor()` is the average number of elements per bucket, `size() / bucket_count()`. The container tries to keep it at or below `max_load_factor()`, which a newly constructed table starts at `1.0` (a copy takes the source's value); when an insert would exceed it, the table **rehashes**: allocates a larger bucket array and relinks every element, which invalidates iterators. `rehash(n)` guarantees `bucket_count() >= n` and `>= size() / max_load_factor()`. `reserve(n)` is defined as `rehash(ceil(n / max_load_factor()))`, so it counts **elements**, not buckets. Call `reserve` when you know roughly how many elements are coming: with libc++, inserting 100,000 integers rehashed 16 times without it and never with it. `max_load_factor(z)` is only a hint; lowering it trades memory for shorter bucket chains.

code

cpp · 21 lines
cpp
#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> cache;
    std::cout << "default max_load_factor " << cache.max_load_factor() << '\n';

    std::size_t rehashes = 0, buckets = cache.bucket_count();
    for (int i = 0; i < 100000; ++i) {
        cache.emplace(i, i);
        if (cache.bucket_count() != buckets) { ++rehashes; buckets = cache.bucket_count(); }
    }
    std::cout << "no reserve: " << rehashes << " rehashes, " << buckets << " buckets\n";

    std::unordered_map<int, int> sized;
    sized.reserve(100000);  // == rehash(ceil(100000 / max_load_factor()))
    std::size_t before = sized.bucket_count();
    for (int i = 0; i < 100000; ++i) sized.emplace(i, i);
    std::cout << "reserve: " << before << " buckets before, " << sized.bucket_count()
              << " after, load_factor " << sized.load_factor() << '\n';
}

go deeper

for a junior

Know that a std::unordered_map grows its bucket array automatically and that reserve before a bulk insert avoids repeated growth.

for a middle

Define load_factor and max_load_factor, the 1.0 default, and the exact relation between reserve(n) and rehash.

for a senior

Treat rehash as a latency spike: reserve ahead of predictable growth, use the (N + n) <= z * B rule, and size buckets from production counts.

for a principal

Decide where a service pre-sizes its hash tables and how it monitors growth, trading memory headroom against tail latency.

## Buckets and the load factor An unordered container organizes its elements into **buckets**. Keys with the same hash land in the same bucket, and a lookup hashes the key, picks a bucket and compares only against the elements in it. How long those chains are on average is the **load factor**: - `bucket_count()`: the current number of buckets. - `load_factor()`: `size() / bucket_count()`, a `float`. - `max_load_factor()`: the bound the container tries to keep the load factor under. The standard's constructors that build a table from scratch set it to `1.0`; copy construction copies the source's value. - `max_load_factor(z)`: sets a new bound, but the standard words it as a **hint**: it *may* change the maximum, using `z`. The default bucket count of a default-constructed container is implementation-defined. ## When the table grows The standard requires that the number of buckets is increased automatically as elements are added, so that the average stays below the bound. Each growth step is a **rehash**: 1. a new, larger bucket array is allocated; 2. every element is redistributed into it, which means rehashing each key unless the implementation cached its hash; 3. the old array is freed. The elements themselves stay in their nodes, so references survive, but every iterator is invalidated and iteration order changes. Growth policy is the implementation's choice. libstdc++'s default policy picks prime bucket counts with a growth factor of 2; libc++ grows to at least twice the old count and rounds a non-power-of-two request up to a prime. In the code example, 100,000 inserts into an empty libc++ map triggered **16 rehashes** and ended with 102,877 buckets. ## rehash versus reserve | Call | Argument means | Guarantees afterwards | |---|---|---| | `rehash(n)` | a bucket count | `bucket_count() >= n` and `bucket_count() >= size() / max_load_factor()` | | `reserve(n)` | an element count | same as `rehash(ceil(n / max_load_factor()))` | `rehash` is average linear in `size()`, worst case quadratic. Two consequences people miss: - `reserve(n)` on an `unordered_map` and `reserve(n)` on a `std::vector` share a name, but the hash version counts elements against the load factor; there is no "capacity" to query afterwards, only `bucket_count()`. - `rehash(0)` is allowed to *shrink* the bucket array to the minimum that satisfies the load factor; libc++ does shrink when asked for fewer buckets than it has. ## Warming the session cache A session cache that is rebuilt from a snapshot at startup knows its size in advance: 1. call `cache.reserve(expected_sessions)` before the bulk load, so no rehash happens during it; 2. load the snapshot; with libc++, `reserve(100000)` produced 100,003 buckets and a load factor of about 1.0 after 100,000 inserts, with zero rehashes; 3. keep reserving ahead of predictable growth, since each later rehash is a latency spike proportional to the whole table. A guarantee comes with it: the standard says inserts do not invalidate iterators while `(N + n) <= z * B`, where `N` is the current size, `n` the number inserted, `B` the bucket count and `z` the maximum load factor. Reserving makes that condition hold for the planned inserts. ## Tuning max_load_factor - **Lower it** (for example `0.5`) when lookups dominate and memory is cheap: more buckets, shorter chains, fewer equality comparisons per lookup. - **Raise it** when memory matters more than lookup speed; in libstdc++ and libc++ each bucket costs a pointer-sized slot in the bucket array. - Set it **before** reserving, because `reserve` divides by the current maximum load factor, and preferably on an empty table: libc++ never lowers the maximum below the current load factor, so on a loaded map `max_load_factor(0.25f)` left it at 0.626 in one run. libstdc++ stores the new bound without rehashing until a later insert. - Do not expect it to fix a bad hash. The load factor is an average; one overloaded bucket hides inside a healthy-looking number. ## Reading the numbers in production A cheap periodic log line for a long-lived cache is worth having: `size()`, `bucket_count()`, `load_factor()` and the number of rehashes since the last report, counted by comparing `bucket_count()` before and after inserts as the code example does. A rising rehash count says the table should be reserved larger at startup; a steady count with growing latency points away from sizing and towards the hash function or the workload.

  • Does calling max_load_factor(0.25) on a full std::unordered_map immediately make lookups faster?
    Not necessarily. The standard calls the argument a hint. libstdc++ stores the new bound but does not rehash until a later insert; libc++ clamps it to the current load factor, so on a loaded table the call can leave the maximum almost unchanged. To get more buckets now, call `rehash(n)` with an explicit bucket count such as `ceil(size() / 0.25)`, then set the new maximum.
  • Why is reserve(n) on a std::unordered_map defined in terms of rehash?
    Hash containers have no capacity in the vector sense; the only resource is the bucket array. Making room for `n` elements means having enough buckets that `n / bucket_count()` stays at or below `max_load_factor()`, which is exactly `rehash(ceil(n / max_load_factor()))`. Nodes for the elements are still allocated one by one as they are inserted.

  • reserve(n) on an unordered_map allocates n buckets
  • The default max_load_factor is 0.75
  • Rehashing moves elements, so references to them dangle
  • A low load_factor proves every bucket is short
  • max_load_factor(z) always rehashes immediately