Хеширование

На сегодняшнем занятии мы продолжим тему поиска.

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

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

Если каждый ключ должен быть извлечен за один доступ, то положение записи внутри такой таблицы может зависеть только от данного ключа. Оно не может зависеть от расположения других ключей, как это имеет место в дереве. Наиболее эффективным способом организации такой таблицы является массив.
Предположим, что фирма некоторая фирма выпускает детали и кодирует их семизначными цифрами. Для применения прямой индексации с использованием полного семизначного ключа потребовался бы массив из 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;

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

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

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

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

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

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;

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