Кратко: перечислю структуры, дам их асимптотику/поведение при коллизиях и практические компромиссы, затем рекомендую для каждого сценария.
1) Хеш-таблица с открытой адресацией (linear/quadratic/дифф. пробинг)
- Время:
- поиск/вставка/удаление: в среднем $\mathrm{O}(1)$ (фактически $\mathrm{O}\left(\frac{1}{1-\alpha }\right)$, где $\alpha$ — заполненность), в худшем — $\mathrm{O}(n)$.
- итерация: $\mathrm{O}(n)$ по массиву, хорошая локальность кэша.
- Память: массив пар (ключ,значение) + метки состояния; низкий накладной указателей.
- Коллизии: разрешаются последовательными пробами — кластеризация (primary/secondary) ухудшает время при высокой $\alpha$.
- Компромиссы: очень быстрая и кэш-дружественная при умеренной/низкой $\alpha$; плохо при высоком заполнении и при частых удалениях (требует переразметки) и при переменных размерах ключей (копирование).
2) Хеш-таблица с цепочками
- Время:
- среднее поиск/вставка/удаление: $\mathrm{O}(1+\alpha )$ (обычно $\mathrm{O}(1)$ при контролируемой $\alpha$), худшее — $\mathrm{O}(n)$ (все в одной цепочке).
- итерация: $\mathrm{O}(n)$, но хуже локальность из‑за указателей.
- Память: массив бакетов + для каждого элемента либо узел (указатели) либо динамический контейнер; больше накладных указателей, но гибко при разном размере данных.
- Коллизии: просто добавляются в цепочку; деградация мягче, легко использовать списки/векторы/деревья внутри бакета (например, переход на дерево при длинной цепочке).
- Компромиссы: лучше при неопределённом числе элементов и частых удалениях/вставках без полной переразметки; хуже по кэшу и по памяти на указатели.
3) Самобалансирующееся дерево поиска (AVL, Red‑Black)
- Время: поиск/вставка/удаление — гарантированно $\mathrm{O}(\log n)$; итерация (in‑order) — $\mathrm{O}(n)$ (сортированный порядок).
- Память: узлы с указателями и балансной информацией — значительный накладной.
- Коллизий хеш‑типа нет (ключи упорядочены, сравнения определяют путь).
- Компромиссы: гарантированные временные пределы и упорядоченность; хуже по кэш-попаданию и по постоянной фактору чем хеш при точечных запросах.
4) Сбалансированное B‑/B+‑дерево (пакетно-оптимизированное дерево)
- Время: поиск/вставка/удаление — $\mathrm{O}({\log }_{B}n)$ (B — порядок узла), итерация — $\mathrm{O}(n)$ с хорошей блоковой локальностью.
- Память: узлы содержат много ключей/указателей — полезно при блочном хранении (диск/SSD) и при пакетных операциях.
- Компромиссы: оптимально для внешней памяти и для больших блоковых операций; в памяти RAM обычно уступает по постоянным факторам.
5) Пробитое/радиксное дерево (Patricia / radix trie)
- Время: поиск/вставка/удаление — $\mathrm{O}(L)$, где $L$ — длина ключа в битах/символах (в компрессированной форме — количество различающих битов).
- Память: в классическом trie — большой разброс по памяти; в компрессированных (Patricia) — значительно экономнее при общих префиксах.
- Коллизии: нет как таковых; ключи различаются по префиксам/битам.
- Компромиссы: отлично при строковых/битовых ключах с общими префиксами и при требовании префиксного поиска; неэффективен для коротких случайных ключей с высокой разбивкой без компрессии.
Рекомендации по сценариям
(a) Низкая латентность в памяти (минимальная задержка доступа, хорошая кэш‑локальность)
- Выбор: хеш с открытой адресацией.
- Почему: проход по смежному массиву даёт наилучшую кэш‑локальность, среднее время ~$\mathrm{O}(1)$. Число проб и нагрузку контролируйте ($\alpha \lesssim 0.7$) и избегайте частых ремэппингов.
(b) Память сильно ограничена
- Выборы (по приоритету): 1) открытая адресация с компактными записями (при фиксированном размере ключа/значения), 2) компрессированный radix/Patricia trie (если ключи имеют общие префиксы), 3) chaining только если можно хранить элементы в компактных массивах без указателей.
- Почему: открытая адресация минимизирует накладные указатели; Patricia сокращает дублирование префиксов. Цепочки и классические деревья платят большим количеством указателей.
(c) Частые пакетные вставки (batch inserts)
- Выборы: 1) хеш с открытой адресацией, если заранее можно выделить итоговый размер (предварительное резервирование предотвращает переразметку); 2) B‑дерево / B+‑tree при больших блоковых вставках на внешнюю память; 3) radix‑trie если ключи похожи и вставки по префиксам.
- Почему: при заранее выделенном размере открытая адресация даёт быструю амортизированную вставку $\mathrm{O}(1)$. Если вставки очень большие и внешняя память/SSD задействованы — B‑деревья эффективнее.
(d) Интенсивные итерации по ключам (прямой обход всех ключей, возможно в сортированном порядке)
- Выборы: 1) для неотсортированного быстрого обхода — хеш с открытой адресацией (линейный проход по массиву, хорошая локальность); 2) для отсортированного обхода — самобалансирующееся дерево или B+‑дерево (in‑order или последовательные leaf‑страницы), особенно B+ для блочной итерации.
- Почему: open‑addressing — лучший по сырой пропускной способности обхода; деревья дают отсортированность и предсказуемый порядок.
Короткие сводные сравнения по операциям (среднее/худшее):
- Open addressing: поиск/вставка/удаление среднее $\mathrm{O}(1)$, худшее $\mathrm{O}(n)$; итерация $\mathrm{O}(n)$; кэш‑дружественно.
- Chaining: среднее $\mathrm{O}(1)$ (фактически $\mathrm{O}(1+\alpha )$), худшее $\mathrm{O}(n)$; память на указатели; гибкая обработка коллизий.
- AVL/Red‑Black: $\mathrm{O}(\log n)$ гарантированно; отсортированность; худшая кэш‑локальность.
- B/B+: $\mathrm{O}({\log }_{B}n)$; отлична для блочных/внешних операций и пакетной итерации.
- Radix/Patricia: $\mathrm{O}(L)$ (L — длина ключа); хороша для префиксных операций; память зависит от компрессии префиксов.
Практические советы
- Если нужна максимальная скорость чтения/низкая латентность и ключи фиксированы — открытая адресация с предварительным резервированием.
- Если память бедна на указатели, но ключи длинные с общими префиксами — используйте компрессированный radix.
- Для стабильной гарантии времени на операцию и сортированного доступа — самобалансирующееся дерево или B+ для блочного ввода/вывода.
- В гибридных реализациях комбинируют: хеш‑таблица с бакетами, где длинные бакеты заменяются деревом (как в некоторых std::unordered_map реализации), чтобы избежать худших случаев.
Если хотите — могу дать конкретные числовые пороги/параметры (рекомендуемая нагрузка $\alpha$, размеры бакетов, выбор пробинга) под вашу рабочую нагрузку.