Разрешение коллизий - Динамическое хеширование

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

Метод цепочек

Метод цепочек - самый очевидный путь решения проблемы. В случае, когда элемент таблицы с индексом, который вернула хеш-функция, уже занят, к нему присоединяется связный список. Таким образом, если для нескольких различных значений ключа возвращается одинаковое значение хеш-функции, то по этому адресу находится указатель на связанный список, который содержит все значения. Поиск в этом списке осуществляется простым перебором, т. к. при грамотном выборе хеш-функции любой из списков оказывается достаточно коротким. Но даже здесь возможна дополнительная оптимизация. Дональд Кнут ([3], стр. 558) отмечает, что возможна сортировка списков по времени обращения к элементам. С другой стороны, для повышения быстродействия желательны большие размеры таблицы, но это приведет к ненужной трате памяти на заведомо пустые элементы. На рисунке ниже показана структура хеш-таблицы и образование цепочек при возникновении коллизий.

Прекрасная наглядная иллюстрация этой схемы разрешения коллизий в виде Java-апплета вместе с исходным кодом на C++ представлена по адресу [14].

Открытая адресация

Другой путь решения проблемы, связанной с коллизиями, состоит в том, чтобы полностью отказаться от ссылок, просто просматривая различные записи таблицы по порядку до тех пор, пока не будет найден ключ K или пустая позиция [3]. Идея заключается в формулировании правила, согласно которому по данному ключу определяется "пробная последовательность", т. е. последовательность позиций таблицы, которые должны быть просмотрены при вставке или поиске ключа K. Если при поиске встречается пустая ячейка, то можно сделать вывод, что K в таблице отсутствует, т. к. эта ячейка была бы занята при вставке, т. к. алгоритм проходил ту же самую цепочку. Этот общий класс методов назван открытой адресацией [4].

Похожие статьи




Разрешение коллизий - Динамическое хеширование

Предыдущая | Следующая