Ниже краткое сравнение по операциям, памяти и практическим сценариям для каждой структуры. Везде $n$ — число элементов, при необходимости указываю среднее/худшее время.
1) Массив (array)
- Сложность:
- доступ по индексу: $\mathrm{O}(1)$ - поиск (линейный): $\mathrm{O}(n)$ - вставка/удаление в середину: $\mathrm{O}(n)$ - добавление в конец (динамический массив амортизированно): $\mathrm{O}(1)$ амортиз.
- Память: $\mathrm{O}(n)$ подряд; минимальные накладные расходы (константный метаданных), возможна неиспользуемая зарезервированная ёмкость.
- Практика / примеры:
- случайный доступ к элементам; статические таблицы; реализация массивов в языках; хорош для сортировки в памяти и для работы с последовательными блоками данных.
2) Связный список (singly/doubly linked list)
- Сложность:
- доступ по индексу: $\mathrm{O}(n)$ - вставка/удаление при известной позиции (узле): $\mathrm{O}(1)$ - поиск: $\mathrm{O}(n)$ - Память: $\mathrm{O}(n)$ плюс накладные указатели: для односвязного — примерно $n$ указателей, для двусвязного — примерно $2n$ указателей.
- Практика / примеры:
- частые вставки/удаления в середине при наличии итератора; реализации очередей/стеков (если не требуется случайный доступ); список смежности в графах (когда важны быстрые вставки).
3) Хеш-таблица (hash table)
- Сложность (с хорошей хеш-функцией, среднее):
- поиск/вставка/удаление: $\mathrm{O}(1)$ среднее, $\mathrm{O}(n)$ худшее (коллизии или атака)
- Память: $\mathrm{O}(n)$ с константным фактором, зависящим от коэффициента заполнения $\alpha$ (таблица размера $m\approx n/\alpha$); дополнительные затраты на ключи/значения и служебные метки.
- Практика / примеры:
- быстрые ключ-значение операции: кэширование, подсчёт частот, множество уникальных элементов; когда важен быстрый доступ, не нужен упорядоченный перебор.
4) Сбалансированные деревья (AVL, RB-tree)
- Сложность:
- поиск/вставка/удаление: $\mathrm{O}(\log n)$ (среднее и худшее)
- проход в порядке: $\mathrm{O}(n)$ - Память: $\mathrm{O}(n)$ с накладными указателями на детей (и возможно на родителя) плюс небольшие метаданные (баланс/цвет).
- Практика / примеры:
- упорядоченные коллекции, диапазонные запросы, операции predecessor/successor; базы данных и индексы, реализации std::map / TreeMap; когда нужен упорядоченный вывод или гарантированное логарифмическое время.
5) Куча (heap, бинарная куча / priority queue)
- Сложность (для бинарной кучи в массиве):
- получение минимума/максимума: $\mathrm{O}(1)$ - вставка: $\mathrm{O}(\log n)$ - извлечение экстремума: $\mathrm{O}(\log n)$ - уменьшение/увеличение ключа: $\mathrm{O}(\log n)$ (в зависимости от реализации)
- Память: $\mathrm{O}(n)$, обычно реализуется в массиве (малый константный оверхед).
- Практика / примеры:
- планирование задач, алгоритмы на графах (Dijkstra, A*), объединение k отсортированных списков, очереди с приоритетом.
6) Префиксное дерево (trie)
- Сложность (для ключей длины $L$):
- вставка/поиск/удаление: $\mathrm{O}(L)$ - Память: потенциально большое — в худшем случае число узлов пропорционально сумме длин ключей; вариант компрессии (radix/compact trie) уменьшает расход. Часто накладной фактор зависит от размера алфавита (дети на символы).
- Практика / примеры:
- автодополнение и поиск по префиксам, словари, IP-таблицы с префиксами, задачи, где важен поиск по префиксу или распределение по символам.
7) Bloom-фильтр
- Сложность:
- вставка: $\mathrm{O}(k)$ ( $k$ — число хеш-функций)
- проверка принадлежности: $\mathrm{O}(k)$ - удаления стандартно не поддерживаются (есть варианты Counting Bloom)
- Память: $\mathrm{O}(m)$ бит, где $m$ выбирают для целевого false-positive rate $p$. Вероятность ложного срабатывания:
$$p\approx {\left(1-e^{-kn/m}\right)}^k$$ оптимальное число хешей:
$$k\approx \frac{m}{n}\ln 2$$ - Свойства: экономная по памяти структура с возможными ложноположительными ответами, но без ложных отрицаний.
- Практика / примеры:
- фильтрация запросов к внешнему хранилищу (CDN, базы данных) перед дорогой операцией; проверка не принадлежит ли элемент множеству; распределённые системы (например, предотвращение лишних запросов).
Короткие рекомендации выбора
- Нужен быстрый случайный доступ и компактность → массив.
- Частые вставки/удаления по итератору → связный список.
- Быстрые ключ-значение операции без порядка → хеш-таблица.
- Нужен порядок, диапазонные запросы и предсказуемое время → сбалансированное дерево.
- Приоритетные задачи → куча.
- Поиск по префиксу / словарные операции по строкам → trie.
- Очень экономичная проверка принадлежности с допуском ложноположительных → Bloom-фильтр.
Если нужно, могу привести табличное сравнение со всеми сложностями в одну матрицу.