Перейти на PRO

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

Тип вопроса: STL Вероятность: 25% Категория: C/C++ Разработчик

Ответ

В реализации 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).

Ответ 18+ 🔞

А, блядь, про unordered_map спросили? Ну это ж классика, ёпта! Сидишь такой, думаешь — о, хеш-таблица, скорость света, поиск за O(1), красота! А потом бац — и нихуя не работает, потому что все ключи в одну корзину попали. Как будто в час пик в одну маршрутку пытаются залезть овердохуища народа.

Смотри, как это устроено под капотом, чтоб тебе не пиздец как потом охуевать. Берётся массив, да. Это корзины (buckets). А в каждую такую корзину вешается односвязный список, типа цепочка. Всё, приехали. Это и есть метод цепочек.

Работает просто, как три копейки:

  1. Ты суёшь туда ключ — ему считают хеш. Хеш-функция, блядь, главная здесь звезда.
  2. По этому хешу вычисляют, в какую именно корзину его пихать: индекс = хеш(ключ) % количество_корзин.
  3. И вот тут начинается самое интересное. Если в этой корзине уже кто-то сидит — welcome to коллизия, сука! Нового пришельца просто добавляют в конец цепочки в этой же корзине. Как в общежитии, блядь, подселяют.

Вот, смотри на этот пиздатый пример. Я тут нарочно хеш-функцию такую кривую написал, что она всегда единицу возвращает. Ядрёна вошь!

#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
}

Запустишь это — и удивление пиздец: корзин дохуя, а все три твоих фрукта сидят в одной, как гомосеки в шкафу. И поиск по такому unordered_map из O(1) превращается в O(n), потому что надо по цепочке ползать. Пидарас шерстяной, а не контейнер.

А теперь про производительность, тут важно, не проеби.

Есть такая штука — коэффициент нагрузки (Load Factor). Это, грубо говоря, насколько плотно упакованы корзины. Считается так: количество_элементов / количество_корзин. По умолчанию, когда этот коэффициент переваливает за 1.0, контейнер такой: «Всё, бля, терпения ноль ебать!» — и делает rehash. Это когда он берёт, увеличивает количество корзин в разы и все элементы заново перераспределяет. Операция, я тебе скажу, не из быстрых, все потоки могут встать.

Чтобы не охуеть в самый ответственный момент, можно этим процессом немного управлять:

map.max_load_factor(0.7); // Говорим: "Слушай, как заполнится на 70% — сразу бей тревогу!"
map.rehash(100); // Или вот так: "На, бля, держи память под 100 корзин сразу, чтобы не дрочился потом!"

Главный вывод, чувак: если хеш-функция — пизда рулю, то никакие оптимизации не спасут. Все элементы свалятся в одну корзину, и твоя супер-пупер хеш-таблица будет работать как обычный список. Доверия ебать ноль к таким ситуациям.

И да, стандарт не говорит точно, как коллизии разрешать. Но все нормальные ребята (GCC, Clang, MSVC) используют именно цепочки. Так что можешь на это рассчитывать.

© ХакСобесов, 2026
support@hacksobesov.com