Кратко и по делу — как это устроено, какие стратегии и что влияет на производительность.
Основная идея
- Таблица размера $m$ хранит ключи/значения по индексу, вычисляемому хеш-функцией $h(k)$ мод $m$. При коллизии (два ключа дали один индекс) применяют стратегию разрешения коллизий.
- Обозначения: $n$ — число элементов, $m$ — число «ячееk» (buckets), загрузка (load factor) $\alpha =n/m$.
Стратегии разрешения коллизий
1. Отдельные цепочки (separate chaining)
- В каждой ячейке список/вектор/дерево элементов, попавших в этот бакет.
- Время поиска: в среднем $O(1+\alpha )$; при равномерном распределении цепочки короткие.
- Плюсы: простота вставки/удаления, легко масштабировать (можно держать $\alpha >1$).
- Минусы: указатели/распределённая память → плохая локальность кэша; при плохом хеше — деградация до $O(n)$.
- Практика: списки могут заменять на динамические массивы или на сбалансированные деревья (Java HashMap «treeify»), чтобы ограничить худший случай до $O(\log n)$.
2. Открытая адресация (open addressing)
- Все элементы хранятся прямо в массиве; при коллизии ищем другую позицию по последовательности проб (probing).
- Варианты:
- Линейное пробирование: $h(k),h(k)+1,h(k)+2,\dots$ - Простая реализация, лучшая кэш-локальность, но склонность к кластеризации (primary clustering).
- Ожидаемое число проб для линейного пробирования (классический анализ):
- для неуспешного поиска $\approx \frac{1}{1-\alpha }$,
- для успешного поиска $\approx \frac{1}{2}\left(1+\frac{1}{1-\alpha }\right)$.
- Квадратичное пробирование: пропуски зависят квадратично → уменьшает кластеризацию, но требует осторожного выбора размера таблицы.
- Двойное хеширование (double hashing): второй хеш задаёт шаг; даёт поведение близкое к «случайному хешированию», меньше кластеров.
- Для равномерного (random) размещения ожидаемые значения:
- неуспешный поиск $\approx \frac{1}{1-\alpha }$,
- успешный поиск $\approx \frac{1}{\alpha }\ln \frac{1}{1-\alpha }$.
- Плюсы: лучшая кэш-локальность, меньше накладных указателей, часто экономней по памяти при низком $\alpha$.
- Минусы: удаление сложнее (требуются «tombstones» или реинсерты), производительность резко падает при $\alpha$ близком к 1.
3. Специализированные схемы
- Cuckoo hashing: 2 (или более) позиции для каждого ключа, при вставке возможны перемещения; гарантированное $O(1)$ время поиска, вставка может потребовать реорганизации/ре-хеширования.
- Robin Hood hashing: минимизирует разброс расстояний до родного места — меньше вариативности времени доступа.
- Hopscotch hashing: сочетает преимущества локальности и малых цепочек перемещений.
- Эти схемы дают лучшие гарантии на худший/амортизированный случай, но сложнее в реализации.
Амортизированная сложность операций
- При разумной загрузке и хорошей хеш-функции:
- Поиск, вставка, удаление — амортизированно $O(1)$.
- Рехеширование/увеличение таблицы:
- При увеличении размера вдвое переразмещение всех элементов — разовая операция $O(n)$.
- Если увеличивать по фактору (обычно 2), стоимость ре-хеша амортизированно распределяется → вставка остаётся $O(1)$ амортизированно.
- Худший случай:
- При плохой хеш-функции или атаке: операция может быть $O(n)$ (в цепочках — длинная цепочка; в открытой адресации — длинная последовательность проб).
Влияние качества хеш-функции
- Требования к хорошему хешу:
- Равномерное распределение по бакетам (низкая вероятность коллизий).
- Быстродействие (хеш вычисляют часто).
- Использование всех битов исходных данных (избегать использования только низких/высоких битов при power-of-two размере).
- Стохастическая независимость или случайная соль (seed) для защиты от целенаправленных коллизий (DOS-атаки).
- Плохой хеш → повышенная $\alpha$ в отдельных бакетах → увеличение времени до $O(n)$.
- Практика: для таблиц размера степеней двойки используют хорошие финализаторы/микширование (multiplicative hashing, xorshift), либо берут простые, но быстрые non-cryptographic хеши (MurmurHash, xxHash). Криптографические хеши обычно излишни и медленны, но могут защищать от атак.
Практические рекомендации
- Держите целевую нагрузку $\alpha$ ниже некоторого порога (например $0.5-0.75$) для open addressing; в chaining можно позволить $\alpha >1$.
- При ограничении памяти и важной кэш-локальности — open addressing (линейное/двойное).
- Если важны простота удаления и устойчивость к худшим случаям — chaining.
- Используйте проверенные хеш-функции и, при веб-приложениях, соль/рандомизацию, чтобы предотвратить целенаправленные коллизии.
Кратко по сложностям
- При хорошей хеш-функции и контролируемой загрузке: поиск/вставка/удаление — амортизированно $O(1)$.
- Рехеш: разовая $O(n)$, амортизированно $O(1)$ на вставку при росте таблицы геометрически.
- Плохой хеш или атака → возможная деградация до $O(n)$.