2018-01-08
2783
Хеширование
На сегодняшнем занятии мы продолжим тему поиска.
На прошлом занятии мы рассмотрели, что запись, для которой организуется поиск, хранится в некоторой таблице и что прежде, чем найти требуемую запись, необходимо организовать просмотр некоторого количества ключей.
Очевидно, что эффективными методами поиска являются те методы, которые минимизируют число этих сравнений. В идеале мы бы хотели иметь такую организацию таблицы, при которой не было бы ненужных сравнений. Посмотрим, возможна ли такая организация.
Если каждый ключ должен быть извлечен за один доступ, то положение записи внутри такой таблицы может зависеть только от данного ключа. Оно не может зависеть от расположения других ключей, как это имеет место в дереве. Наиболее эффективным способом организации такой таблицы является массив.
Предположим, что фирма некоторая фирма выпускает детали и кодирует их семизначными цифрами. Для применения прямой индексации с использованием полного семизначного ключа потребовался бы массив из 100 млн. элементов. Ясно, что это привело бы к потере неприемлемо большого пространства, поскольку совершенно невероятно, что какая-либо фирма может иметь больше чем тысяча наименований изделий. Поэтому необходим некоторый метод преобразования ключа в какое-либо целое число внутри ограниченного диапазона.
|
|
|
Тогда для хранения всего файла будет достаточно массива из 1000 элементов. Этот массив индексируется целым числом в диапазоне от 0 до 999 включительно. В качестве индекса записи об изделии в этом массиве используются три последние цифры номера изделия.
|
Рис. Записи о деталях
Отметим, что два ключа, которые близки друг к другу как числа (такие как 4618396 и 4618996), могут располагаться дальше друг от друга в этой таблице, чем два ключа,. которые значительно различаются как числа (такие как 0000991 и 9846995). Это происходит из-за того, что для определения позиции записи используются только три последние цифры ключа.
Хеширование - это способ сведения хранения одного большого множества к более меньшему.
Функция, которая трансформирует ключ в некоторый индекс в таблице, называется хеш-функцией.
В данном случае h(key):= key mod 1000;
Хеш-таблица - это обычный массив с необычной адресацией, задаваемой хеш-функцией.{см. рисунок}
Этот метод имеет один недостаток. Давайте добавим в таблицу запись с ключом 0596397. Увидим, что данная ячейка уже занята.
Ситуация, когда два или более ключа ассоциируются с одной и той же ячейкой называется коллизией при хешировании.
Следует отметить, однако, что хорошей хеш-функцией является такая функция, которая минимизирует коллизии и распределяет записи равномерно по всей таблице.
|
|
|
Совершенная хеш-функция - эта функция, которая не порождает коллизий.
Разрешить коллизии при хешировании можно 2 методами:
1. методом открытой адресации
2. методом цепочек
Разрешение коллизий при хешировании методом цепочек
Он представляет собой организацию связанного списка из всех записей, чьи ключи хешируются в одно и то же значение.
75 66 42 192 91 40 49 87 67 16 417 130 372 227
|
Рис. Разрешение коллизий при хешировании методом цепочек.
type
link = ^node;
node = record
key: integer;
st: string;
next: link;
end;
var
mas: array[0..9] of link;
function h(key: integer): integer;
begin
h:=key mod 10;
end;
function search(key1: integer; st1: string): link;
var
i: integer;
q, p, s: link;
begin
i:= h(key1);
q:=nil;
p:=mas[i];
while p <> nil do
begin
if p^.key = key1 then
begin
search:=p;
exit;
end;
q:= p;
p:= p^.link;
end;
{Если ключ не найден, вставляем новую запись}
new(s);
s^.key:=key1;
s^.st:=st1;
s^.next:=nil;
if q = nil then
mas[i]:=s
else
q^.next:=s;
search:=s;
end;
Удаление узла из таблицы, которая построена по методу цепочек, заключается просто в исключении узла из связанного списка. Удаленный узел никак не влияет на эффективность алгоритма поиска. Алгоритм будет работать так, как если бы этот узел никогда не вставлялся в таблицу. Отметим, что эти списки могут быть динамически переупорядочены для получения большей эффективности поиска.
Основным недостатком метода цепочек является то, что для узлов указателей требуется дополнительное пространство.
Выбор хеш-функции
Обратимся теперь к вопросу о том, как выбрать хорошую хеш-функцию. Ясно, что эта функция должна создавать как можно меньше коллизий при хешировании, т.е. она должна равномерно распределять ключи на имеющиеся индексы в массиве. Конечно, нельзя определить, будет ли некоторая конкретная хеш-функция распределять ключи правильно, если эти ключи заранее не известны. Однако, хотя до выбора хеш-функции редко известны сами ключи, некоторые свойства этих ключей, которые влияют на их распределение, обычно известны.
1. метод деления. Некоторый целый ключ делится на размер таблицы и остаток от деления берется в качестве значения хеш-функции. Эта хеш-функция обозначается h (key):= key mod m.
2. метод середины квадрата. Ключ умножается сам на себя и в качестве индекса используется несколько средних цифр этого квадрата.
Function h(key: integer): integer;
Begin
Key:=key*key; {Возвести в квадрат}
Key:=key shl 11;{Отбросить 11 младших бит}
H:= key mod 1024;{Возвратить 10 младших бит}
End;
3) Аддитивный метод для строк (размер таблицы равен 256). Для строк вполне разумные результаты дает сложение всех символов и возврат остатка от деления на 256.
Function h(st: string): integer;
Var
Sum: longint;
I: integer;
Begin
For i:=0 to length(st) do
Sum:= sum + ord(st[i]);
H:=sum mod 256;
End;
4) Исключающее ИЛИ для строк (размер таблицы равен 256). Этот метод аналогичен аддитивному, но успешно различает схожие слова и анаграммы (аддитивный метод даст одно значение для XY и YX). Метод заключается в том, что к элементам строки последовательно применяется операция "исключающее или". В алгоритме добавляется случайная компонента, чтобы еще улучшить результат.
var
rand8: array[0..255] of integer;
procedure init;
var
i: integer;
begin
randomize;
for i:=0 to 255 do
rand8[i]:=random(255);
end;
function h(st: string): integer;
Var
Sum: longint;
I: integer;
Begin
For i:=0 to length(st) do
Sum:= sum + ord(st[i]) xor rand8[i];
H:=sum mod 256;
end;
