Hash Tables

«Для каждого заказа найти пользователя», «есть ли такой элемент среди уже виденных», «сколько раз встречается значение» — если ответ ищется проходом по коллекции, а сам вопрос задаётся в цикле, получается $O(n\cdot m)$. Миллион заказов и миллион пользователей — это $10^{12}$ операций.

Отсортировать и искать бинарно — уже лучше, $O(n\log n)$, но порядок здесь никому не нужен: вопрос-то про точное совпадение ключа, а не про соседей по величине.

Отсюда средняя стоимость операции — константа, не зависящая от размера коллекции. Плата известна заранее: $O(n)$ памяти, отсутствие порядка и худший случай, который надо держать в уме.

a:  2   7   11   15        цель 9

2:   нужно 9 - 2 = 7   ->  семёрку ещё не видели, запоминаем двойку
7:   нужно 9 - 7 = 2   ->  двойка в таблице есть  ->  ответ 2 + 7

Ключевой ход — перевернуть вопрос. Мы не ищем пару к текущему элементу среди оставшихся, а заранее знаем, какое число нам нужно, и проверяем, встречалось ли оно. Один проход вместо перебора пар.

a b a c b a

a -> 3
b -> 2
c -> 1

теперь любой вопрос про количество -- одно обращение

Таблица — это массив корзин и функция, переводящая ключ в его номер: $h(\text{ключ})\mathrm{mod}m$. Разные ключи могут попасть в одну корзину — это коллизия, и её нужно разрешать. Два основных способа: цепочки (в корзине список) и открытая адресация (ищем следующую свободную ячейку по правилу пробирования).

• Коэффициент заполнения — отношение числа элементов к числу корзин; при превышении порога таблица перестраивается вдвое больше.
• Рехеширование стоит $O(n)$, но случается всё реже — отсюда амортизированная константа на вставку.
• Требование к ключу: неизменяемость и согласованность хеша с равенством. Равные ключи обязаны иметь равный хеш.

Константа получается не из магии, а из двух допущений. Первое: хеш-функция распределяет ключи по корзинам примерно равномерно, поэтому средняя длина цепочки равна коэффициенту заполнения, а он поддерживается ограниченным. Второе: рост таблицы геометрический — при удвоении суммарная стоимость всех рехеширований линейна, то есть на операцию приходится константа.

Оба допущения можно нарушить, и тогда таблица деградирует до списка. Если ключи подобраны злонамеренно под известную хеш-функцию, все они попадут в одну корзину: это не теоретический риск, а класс атак на веб-сервисы (HashDoS). Защита — рандомизация хеша при старте процесса, и в современных языках она включена по умолчанию.

Параметры реализации, которые видны снаружи: способ разрешения коллизий (цепочки против открытой адресации — вторая быстрее по кешу, но чувствительнее к заполнению), пороговый коэффициент заполнения и рандомизация хеша.

• Изменяемый ключ. Положили список или объект, изменили его — и запись больше не находится: хеш изменился, корзина осталась прежней.
• Хеш не согласован с равенством. Равные объекты с разными хешами дают дубликаты в множестве.
• Опора на порядок обхода. Он не гарантирован по смыслу структуры; нужен порядок — сортируйте явно.
• Память. Таблица держит запас под заполнение: на миллиардах ключей это гигабайты, и иногда дешевле отсортировать.
• Вещественные ключи. 0.1 + 0.2 и 0.3 — разные ключи; для дробных величин используют округление до целых единиц.
• Коллизионная атака. Если ключи приходят извне, нужна рандомизация хеша — иначе $O(n)$ на операцию по чужому выбору.

1. Почему средняя стоимость операции — константа, а худшая — $O(n)$?
2. Почему таблица растёт вдвое, а не на фиксированное число корзин?
3. Что произойдёт, если положить в множество изменяемый объект и затем его изменить?
4. Группировка анаграмм: какой ключ выбрать и почему он одинаков у всех слов группы?
5. Когда массив-счётчик предпочтительнее хеш-таблицы?