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

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

Структура

Заведём вектор длины $M$, где $M ~- $ максимальное значение хеш-функции $h$. По аналогии с хешированием цепочками, сначала это будет небольшая константа, а по мере заполнения хеш-таблицы мы будем её увеличивать. Далее в тексте по хеш-функцией $h$ автор имеет в виду остаток от хеш-функции по модулю $M$.

Добавление

При добавлении ключа $k$ в хеш-таблицу, мы сначала считаем его хеш, берём его по модулю $M$, и затем кладём в ячейку с получившимся номером $h(k)$. Если она занята (например, до этого добавили другой ключ с таким же значением хеш-функции), то пытаемся положить в $h(k)+1$, $h(k)+2$ итд до тех пор, пока не найдём свободную ячейку (или ячейку, из которой что-то удалили, но об этом чуть позже).

Проверка на наличие

Пусть мы хотим проверить, лежит ли ключ $k$ в нашей хеш-таблице. Посчитаем $h(k)$ и посмотрим на ячейку с таким номером. Если она свободна, значит такого ключа нет в таблице (поймите почему!). Если же ячейка занята, но там лежит не тот ключ, который мы ищем, пойдём в $h(k) + 1$ и так до тех пор, пока мы либо не найдём свободную ячейку, либо не найдём наш ключ, либо не обойдём всю хеш-таблицу, не найдя ни первого ни второго. Если мы нашли свободную ячейку, то ключа нет, если мы нашли ключ, то он есть ( =) ), а если мы обошли всю хеш-таблицу и ничего не нашли, то ключа тоже нет. Более того, если мы обошли всю хеш-таблицу и все ячейки заняты, то надо провести перехеширование, о чём можно прочитать ниже.

Удаление

Чтобы удалить ключ, его сначала надо найти, для этого см. предыдущий пункт. Затем, если его просто удалить из ячейки, то дальнейшие поиски, которые должны были бы пройти мимо этой ячейки, наткнутся на пустую ячейку и решат, что ключа, который они ищут нет, что может быть неверно. Поэтому вместо удаления мы будем класть в такие ячейки специальное значение DELETED, которое не встречается среди ключей.

Перехеширование

Аналогично с хешированием цепочками, будем перехешировать нашу хеш-таблицу когда load_factor становится больше $\frac{3}{4}$. Для этого заведём хеш-таблицу с вдвое большим числом бакетов и все старые ключи закинем в неё (с новой хеш-функцией), а старую хеш-таблицу удалим.

Длинные run'ы

Пусть мы вставили в хеш-таблицу 10 разных ключей с одинаковым значением хеш-функции. По построению они займут 10 последовательных ячеек таблицы $i, i+1, \dots, i + 9$. Если теперь мы захотим вставить 2 ключа со значением хеш-функции, равным $i - 1$, то первый вставится сразу, а вот для вставки следующего нам придётся пройти 10 ячеек прежде, чем мы найдём свободную.

Эта проблема имеет 2 примерно одинаковых по производительности решения:

1. на $i$-ом шаге мы идём не в ячейку с номером $h(k) + i$, а в $h(k) + i^2$
2. на $i$-ом шаге мы идём в ячейку с номером $h_1(k) + i \times h_2(k)$, где $h_i ~-$ разные хеш-функции.

Благодаря такому решению мы избавляемся от проблемы кластеризации (когда ключи лежат рядом) и средняя длина run'а (последовательность ячеек, которую мы проходим в запросе) уменьшается за счёт уменьшения их пересечений для разных значений хеш-функции.

---

Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex