Вкратце и по пунктам (сравнение хеш-таблицы vs сбалансированного бинарного дерева, на примере std::unordered_map vs std::map):
1) Время (асимптотика)
- std::unordered_map (хеш): среднее время поиска/вставки/удаления $O(1)$, худший случай (при многих коллизиях или специально подобранных ключах) $O(n)$. Реально — очень быстро для «обычных» ключей.
- std::map (сбалансированное дерево, обычно RB-tree): гарантированное время поиска/вставки/удаления $O(\log n)$ в худшем и среднем случае. Константы больше, чем у хеша, но предсказуемо.
2) Память
- std::unordered_map: хранит массив бакетов размера $B$ плюс узлы для элементов; память = $O(B+n)$. Из-за бакетов и возможных пустых слотов обычно больше накладных расходов на малых/редких данных. Зависит от load_factor ($\alpha =n/B$).
- std::map: хранит узел на элемент (указатели на left/right/parent + цвет/служебные данные) — память $O(n)$. Накладные расходы на узел могут быть сопоставимы с узлом в хеш-таблице, но нет массива бакетов, поэтому при больших $n$ иногда компактнее; на малых — map может быть выгоднее по сравнению с сильно разреженным unordered_map.
3) Детeрминированность итерации
- std::unordered_map: порядок итерации не определён стандартом, зависит от реализации, хеша и текущего состояния (rehash). Итерация ненадёжна для воспроизводимости; вставки/rehash могут менять порядок.
- std::map: итерация упорядочена по ключу (в порядке компаратора) и детерминирована при одинаковой последовательности операций; подходит, когда нужен упорядоченный вывод или стабильный порядок.
4) Устойчивость к атакам (подбор ключей / DoS)
- std::unordered_map: если злоумышленник может подбирать входы, он может создать множество коллизий и превратить операции в $O(n)$ — классическая атака на хеш-таблицы. Стандарт сам по себе не требует рандомизации хеша; некоторые реализации вводят защитные меры (рандомизация или альтернативные стратегии), но нельзя на это полагаться во всех окружениях.
- std::map: атаке через коллизии хеша не подвержен — гарантированное $O(\log n)$. Поэтому предпочтителен в публичных сервисах, где входы не доверенные.
5) Итераторы и их валидность
- std::unordered_map: rehash (автоматический при превышении load factor или вручную) инвалидирует все итераторы; вставка может инвалидировать при rehash; удаление инвалидирует только удаляемый элемент.
- std::map: вставка не инвалидирует существующие итераторы, удаление инвалидирует только итератор на удалённый элемент; более стабильное поведение итераторов.
6) Сценарии использования / рекомендации
- Выбирать std::unordered_map когда: нужен максимально быстрый доступ по ключу в среднем, не важен порядок, данные из доверенного источника или вы контролируете хеш/рандомизацию; примеры — кэши, частотные подсчёты, быстрые ассоциативные массивы.
- Выбирать std::map когда: нужен упорядоченный перебор / диапазонные запросы (lower_bound/upper_bound), требуются гарантии по худшему случаю $O(\log n)$, нужен стабильный порядок итерации или безопасная работа с недоверенными входами; примеры — индексы с диапазонными запросами, публичные серверы, где возможен DoS через коллизии.
Короткое резюме:
- скорость в среднем: std::unordered_map ($O(1)$) быстрее; гарантии и порядок: std::map ($O(\log n)$) надёжнее; память: зависит от реализации и load factor, но unordered_map часто имеет большую накладную из‑за бакетов; безопасность против подборов ключей: std::map выигрывает.