Кратко: при частых range‑запросах и ограниченной памяти предпочтительнее упорядоченная структура (сбалансированное дерево или B/B+‑дерево). Хеш‑таблица выигрывает по простым point‑операциям при достаточном запасе памяти и хорошей реализации open‑addressing.
1) Асимптотика (n — число элементов, k — размер результата диапазона):
- Хеш‑таблица (среднее, хорошая хеш‑функция): поиск/вставка/удаление $O(1)$ в среднем, худший случай $O(n)$. range‑query без внешнего индекса: $O(n+k)$ (надо просканировать все элементы).
- Сбалансированное дерево (AVL/Red‑Black): поиск/вставка/удаление гарантированно $O(\log n)$. range‑query (итерация от нижней границы): $O(\log n+k)$.
2) Память (примерно, s_k — размер ключа, s_v — значение, p — размер указателя, m — число бакетов, α = n/m):
- Хеш‑цепочки: таблица бакетов $\Theta (m)$ + узлы $\Theta (n(s_k+s_v+p))$. При фиксированном $\alpha$ память $\Theta (n(s_k+s_v+p))$.
- Open‑addressing: массив слотов $\Theta (m(s_k+s_v))$, обычно $m\approx n/\alpha$, итого $\Theta (n(s_k+s_v)/\alpha )$ (меньше накладных указателей, но требуется место для пустых слотов).
- Сбалансированное дерево: узлы $\Theta (n(s_k+s_v+c\cdot p))$, обычно $c\ge 2$ (лев/прав + возможно parent/цвет) — заметно больше указателей на элемент.
3) Практические факторы:
- Локальность кэша: open‑addressing хешов лучше (массив), деревья плохо (прыжки по указателям).
- Rehashing/перераспределение: хеш‑таблица периодически требует реаллокации при росте; в условиях ограниченной памяти это может быть дорого или невозможным.
- Удаления: open‑addressing требует tombstones/реорганизации; цепочки проще для частых удалений.
- Range queries: хеш плохо масштабирует — даже при малой константе для point‑опер. дерево даёт прямой, эффективный обход.
- Дисковая/страничная эффективность: для больших наборов и ограниченной памяти лучше B‑ или B+‑дерево (работают блоками, оптимальны для range‑запросов и минимизации I/O).
4) Рекомендации:
- Если основная нагрузка — point lookup/insert/delete и память критична, и range‑запросы редки: open‑addressing хеш‑таблица (низкая накладная на узел, хорошая кэш‑локальность).
- Если частые range‑запросы (или нужны упорядоченные итераторы) и важны гарантии времени — сбалансированное дерево (или ещё лучше B+/B‑tree при блочном хранении).
- При очень строгой памяти и частых range‑запросах рассмотрите B+‑tree с оптимизированным размером страницы (меньше указателей на элемент, эффективные последовательные чтения).
Вывод: для частых range‑запросов и ограниченной памяти предпочтение обычно отдают упорядоченным деревьям (или B+‑tree); хеш‑таблица — лучше для исключительно точечных операций при допустимой цене за память/реорганизацию.