Схемы хеширования

Традиционно принято выделять две схемы хеширования:

• хеширование с цепочками (со списками);

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

В первом случае выбирается некая хеш-функция f(k) = i, где i трактуется как индекс в таблице списков t. Поскольку нельзя гарантировать, что не встретится двух разных ключей, которым соответствует один и тот же индекс i (коллизия), такие «однородные» ключи просто помещаются в список, начинающийся в i-ячейке хеш-таблицы t (см. рисунок). Очевидно, что процесс заполнения хеш-таблицы будет достаточно простым, но при этом доступ к элементам потребует двух операций: вычисления индекса и поиска в соответствующем списке. Операции по занесению и поиску элементов при таком виде хеширования будут вестись в незамкнутом (открытом) пространстве памяти.

Отображение ключей путем хеширования с цепочками

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

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

• по первичному ключу новой строки вычисляется значение хеш-функции f(k) и результат трактуется, как номер строки в созданной таблице;

• если строка уже занята, производится проверка следующих строк по специальному алгоритму до тех пор, пока не будет обнаружено свободное место.

Аналогично производится поиск нужной строки:

• если после вычисления f(k) на месте в таблице, которое соот­ветствует вычисленному значению, оказывается пустая строка, значит, искомой строки просто нет;

• иначе (строка занята);

• если значение ключа совпало с искомым, поиск заканчива­ется;

• иначе (значение не совпало) – проверяются следующие стро­ки до строки с нужным ключом – строка найдена или до пус­той строки – строка отсутствует.

Подробнее о методах хеширования см. – Литература.

1. Кнут Д. Искусство программирования, т.3. М.: Вильямс, 2000.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Вильямс, 2000.

3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2001.

4. Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985.

5. Керниган Б., Пайк Р. Практика программирования. СПб.: Невский диалект, 2001.

11