Хеш-таблицы (цепочки)

Задача

Мы реализуем множество строк, к которому поступают запросы вида

• void Add(s) - добавить строку $s$ в множество
• bool HasKey(s) - сказать, лежит ли сейчас в множестве $s$
• void Remove(s) - удалить $s$ из множества, если она там есть

Мы уже можем решить такую задачу с помощью хешей: заведём set и будем работать не со строками, которые к нам поступают, а с их хешами. Тогда все операции мы умеем выполнять за $O(log(n))$, где $n ~-$ максимальное количество строк, которое будет лежать в множестве.

Однако этот метод имеет существенный минус $~-$ он опирается на предположение о том, что наше хеширование не допускает коллизии, а мы уже знаем из парадокса дней рождений, что это очень сильно предположение. Значит, надо что-то делать с коллизиями. Более того, структура данных, которую мы сейчас придумаем, позволит отвечать на запросы не за $O(log(n))$, а за $O(1)$ в среднем, что, конечно, гораздо лучше.

Структура

Пусть наша хеш-функция отображает все поступающие объекты в $[0, \dots, M-1]$. Заведём двумерный динамический массив (vector по-русски) размера $M$ и в ячейку с номером $i$ (это вектор, будем их называть бакетами) будем складывать все объекты, хеши которых равны $i$.

Теперь, чтобы положить объект в нашу структуру, нам достаточно посчитать его хеш и push_back'нуть его в соответствующий бакет. Для проверки на наличие объекта мы опять же считаем хеш и поочерёдно проверяем все объекты в соответствующем бакете на равенство интересующему нас.

Чтобы удалить элемент надо сделать следующее: найти его в нужном бакете, свапнуть с последним и сделать pop_back.

Оптимизация памяти и перехеширование

Заметим, что сейчас наша структура в тратит как минимум $M$ ячеек памяти. Если мы хотим хешировать по модулю хотя бы $10^9$, то это непозволительная роскошь. Давайте изначально положим количество бакетов равным, скажем, 179, а потом, по мере необходимости, будем увеличивать их количество.

Однако, наша хешфункция все ещё считает хеш по модулю $M$, а не по модулю числа бакетов, что же делать? Давайте просто дополнительно брать остаток от хеша по модулю числа бакетов и класть объект уже туда ($bucket[h(s) \mod bucket\_count].push\_back(s)$).

Заметим, что если у нас маленькое число бакетов, то довольно быстро размер бакета начнёт расти, чего нам не хочется, ведь чем длиннее цепочка, тем дольше работают операции HasKey и Delete. Значит, если цепочки становятся слишком длинными, надо увеличить число бакетов, чтобы цепочки сократились за счёт перераспределения ключей по бакетам.

Будем увеличивать число бакетов вдвое в тот момент, когда load_factor $=\frac{\text{число ключей в таблице}}{\text{число бакетов}}$ начнёт превосходить некоторой заданной наперёд константы, например, $\frac{3}{4}$.

Заметим, что как только мы увеличили число бакетов, значения хешфункции по модулю старого числа бакетов для всех ключей, которые лежали в хеш-таблице, стали неактуальными. Значит, их надо пересчитать. Да, за $O(\text{#ключей в таблице}}$. Заметим, что поскольку мы каждый раз увеличиваем число бакетов вдвое, такие тяжёлые операции будут происходить всё реже, хотя и каждый раз перехешировать придётся больше ключей. Однако, средняя стоимость одной операции будет $O(1)$.