Как разрешаются коллизии в std::unordered_map?

В реализации std::unordered_map из стандартной библиотеки C++ коллизии (ситуации, когда разные ключи имеют одинаковый хеш) разрешаются с помощью метода цепочек (separate chaining).

Принцип работы:

• Хеш-таблица состоит из массива «корзин» (buckets).
• Каждая корзина содержит односвязный список (или иногда двусвязный список) элементов.
• При вставке или поиске ключа:
  1. Вычисляется хеш-код ключа.
  2. По хеш-коду определяется индекс корзины: index = hash(key) % bucket_count.
  3. Операция (вставка, поиск, удаление) выполняется над цепочкой элементов в этой корзине.

Пример, демонстрирующий коллизию:

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

struct BadHash {
    // Плохая хеш-функция: всегда возвращает 1
    std::size_t operator()(const std::string&) const { return 1; }
};

int main() {
    std::unordered_map<std::string, int, BadHash> map;
    map["apple"] = 1;   // Хеш=1 -> корзина 1
    map["banana"] = 2;  // Хеш=1 -> корзина 1 (КОЛЛИЗИЯ, добавляется в ту же цепочку)
    map["cherry"] = 3;  // Хеш=1 -> корзина 1 (еще одна коллизия)

    std::cout << "Bucket count: " << map.bucket_count() << 'n';
    std::cout << "Elements in bucket #1: " << map.bucket_size(1) << 'n'; // Выведет 3
}

Управление производительностью:

• Коэффициент нагрузки (Load Factor): Отношение size() / bucket_count(). При превышении max_load_factor() (по умолчанию 1.0) происходит rehash — увеличение количества корзин и перераспределение всех элементов, что может быть дорогой операцией.

  map.max_load_factor(0.7); // Установить максимальный коэффициент нагрузки
  map.rehash(100); // Заблаговременно выделить память под 100 корзин

• При большом количестве коллизий в одной корзине время поиска деградирует до O(n). Качественная хеш-функция — ключ к производительности.

Важно: Стандарт C++ не фиксирует конкретный метод разрешения коллизий, но метод цепочек используется во всех основных реализациях (GCC libstdc++, Clang libc++, MSVC STL).