Краткий ответ

Поиск в std::unordered_map имеет ожидаемую сложность O(1), когда хеш-функция равномерно распределяет ключи по корзинам, а число элементов на корзину остаётся небольшим. При большом количестве коллизий несколько ключей попадают в одну корзину, поэтому поиск внутри неё становится линейным; в худшем случае сложность достигает O(n).

Исторический контекст

Хеш-таблицы появились как способ быстро находить значение по ключу без поддержания порядка элементов, который требуется сбалансированным деревьям. Такой подход обычно даёт более быстрый средний поиск, но зависит от качества преобразования ключа в индекс корзины.

В стандартной библиотеке C++ неупорядоченные ассоциативные контейнеры стандартизованы начиная с C++11. Они дополняют std::map: первый ориентирован на ожидаемую скорость доступа, второй гарантирует упорядоченность и логарифмическую сложность основных операций.

Постановка проблемы

Разработчик может ошибочно считать, что любой вызов поиска в std::unordered_map всегда выполняется за константное время. Это приводит к неверной оценке производительности, особенно при внешних или специально подобранных ключах, плохой хеш-функции и большом коэффициенте заполнения.

Коллизии сами по себе нормальны: количество возможных ключей обычно намного больше количества корзин. Риск возникает тогда, когда коллизии распределяются неравномерно и одна корзина содержит значительную долю элементов.

Подробное решение

Контейнер вычисляет хеш ключа, затем по нему выбирает корзину. Внутри корзины он проверяет один или несколько элементов, сравнивая их ключи; поэтому итоговое время зависит не только от вычисления хеша, но и от длины цепочки коллизий или другой внутренней структуры, используемой реализацией.

При равномерном распределении средняя длина поиска остаётся ограниченной, и сложность считается O(1) в среднем. Если же все или многие ключи попадают в одну корзину, поиск просматривает их последовательно и становится O(n) в худшем случае.

Коэффициент заполнения приблизительно равен отношению числа элементов к числу корзин. При его превышении контейнер обычно выполняет rehash: выделяет больше корзин и перераспределяет элементы. Это помогает уменьшить длины цепочек, но отдельная операция перераспределения может стоить O(n); последовательность вставок при этом обычно анализируют с амортизированной ожидаемой сложностью.

Качество хеша — не единственный фактор. На результат также влияют реализация контейнера, политика изменения числа корзин, значение max_load_factor и возможность атакующего заранее подобрать ключи с одинаковыми хешами.

#include <unordered_map>

struct BadHash {
    std::size_t operator()(int) const { return 0; }
};

int main() {
    std::unordered_map<int, int, BadHash> values;
    for (int i = 0; i < 1000; ++i) values[i] = i;
    auto it = values.find(777);
}

В примере все ключи попадают в одну корзину. Поэтому поиск 777 вынужден проверять элементы этой корзины, и для такого распределения его стоимость растёт вместе с числом элементов.

Если требуется гарантированная логарифмическая сложность и порядок ключей, следует рассмотреть std::map. Если нужен средний константный доступ и порядок не важен, подходит std::unordered_map, но хеш-функцию и характер ключей необходимо оценивать отдельно.

Ситуация из практики

Сервис хранит записи по идентификаторам клиентов и стал медленно отвечать после загрузки большого набора данных. Проверка показала, что пользовательская хеш-функция учитывала только несколько младших битов идентификатора, поэтому ключи неравномерно распределялись по корзинам.

Первый вариант — оставить контейнер и увеличить число корзин. Это может уменьшить среднюю длину цепочек, но не устраняет систематически плохое распределение: часть корзин всё равно останется перегруженной.

Второй вариант — заменить контейнер на std::map. Он даёт гарантированную O(log n) для поиска и не зависит от качества хеша, но обычно требует больше сравнений и не предоставляет ожидаемого константного доступа.

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

Что кандидаты часто упускают

Всегда ли увеличение числа корзин устраняет плохие коллизии?

Нет. Если хеш-функция возвращает одинаковое значение для разных ключей, увеличение числа корзин не изменит ситуацию: все ключи по-прежнему попадут в одну корзину. Увеличение числа корзин эффективно только при хешах, которые используют доступный диапазон значений достаточно равномерно.

Гарантирует ли std::unordered_map отсутствие инвалидирования итераторов при изменении значения элемента?

Изменение отображаемого значения через существующий итератор обычно не меняет ключ и структуру контейнера, поэтому само по себе не вызывает перераспределения. Однако вставка, которая приводит к rehash, инвалидирует итераторы контейнера, поскольку элементы перемещаются между корзинами; ссылки и указатели на элементы имеют отдельные гарантии и не следует автоматически приравнивать их к итераторам.

Почему нельзя оценивать производительность только по средней сложности?

Средняя O(1) предполагает приемлемое распределение хешей и характерный набор входных данных. В системах, где ключи поступают извне, атакующий может намеренно создать много коллизий и приблизить поиск к O(n), что приводит к резкому росту времени обработки. Для таких случаев проверяют хеширование на целевых данных, ограничивают входные объёмы, выбирают подходящий контейнер и учитывают требования к устойчивости к атакам.