Кратко и по пунктам — сравнение для задачи подсчёта уникальных событий в потоке (обсуждаю три структуры: хеш-таблица, сбалансированное БД-дерево, Count‑Min Sketch). Отмечу, что «подсчёт уникальных событий» можно понимать по-разному: (a) поддерживать множество уже виденных ключей / membership и точный подсчёт distinct, (b) поддерживать частоты каждого ключа. Для каждого случая укажу, какие гарантии и ограничения.
1) Хеш‑таблица (hash table)
- Гарантии: точный подсчёт — хранит каждый уникальный ключ и его счётчик; операции вставки/обновления и проверки membership дают точный результат (при корректной реализации).
- Память: пропорциональна числу уникальных ключей $n$: $O(n)$ (реальный расход = суммарный размер ключей + счётчиков + служебные данные и контроль загрузки).
- Точность: 100% (нет приближений).
- Временная сложность: амортизированно $O(1)$ на вставку/обновление/поиск.
- Дополнительно: не даёт упорядоченности и тяжеловесна при очень больших $n$; поддерживает удаления точно.
- Когда выбирать: когда $n$ помещается в доступную память и нужен точный результат; когда важны частоты для конкретных ключей; простые real‑time системы с умеренной кардинальностью.
2) Сбалансированное бинарное дерево (RB-tree, AVL и т.п.)
- Гарантии: также точный подсчёт и хранение всех ключей; дополнительно даёт упорядоченность (порядок по ключу), поддерживает диапазонные запросы, ранжирование.
- Память: $O(n)$ (каждый узел = ключ + счётчик + указатели/балансировочные данные).
- Точность: 100%.
- Временная сложность: $O(\log n)$ на вставку/удаление/поиск.
- Дополнительно: лучше для задач, где нужны range‑queries, итерация в порядке, или быстрое получение k‑го по порядку; более высокая константа по сравнению с хеш‑таблицей.
- Когда выбирать: когда важен порядок/диапазонные запросы или нужно детерминированное $O(\log n)$ поведение; при умеренной $n$ и желании точности.
3) Count‑Min Sketch (CMS)
- Назначение: компактная приближённая структура для подсчёта частот элементов в потоке (поддерживает поток обновлений типа «увеличить счётчик ключа»).
- Гарантии: для частоты элемента $i$ с истинной частотой $f_i$ и общим объёмом обновлений $N$ вы получаете оценку ${\tilde{f}}_i$ с гарантией
$${\tilde{f}}_i\ge f_i\text{и}{\tilde{f}}_i\le f_i+\epsilon N$$ с вероятностью не менее $1-\delta$.
Параметры структуры связаны как: ширина $w=\lceil e/\epsilon \rceil$, глубина $d=\lceil \ln (1/\delta )\rceil$.
- Память: $O(w\cdot d)=O\left(\frac{1}{\epsilon }\log \frac{1}{\delta }\right)$ ячеек (намного меньше, чем хранить все ключи при большом $n$).
- Точность: приближённая; CMS всегда переоценивает (нет отрицательных ошибок), ошибка пропорциональна $\epsilon N$. Не даёт точного множества уникальных ключей и плохо подходит для подсчёта чистой кардинальности (distinct count).
- Временная сложность: $O(d)$ на обновление/запрос (обычно $d$ мало).
- Ограничения: не поддерживает корректные отрицательные обновления/удаления без дополнительных ухищрений; не восстанавливает ключи (нельзя перечислить все ключи без дополнительной памяти); плохо подходит для подсчёта числа уникальных элементов (для этого есть специальные структуры).
- Когда выбирать: при больших потоках с ограниченной памятью, когда нужны приближённые частоты «heavy hitters» или быстрые ответы на «сколько раз виделся ключ» с допустимой ошибкой; применяется в сетевой телеметрии, стриминговой аналитике.
4) Примечание про подсчёт количества уникальных элементов (cardinality)
- Ни хеш‑таблица, ни BST, ни CMS непосредственно не являются наиболее эффективными для только оценки числа разных элементов:
- Точные структуры (хеш/BST) дают точное значение, но требуют $O(n)$ памяти.
- Для приблизительного подсчёта cardinality лучше использовать специальные алгоритмы, например HyperLogLog: память ~ $O(\log \log n)$ или фиксированная константа для заданной точности; возвращает оценку числа уникальных с малой относительной ошибкой.
- Для проверки «виделся ли ключ» компактнее будет Bloom filter (приближённо, с ложными позитивами).
5) Короткие практические рекомендации
- Нужна точность и $n$ помещается в память — используйте хеш‑таблицу (если нужен порядок — BST).
- Нужны упорядоченные обходы или range‑запросы — используйте сбалансированное БД‑дерево.
- Ограничена память и поток очень большой; нужны приблизительные частоты / heavy hitters — используйте Count‑Min Sketch (с подбором $\epsilon ,\delta$).
- Нужен только подсчёт числа уникальных элементов (без списков ключей) при очень больших объёмах — используйте HyperLogLog.
- Нужна компактная проверка membership — Bloom filter.
Если нужно, могу привести конкретные численные примеры памяти/параметров для заданных требований по ошибке $\epsilon$ и вероятности $\delta$.