Хеширование. Метод повторного хеширования. Разрешение коллизий методом цепочек

Страницы работы

Содержание работы

Лекция 8. ХЕШИРОВАНИЕ.

При рассмотрении процедур поиска обычно предполагается, что запись для которой организуется поиск хранится в некоторой таблице, и нахождение нужной записи сводится к просмотру некоторого количества значений ключевых полей. Организация файла  и порядок, в котором вставляются ключи, определяют то число проверок, которые должны быть выполнены для получения нужной записи. Очевидно, что эффективными методами поиска, являются те, которые минимизируют число таких сравнений. В идеале требуется такая организация таблицы, при которой не было бы ненужных сравнений.

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

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

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

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

481137 -> 137;

481934 -> 934.

Функция, которая трансформирует значение ключа записи в некоторый значение индекса элемента массива для хранения записей называется хеш -функцией h(key). В приведенном выше примере

h(key) =  key mod 1000.

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

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

-  чем больше массив, тем менее эффективно используется память ЭВМ;

-  увеличение массива уменьшает возможность коллизий, а следовательно уменьшает время на размещение и поиск нужной записи.

Для разрешения коллизий могут использоваться два качественно различных метода: метод повторного хеширования (метод открытой адресации)  и метод цепочек.

Метод повторного хеширования.

Примером повторного хеширования является метод линейного опробования, при котором при возникновении коллизии запись помещается в следующую свободную позицию. То есть функция  rh (i) повторного хеширования имеет вид

rh(i) = (i+1) mod 1000, где i позиция в массиве, на которую претендовала запись до повторного хешированияю В частности, на первом шаге

rh(h(key)) = h(key) + 1 .

В общем случае для повторного хеширования rh воспринимает одно значения индекса в массиве и выдает следующее значение индекса. Если ячейка rh(h(key)) уже занята, то преобразование полученного индекса выполняется еще раз и проверяется позиция массива с номером   rh(rh(h(key))). Процесс продолжается до тех пор, пока не будет найдена пустая ячейка. Данный цикл может оказаться бесконечным по двум возможным причинам:

-  массив может быть заполненным, так что вставить какое-либо новое значение невозможно;

Похожие материалы

Информация о работе