Деревья, множества, хэш-таблицы
Бинарные деревья. Начало
Бинарное дерево. Способы обхода и удаления вершин
Реализация бинарного дерева на Python
Множества (set). Операции над множествами
Множества set и multiset в C++
Контейнер map библиотеки STL в C++
Префиксное (нагруженное, Trie) дерево. Ассоциативные массивы
Хэш-таблицы. Что это такое и как работают
Хэш-функции. Универсальное хэширование
Метод открытой адресации. Двойное хэширование
Использование хэш-таблиц в Python и С++
Обучающие курсы
Python Python ООП Структуры данных Django C/C++
Телеграм-каналы
Канал selfedu_rus Python Django Машинное обучение Java и С++
Наш канал

Метод открытой адресации. Двойное хэширование

Курс по структурам данных: https://stepik.org/a/134212

Мы продолжаем тему по хэш-таблицам. Это занятие начнем с рассмотрения метода открытой адресации для разрешения коллизий. При использовании этого метода предполагается данные (ключ, значение) хранить непосредственно в ячейках хэш-таблицы. Если ячейка пуста, то в нее записывается какое-либо предопределенное значение, например, None. То есть, мы отказываемся от дополнительного хранения указателей, и это приводит к некоторой экономии памяти. В результате мы имеем возможность формировать более длинные таблицы и, тем самым, уменьшать вероятность возникновения коллизий.

Но коллизии все равно будут появляться. Спрашивается, как с ними бороться в такой ситуации? Давайте вначале я продемонстрирую это на простом примере, а затем, мы его обобщим.

Разрешение коллизий линейным исследованием

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

При этом Новая хэш-функция делает буквально следующее. Для некоторого ключа k она выдает индекс массива, где этот ключ должен храниться, с начальным параметром i=0. Затем, если параметр i увеличивать на единицу, то мы будем по кругу просматривать все элементы массива длиной m, не выходя за его пределы, благодаря операции mod m:

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

Мы подаем на вход хэш-функции ключ «ff» и, допустим, попадаем в ячейку с индексом 3. Но эта ячейка уже занята, то есть, возникла коллизия. Что делать дальше? А дальше мы просто-напросто увеличиваем значение параметра i на единицу и начинаем искать ближайшую свободную ячейку массива. Это ячейка с индексом 5. Поэтому туда и заносится этот ключ с определенным значением. Вот так, при вставке новых ключей происходит разрешение коллизий при открытой адресации. Также можно заметить, что увеличивая параметр i каждый раз на единицу, мы последовательно (то есть, линейно) перебираем ячейки таблицы. Именно поэтому такой подход получил название линейное исследование.

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

Алгоритмы поиска ключей

Пусть у нас имеется все та же хэш-таблица с открытой адресацией и мы хотим получить значение по ключу «ff». Вначале хэш-функция с параметром i=0 выдает значение 3. Так как в этой ячейке хранится другой ключ, то начинаем поиск, увеличивая параметр i каждый раз на единицу. В ячейке 5 находим искомый ключ и возвращаем его значение «фф».

Давайте, теперь посмотрим, как будет происходить поиск не существующего ключа «dd». Предположим, хэш-функция выдала значение индекса 2. Там записан ключ «d». Это не то, что нам нужно. Поэтому мы начинаем поиск, увеличивая параметр i на единицу. Пока мы проходим по заполненным ячейкам, поиск продолжается, но как только встретили первую пустую, поиск завершается и делается вывод, что такого ключа в таблице нет. Я думаю, вы догадались, почему это так. Вспомним, когда происходит добавление ключей, то новый ключ при коллизии добавляется в первую попавшуюся пустую ячейку. Поэтому, если на этапе исследования попадается пустая ячейка, значит, указанного ключа просто нет в таблице. Благодаря этому, нам не нужно просматривать весь массив в надежде найти нужный ключ и это значительно ускоряет процесс поиска.

Алгоритм удаления ключей

Если же нам нужно удалить какой-либо ключ, то действуем аналогичным образом. Сначала по алгоритму поиска находим нужный ключ. Если он присутствует в таблице, то в ячейку записываем значение, нет, не None, а другую предопределенную константу Delete. Почему так? Дело вот в чем. Предположим, что после удаления ключа «ff» мы хотим найти ключ «dd». Пусть в этом случае хэш-функция возвращает 2-й индекс:

Тогда, при последовательном проходе, мы, дойдя до ячейки 5, остановились бы и сделали вывод, что ключа «dd» нет в таблице, тогда как он есть, просто ранее был удален ключ «ff» и нарушилась целостность последовательности заполненных ячеек. Чтобы этого не было, мы используем другую константу Delete, которая означает, что ячейка пуста, но поиск последующих ключей все равно нужно продолжать, пока либо не найдем искомый ключ, либо не дойдем до ячейки со значением None. Вот такая тонкость имеется в алгоритме удаления и последующего поиска ключей с учетом удаленных элементов.

Разрешение коллизий квадратичным исследованием

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

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

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

где a, b – некоторые положительные константы. Причем значения a, b и m нужно выбирать так, чтобы при изменении i в диапазоне [0; m-1] функция перебирала все ячейки таблицы ровно один раз. То есть, она не должна дважды выдавать одну и ту же ячейку. Поэтому параметры a, b и m не могут быть произвольными, включая размер хэш-таблицы. Хотя во всем остальном такой подход, в среднем, показывает лучшие результаты, в сравнении с линейным исследованием.

Двойное хэширование

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

где - вспомогательные хэш-функции. При начальном значении i=0 мы получаем стартовый индекс ячейки , а затем, смещаемся с шагом по хэш-таблице, выполняя, таким образом, перебор ячеек. Здесь мы для разных ключей k мы будем иметь разные смещения и поэтому данные будут хорошо перемешиваться в таблице.

Внимательный слушатель может заметить, что не при любых смещениях мы сможем обойти все ячейки таблицы. Например, если , где n – натуральное число, и , то мы обойдем ячейки таблицы через одну:

Чтобы избежать такого эффекта, значение функции и размер таблицы m должны быть взаимно просты. Я напомню, что два натуральных числа называются взаимно простыми, если у них нет общих делителей, кроме 1. Это условие достаточно просто выполнить. Томас Кормен в своей книге «Алгоритмы: построение и анализ» приводит следующий пример выбора хэш-функции:

где - немного меньше m, например . Было показано, что при размере таблицы и правильном выборе хэш-функции , метод двойного хэширования превосходит методы линейного и квадратичного поиска и близко к идеальной схеме равномерного хэширования. То есть, операции вставки, поиска и удаления ключей, в среднем, выполняются за фиксированное время O(1). Именно поэтому метод двойного хэширования получил широкое распространение и применяется для разрешения коллизий, когда данные хранятся непосредственно в ячейках таблицы.

Заключение

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

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