Хеширование

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

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

В идеальном случае существует взаимно однозначное соответствие между значениями ключей и множеством адресов таблицы. Пусть, например, элементы таблицы содержат информацию о владельцах внутренних телефонов некоторой организации. Номер телефона состоит из 3 цифр. Тогда достаточно иметь таблицу размером 1000 записей, в которой адрес элемента равен номеру телефона. Однако на практике так случается редко. Если в этом примере номера телефонов не являются внутренними и состоят из 6 цифр, то таблица должна иметь 10⁶ записей и будет почти незаполнена.

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

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

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

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

Среди универсальных способов построения хеш-функции можно назвать метод середины квадрата, предложенный еще фон Нейманом для построения последовательностей псевдослучайных чисел. Метод основан на том, что при возведении в квадрат все цифры целого числа в двоичной системе счисления дают свой вклад в значения средних цифр. Если для числа выделяется N разрядов, то его квадрат имеет разрядность 2N, и значения N средних разрядов дает очередное псевдослучайное число. Зная размер таблицы, легко привести каждое полученное значение в имеющийся диапазон адресов. Мы выберем для примеров другую распространенную хеш-функцию вида H(k) = k mod N, где k-значение ключа, N-размер таблицы, H(k)-полученное значение адреса.

Пусть выполняется размещение элементов в таблице, и для очередного элемента с ключом k получен адрес h₀ = k mod N. Рассмотрим методы разрешения коллизий при хешировании.

Простейшим методом разрешения коллизий является метод линейной пробы. Если ячейка таблицы с адресом h₀ занята, то применяется функция повторного хеширования h_i = (h₀+i) mod N, где i – номер попытки размещения элемента.

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

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

Другим способом разрешения коллизий является метод квадратичной пробы, для которого функция повторого хеширования имеет вид h_i = (h₀+i²) mod N. Этот метод не приводит к эффекту скучивания, но менее эффективен по памяти. Возможна ситуация, когда свободные ячейки в таблице имеются, но не могут быть найдены при повторном хешировании. Обычно максимально допустимое число попыток размещения элемента при использовании этого метода определяется некоторой константой или зависит от размера таблицы. Впрочем, если N-простое число, то гарантируется заполнение таблицы хотя бы наполовину. Действительно, если h_j = h_i, то j²= i² mod N или (j+i)(j-i)=0 mod N, то есть (j+i)(j-i)=cN. Считая j>i, можно сделать вывод, что j>N/2, то есть ситуация встретилась после N/2 попыток размещения элемента, во время которых места в таблице оказывались занятыми. Иными словами, ситуация возможна, когда не менее половины таблицы занята.

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

Для достижения высокой скорости хеширования рекомендуется резервировать память в таблице с запасом 10-50 % от ожидаемого числа элементов.

Рассмотрим простой пример хеширования с квадратичным апробированием. В качестве таблицы используется массив.

Program Heshir;

Uses Crt;

Const

P=13; { простое число }

Raz=5; { число попыток поиска }

Type

index=0..P-1;

word=record

Key: integer;

Count: integer; { число включений }

end;

Var

T: array[0..P-1] of word; { массив для расстановки }

K: integer; { ключ поиска }

Ind, H: index;

I, Kolz: integer; { количество записей в таблице }

B: boolean;

Procedure Search(K:integer; var Ind: index);

{ возвращает индекс, по которому размещен элемент }

Begin

if Kolz>=P then

begin

WriteLn('Таблица переполнена !');

Exit

end;

H:=K mod P;

For I:=1 to Raz do

begin

WriteLn('Печать перед обработкой записи: ');

WriteLn('H=', H, ' Count=', T[H].count);

WriteLn('Количество записей(Kolz): ', Kolz);

if (K=T[K].Key) or (T[K].Count=0) then

{ нашли ключ или пустое место в таблице }

begin

T[H].Count:=T[H].Count+1;

if T[H].Count=1 then { запись впервые }

Kolz:=Kolz+1;

T[H].Key:=K;

Ind:=H;

Exit

end

else

H:=(H+I*I) mod P

end;

WriteLn('За ', Raz, ' попыток не нашли записи и места в таблице !')

End;

Begin

ClrScr;

For I:=0 to P-1 do

T[I].Count:=0;

Kolz:=0;

B:=True;

While B do

begin

Write('Введите очередной ключ (-1 - конец) ');

ReadLn(K);

if K<>-1 then

begin

Search(K, Ind);

WriteLn

end

else

B:=False

end;

End.

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

Вирт приводит следующие данные о среднем числе попыток размещения элемента в зависимости от степени заполнения таблицы, полученные теоретическим путем.

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

Program Heshirov;

Uses Crt;

Const

M=977; { размер таблицы - простое число }

Lim=500; { предельное число попыток размещения в таблице }

Num=20; { число опытов заполнения таблицы от 0 до 95 % }

Type

field=record

Key:word; { ключ размещаемой записи }

Flag:boolean { TRUE - место в таблице свободно }

end;

tsize=0..M-1;

table=array [0..M-1] of field;

result=array[ 0..100] of real;

count=array[0..100] of integer;

Var

T:table; { заполняемая таблица }

H:tsize; { индекс в таблице }

I, J, A: integer;

K, N: word;

R: result; { результаты по процентам }

C: count; { счетчики числа хеширования по процентам }

Begin

TextBackground(3);

ClrScr;

TextColor(14);

TextBackground(0);

GoToXY(35,3);

Writeln('ХЕШИРОВАНИЕ');

TextColor(11); { цвет символов }

TextBackground(0); { цвет фона }

GoToXY(6,4);

Write('Зависимость числа квадратичных проб от коэффициента',

' заполнения таблицы');

For A:=0 to 100 do

begin

R[A]:=0;

C[A]:=0

end;

For J:=1 to Num do

begin

N:=0; { счетчик числа удачных размещений }

For H:=0 to M-1 do { очистка таблицы }

T[h].Flag:=True;

Randomize; { случайная инициализация для Random }

Repeat

I:=0;

K:=Random(65000); { случайный ключ }

H:=K mod M; { приведение в диапазон 0 - M-1 }

While not (T[H].Flag and (T[H].Key<>K) and (I<Lim)) do

{ пока не найдено свободное место }

{ ключи без повторения, попыток не более Lim }

begin

Inc(I);

H:=(K+I*I) mod M

end;

if T[H].Flag then { найдено свободное место }

begin

Inc(N);

T[H].Key:=K;

T[H].Flag:=False { признак заполнения }

end;

A:=Round(N/M*100); { процент заполнения таблицы }

R[A]:=R[A]+I+1; { всего попыток для этого процента }

Inc(C[A]) { число размещаемых записей }

Until A>=95 { заполнение таблицы идет до 95 % }

end;

For A:=0 to 95 do

R[a]:=R[A]/C[A]; { среднее число попыток }

TextColor(13);

TextBackground(1);

GoToXY(1,10); { начало строки 10 }

{ выдача рамки таблицы с результатами }

Write('-');

For I:=1 to 19 do

if R[5*I]>10 then Write('----T')

else Write('---T');

Write(#8,''); { #8 - возврат назад на 1 позицию }

GoToXY(1,12);

Write('+');

For I:=1 to 19 do

if R[5*I]>10 then Write('----+')

else Write('---+');

Write(#8,'+');

GoToXY(1,11);

Write('¦');

GoToXY(1,13);

Write('¦');

{ заполнение строки процентов (от 5 до 95 с шагом 5) }

GoToXY(2,11);

For I:=1 to 19 do

if R[5*I]>10 then Write(' ',5*I:2,'%¦')

else Write(5*I:2,'%¦');

{ выдача конечных результатов }

GoToXY(2,13);

For I:=1 to 19 do

if R[5*I]>10 then Write(R[5*I]:4:1,'¦')

else Write(R[5*I]:3:1,'¦');

{ завершение прорисовки рамки }

GoToXY(1,14);

Write('L');

For I:=1 to 19 do

if R[5*I]>10 then Write('----+')

else Write('---+');

Write(#8,'-');

TextColor(10);

TextBackground(4);

GoToXY(4,23);

Write('Press any key...');

Repeat

Until KeyPressed { ожидание до нажатия клавиши }

End.