std::unordered_map изнутриinternals

std::unordered_map<K, V> внутри хранит массив "бакетов" (обычно указателей на головы связных списков узлов). Вставка ключа k: вычисляется hash(k), берётся остаток от деления на количество бакетов (hash(k) % bucket_count) — это индекс бакета, куда добавляется узел.A std::unordered_map<K, V> internally stores an array of "buckets" (typically pointers to the heads of linked lists of nodes). Inserting key k: compute hash(k), take the remainder modulo the bucket count (hash(k) % bucket_count) — that's the index of the bucket the node gets added to.

Стандарт требует именно chaining (а не open addressing), потому что гарантирует стабильность указателей/ссылок на элементы при вставке других элементов — требование, зафиксированное в стандарте C++11 для unordered_map. При open addressing (используется в некоторых сторонних высокопроизводительных хеш-таблицах вроде abseil's flat_hash_map) элементы физически перемещаются внутри одного массива, что несовместимо с этой гарантией.The standard mandates chaining specifically (not open addressing), because it guarantees pointer/reference stability for elements when other elements are inserted — a requirement written into the C++11 standard for unordered_map. Under open addressing (used by some third-party high-performance hash tables like abseil's flat_hash_map), elements physically move within a single array, which is incompatible with that guarantee.

Каждый бакет с более чем одним элементом — это по сути мини-связный список; поиск внутри бакета — линейный O(k), где k — число элементов в этом бакете. Средняя длина цепочки и есть load_factor.Each bucket with more than one element is essentially a mini linked list; searching within a bucket is linear O(k), where k is the number of elements in that bucket. The average chain length is exactly the load_factor.

load_factor() == size() / bucket_count() — среднее число элементов на бакет. Когда load_factor() превышает max_load_factor() (по умолчанию 1.0) после вставки, происходит rehash: выделяется новый, больший массив бакетов (обычно следующее простое число или степень двойки, в зависимости от реализации), и КАЖДЫЙ существующий элемент пересчитывает свой индекс бакета (hash(k) % new_bucket_count) и перемещается в новый массив.load_factor() == size() / bucket_count() — the average number of elements per bucket. When load_factor() exceeds max_load_factor() (1.0 by default) after an insertion, a rehash happens: a new, bigger bucket array is allocated (typically the next prime or power of two, depending on the implementation), and EVERY existing element recomputes its bucket index (hash(k) % new_bucket_count) and moves into the new array.

std::unordered_map<int, int> m;
m.max_load_factor(0.75f);      // rehash раньше, короче цепочки, больше памяти впустую// rehash earlier, shorter chains, more wasted memory
m.reserve(10000);             // заранее выделить bucket_count под 10000 элементов без max_load_factor — избежать rehash'ей в цикле// pre-size bucket_count for 10000 elements at max_load_factor — avoid rehashes in a loop

Rehash — операция O(n): пересчитать хеш и переставить каждый элемент. Как и реаллокация вектора, она амортизируется до O(1) на вставку за счёт геометрического роста bucket_count, но в отличие от vector — узлы не копируются, а просто перевешиваются между списками (указатели на сами узлы valid, но итераторы всё равно инвалидируются, потому что итератор unordered_map кодирует позицию бакета).Rehash is an O(n) operation: recompute the hash and relink every element. Like vector reallocation, it's amortized down to O(1) per insertion via geometric bucket_count growth, but unlike vector — nodes aren't copied, just relinked between lists (pointers to the nodes themselves stay valid, but iterators are still invalidated, because an unordered_map iterator encodes bucket position).

Хеш-функция должна быть детерминированной (одинаковый вход → одинаковый выход в течение всего времени жизни объекта) и согласованной с operator==: если a == b, то обязательно hash(a) == hash(b) (обратное не требуется — разные ключи МОГУТ иметь одинаковый хеш, это и есть коллизия). Нарушение первого требования — undefined behavior, часто необнаруживаемое сразу.The hash function must be deterministic (same input → same output for the object's entire lifetime) and consistent with operator==: if a == b, then hash(a) == hash(b) must hold (the converse isn't required — different keys CAN share a hash, that's exactly a collision). Violating the first requirement is undefined behavior, often not caught immediately.

Для пользовательского типа ключа нужно специализировать std::hash и определить operator==:For a custom key type, you specialize std::hash and define operator==:

struct Point { int x, y; };

bool operator==(const Point& a, const Point& b) {
    return a.x == b.x && a.y == b.y;
}

template<>
struct std::hash<Point> {
    std::size_t operator()(const Point& p) const noexcept {
        return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 1);  // упрощённая комбинация — на практике лучше boost::hash_combine// simplified combination — in practice prefer boost::hash_combine
    }
};

Плохая хеш-функция (например, возвращающая константу) технически корректна по стандарту, но превращает все операции в O(n) — все элементы попадают в один бакет, и unordered_map вырождается в связный список.A bad hash function (e.g., one that returns a constant) is technically standard-compliant, but turns every operation into O(n) — all elements land in one bucket, and the unordered_map degenerates into a linked list.

• cppreference — std::unordered_map