В каком случае временная сложность поиска элемента в std::unordered_set деградирует до O(n)?

std::unordered_set реализован как хеш-таблица. Средняя сложность операций (вставка, удаление, поиск) составляет O(1), но в худшем случае она может деградировать до O(n), где n — количество элементов в контейнере.

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

Конкретные сценарии:

1. Плохо написанная или злонамеренная хеш-функция, возвращающая одно и то же значение для всех ключей.

   struct TerribleHash {
       std::size_t operator()(const std::string&) const {
           return 0; // Все ключи попадут в bucket #0
       }
   };
   std::unordered_set<std::string, TerribleHash> set;
   // Любой поиск в `set` будет O(n).

2. Атака на сложность (Hash Flooding Attack), когда злоумышленник, зная хеш-функцию, генерирует большое количество ключей, вызывающих коллизии.

3. Неудачный выбор коэффициента max_load_factor и отсутствие рехеширования, приводящее к чрезмерной заполненности всех корзин.

Как избежать:

• Используйте стандартные хеш-функции (std::hash) для встроенных и стандартных типов.
• Для пользовательских типов комбинируйте хеши полей с помощью boost::hash_combine или аналогичных техник.
• В C++11 и позднее стандартная библиотека требует от реализаций защищаться от худшего случая (например, переключаясь на дерево внутри переполненной корзины), но полагаться только на это не стоит.