unordered_map, hashing, and bucket behaviour

Understanding unordered_map, hashing, and bucket behaviour

An unordered_map is an array of buckets plus a hash function. To find a key it hashes the key once, reduces that hash to a bucket index, then walks the short chain of nodes in that one bucket comparing keys with KeyEqual. That is what average O(1) means here: the work does not scale with how many elements the map holds, only with how long the chain in the single bucket it visits is. The price is that ordering is gone entirely, so there is no sorted traversal and no way to ask for a range of keys.

load_factor() is size() divided by bucket_count(), and max_load_factor() (1.0 by default) is the ceiling the container promises to stay under. When an insert would push the load factor past that ceiling, the container allocates a bigger bucket array and re-links every node into it: an O(n) rehash that also changes iteration order and which bucket each key lives in. Because elements live in individually allocated nodes, a rehash rewires links but never copies or moves an element, which is exactly why pointers and references to elements stay valid while all iterators are invalidated. reserve(n) does that sizing up front so a fill loop rehashes at most once.

For your own key types you supply the hash, and the hard rule is that it must agree with equality: if two keys compare equal they must hash equal, otherwise they get filed in different buckets and find() reports absent for an element that is really stored. Beyond correctness, spread is what buys the constant time, because a hash that maps many distinct keys onto one value produces a single long chain and no amount of rehashing can separate keys that share a hash value. So when lookups feel slow, inspect load_factor() and bucket_size(bucket(k)) for the keys you actually query before changing anything else.

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> ages;
    ages.reserve(2);                 // room for two elements at load factor 1.0
    ages["ada"] = 36;
    ages["grace"] = 45;

    auto buckets_before = ages.bucket_count();
    int& ada = ages.at("ada");        // reference into the node holding ada's value

    for (int i = 0; i < 50; ++i) {
        ages["filler" + std::to_string(i)] = i;   // forces at least one rehash
    }

    std::cout << std::boolalpha;
    std::cout << "size: " << ages.size() << '\n';
    std::cout << "bucket_count grew: "
              << (ages.bucket_count() > buckets_before) << '\n';
    std::cout << "load_factor within limit: "
              << (ages.load_factor() <= ages.max_load_factor()) << '\n';
    std::cout << "ada through the old reference: " << ada << '\n';
    ada = 37;
    std::cout << "ada re-read from the map: " << ages.at("ada") << '\n';
}

Worked examples

#include <cstddef>
#include <iostream>
#include <string>
#include <unordered_map>

struct AlwaysZero {
    std::size_t operator()(const std::string&) const noexcept { return 0; }
};

int main() {
    std::unordered_map<std::string, int, AlwaysZero> m;
    m["red"] = 1;
    m["green"] = 2;
    m["blue"] = 3;
    m["cyan"] = 4;

    const std::size_t home = m.bucket("red");

    std::size_t used = 0;
    for (std::size_t b = 0; b < m.bucket_count(); ++b) {
        if (m.bucket_size(b) != 0) ++used;
    }

    std::cout << std::boolalpha;
    std::cout << "size: " << m.size() << '\n';
    std::cout << "elements in red's bucket: " << m.bucket_size(home) << '\n';
    std::cout << "blue shares that bucket: " << (m.bucket("blue") == home) << '\n';
    std::cout << "non-empty buckets: " << used << '\n';
    std::cout << "grew the bucket array anyway: " << (m.bucket_count() > 1) << '\n';
}

#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>

struct Point {
    int x;
    int y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

namespace std {
template <>
struct hash<Point> {
    std::size_t operator()(const Point& p) const noexcept {
        std::size_t h = std::hash<int>{}(p.x);
        h ^= std::hash<int>{}(p.y) + 0x9e3779b9u + (h << 6) + (h >> 2);
        return h;
    }
};
}

int main() {
    std::unordered_map<Point, std::string> grid;
    grid[{1, 2}] = "start";
    grid[{3, 4}] = "goal";
    grid[{1, 2}] = "start again";

    std::cout << "size: " << grid.size() << '\n';
    std::cout << "at {1,2}: " << grid.at({1, 2}) << '\n';
    std::cout << "count {1,2}: " << grid.count({1, 2}) << '\n';
    std::cout << "count {9,9}: " << grid.count({9, 9}) << '\n';
}

Important notes

Common mistakes

Try it yourself