double arrow

Хеширование с открытой адресацией. Способы разрешения коллизий. Анализ эффективности.

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

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

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

Тогда для хранения всего файла будет достаточно массива из 1000 элементов. Этот массив индексируется целым числом в диапазоне от 0 до 999 включительно. В качестве индекса записи об изделии в этом массиве используются три последние цифры номера изделия.

Рис. Записи о деталях

Отметим, что два ключа, которые близки друг к другу как числа (такие как 4618396 и 4618996), могут располагаться дальше друг от друга в этой таблице, чем два ключа,. которые значительно различаются как числа (такие как 0000991 и 9846995). Это происходит из-за того, что для определения позиции записи используются только три последние цифры ключа.

Хеширование - это способ сведения хранения одного большого множества к более меньшему.

Функция, которая трансформирует ключ в некоторый индекс в таблице, называется хеш-функцией.

В данном случае h(key):= key mod 1000;

Хеш-таблица - это обычный массив с необычной адресацией, задаваемой хеш-функцией.{см. рисунок}

Этот метод имеет один недостаток. Давайте добавим в таблицу запись с ключом 0596397. Увидим, что данная ячейка уже занята.

Ситуация, когда два или более ключа ассоциируются с одной и той же ячейкой называется коллизией при хешировании.

Следует отметить, однако, что хорошей хеш-функцией является такая функция, которая минимизирует коллизии и распределяет записи равномерно по всей таблице.

Совершенная хеш-функция - эта функция, которая не порождает коллизий.
Разрешить коллизии при хешировании можно 2 методами:

1. методом открытой адресации

2. методом цепочек

Разрешение коллизий при хешировании методом открытой адресации.

Посмотрим, что произойдет, если мы захотим ввести в таблицу некоторый новый номер изделия 0596397. Используя хеш-функцию h(key):=key mod 1000, мы найдем, что h (0596397) =397 и что запись для этого изделия должна находиться в позиции 397 в массиве. Однако позиция 397 уже занята, поскольку там находится запись с ключом 4957397. Следовательно, запись с ключом 0596397 должна быть вставлена в таблицу в другом месте.

Самым простым методом разрешения коллизий при хешировании является помещение данной записи в следующую свободную позицию в массиве. Например, запись с ключом 0596397 помещается в ячейку 398, которая пока свободна, поскольку 397 уже занята. Когда эта запись будет вставлена, другая запись, которая хешируется в позицию 397 (с таким ключом, как 8764397) или в позицию 398 (с таким ключом, как 2194398), вставляется в следующую свободную позицию, которая в данном случае равна 400.

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

Var
K: array [0...999] of integer;

Function h(key: integer): integer;
Begin
h:= key mod 1000;
End;

Function rh(i: integer): integer;
Begin
rh:=i+1 mod 1000;
End;

Procedure insert(key: integer);
Var
I: integer;
begin
I:= h(key); {хешируем ключ}
while ((k(i)< >key) and (k(i)< >0)) do
i:= rh(i); {мы должны выполнить повторное хеширование}
if k(i) =0 then {вставляем запись в пустую позицию}
k(i)=key
end;

Недостатки метода.

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

Во -вторых, из такой таблицы трудно удалить запись

 

Var

K: array [0...999] of integer;

 

Function h(key: integer): integer;

Begin

h:= key mod 1000;

End;

 

Function rh(i: integer): integer;

Begin

rh:=i+1 mod 1000;

End;

 

Procedure insert(key: integer);

Var

I: integer;

begin

I:= h(key); {хешируем ключ}

while ((k(i)< >key) and (k(i)< >0)) do

i:= rh(i); {мы должны выполнить повторное хеширование}

if k(i) =0 then {вставляем запись в пустую позицию}

k(i)=key

end;

 


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: