Алгоритмы и структуры данных

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

В качестве хеш-функции также применяют функцию преобразования системы счисления. Ключ, записанный как число в некоторой системе счисления P, интерпретируется как число в системе счисления Q > P. Обычно выбирают Q = P+1. Это число переводится из системы Q обратно в систему P, приводится к размеру пространства записей и интерпретируется как адрес.

2.3.2.2. Открытое хеширование

Основная идея базовой структуры при открытом (внешнем) хешировании (рис. 28) заключается в том, что потенциальное множество (возможно, бесконечное) разбивается на конечное число классов. Для В классов, пронумерованных от 0 до В - 1, строится хеш-функция h(x) такая, что для любого элемента х исходного множества функция h^) принимает целочисленное значение из интервала 0, В - 1, соответствующее, естественно, классу, которому принадлежит элемент х. Часто «классы» называют сегментами, поэтому будем говорить, что элемент х принадлежит сегменту h^).

Массив, называемый таблицей сегментов и проиндексированный номерами сегментов 0, 1, ... , B - 1, содержит заголовки для B списков. Элемент х i-го списка - это элемент исходного множества, для которого h(x) = i.

Если сегменты примерно одинаковы по размеру, то в этом случае списки всех сегментов должны быть наиболее короткими при данном числе сегментов. Если исходное множество состоит из N элементов, тогда средняя длина списков будет N/B элементов. Если можно оценить величину N и выбрать В как можно ближе к этой величине, то в каждом списке будет один-два элемента. Тогда время выполнения операторов словарей будет малой постоянной величиной, не зависящей от N (или, что эквивалентно, от B).

Рис. 28. Организация данных при открытом хешировании

Рассмотрим алгоритмы основных операций с хеш-таблицей, при открытом хешировании. В этих алгоритмах будем использовать структуры данных и операции с линейными однонаправленными списками, которые были описаны в 1.2.6.1. Поле Data в элементах списка будет здесь исполнять роль ключа, а роль указателя на список ptrHead будет играть элемент хеш-таблицы:

Const

В = {подходящая константа}; type

HtableOpen = array[0..B-1]  of Pelement;

Кроме того, здесь используется предопределенная функция h(x), которая и является собственно реализацией хеш-функции:

Procedure Clear HtableOpen(var A: HtableOpen);

{Процедура очистки хеш-таблицы}

var

IndexSeg:  integer; begin

for IndexSeg:=0 to B-1 do while A[IndexSeg]  <> nil do

Del LineSingleList(A[IndexSeg], A[IndexSeg]);

end;

function Find HtableOpen(x: TypeData;

var A: HtableOpen;

var current: Pelement): boolean; {функция поиска элемента x в хеш-таблице. Принимает значение true, если найден и возвращает указатель, который устанавливается на найденный элемент, или принимает значение false и возвращает nil} var

IndexSeg: integer;    {номер сегмента} begin

IndexSeg := h(x);

{начало списка, в котором надо искать, это A[IndexSeg]} if Find LineSingleList(x, A[IndexSeg], current)  then

Find HtableOpen := true else

Find HtableOpen := false;

end;

procedure Add HtableOpen(x: TypeData;    var A: HtableOpen);

{Процедура добавления элемента x в хеш-таблицу}

var

IndexSeg: integer;    {номер сегмента} current: Pelement; begin

if not Find HtableOpen(x, A, current) then begin {Если в таблице элемент уже есть, то добавлять не надо} IndexSeg := h(x);

{Добавляем всегда в начало списка} InsFirst LineSingleList(x, A[IndexSeg]); end end;

procedure Del HtableOpen(x: TypeData;    var A: HtableOpen);

{Процедура удаления элемента x из хеш-таблицы}

var

IndexSeg: integer;    {номер сегмента} current: Pelement; begin

if Find HtableOpen(x, A, current) then begin {Если в таблице элемент еще есть, то удаляем} IndexSeg := h(x);

Del LineSingleList(A[IndexSeg], current);

end; end;

Если есть B сегментов и N элементов, хранящихся в хеш-таблице, то каждый сегмент в среднем будет иметь N/B элементов и можно ожидать, что операции добавления, поиска и удаления будут выполняться в среднем за время, пропорциональное 0(1+N/B). Здесь константа 1 соответствует поиску сегмента, а N/B - поиску элемента в сегменте. Если B примерно равно N, то время выполнения операторов становится константой, независящей от N.

2.3.2.3. Закрытое хеширование

При закрытом (внутреннем) хешировании в хеш-таблице хранятся непосредственно сами элементы, а не заголовки списков элементов. Поэтому в каждой записи (сегменте) может храниться только один элемент. При закрытом хешировании применяется методика повторного хеширования. Если осуществляется попытка поместить элемент х в сегмент с номером h(x), который уже занят другим элементом (такая ситуация называется коллизией), то в соответствии с методикой повторного хеширования выбирается последовательность других номеров сегментов h1(x), h2(x), куда можно поместить элемент х. Каждое из этих местоположений последовательно проверяется, пока не будет найдено свободное. Если свободных сегментов нет, то, следовательно, таблица заполнена, и элемент х добавить нельзя.

При поиске элемента х необходимо просмотреть все местоположения h(x), h₁ (x), h₂(x), ... , пока не будет найден х или пока не встретится пустой сегмент. Чтобы объяснить, почему можно остановить поиск при достижении пустого сегмента, предположим, что в хеш-таблице не допускается удаление элементов. И пусть, для определенности, h3(x) - первый пустой сегмент. В такой ситуации невозможно нахождение элемента х в сегментах h4(x), h5(x) и далее, так как при вставке элемент х вставляется в первый пустой сегмент, следовательно, он находится где-то до сегмента h₃(x).

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

Существует несколько методов повторного хеширования, т. е. определения местоположений h(x), h₁(x), h₂(x), ... :

• линейное опробование;
• квадратичное опробование;
• двойное хеширование.

Линейное опробование (рис. 29, а) сводится к последовательному перебору сегментов таблицы с некоторым фиксированным шагом:

адрес = h(x) + c-i ,

где i - номер попытки разрешить коллизию; c - константа, определяющая шаг перебора. При шаге, равном единице, происходит последовательный перебор всех сегментов после текущего.

Квадратичное опробование (рис. 29, б) отличается от линейного тем, что шаг перебора сегментов нелинейно зависит от номера попытки найти свободный сегмент:

адрес = h(x) + c-i + d-i²,

где i - номер попытки разрешить коллизию, c и d - константы.

Благодаря нелинейности такой адресации уменьшается число проб при большом числе ключей-синонимов.

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

Еще одна разновидность метода открытой адресации, которая называется двойным хешированием (рис. 29, в), основана на нелинейной адресации, достигаемой за счет суммирования значений основной и дополнительной хеш-функций

адрес = h₁(x) + i-h₂(x).

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

Однако в случае многократного превышения адресного пространства и, соответственно, многократного циклического перехода к началу будет происходить просмотр одних и тех же ранее занятых сегментов, тогда как между ними могут быть еще свободные сегменты. Более корректным будет использование сдвига адреса на 1 в случае каждого циклического перехода к началу таблицы. Это повышает вероятность нахождения свободных сегментов.

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

Const

В = {подходящая константа};

empty = ^л л;       {10 пробелов}

deleted = {10 символов *}

c = 1;    {шаг перебора}

MaxCase = {подходящая константа};    {Max количество попыток} type

TypeElem = string[10]

HTableClose = array[0..B-1]  of TypeElem;

Теперь приведем сами алгоритмы на примере линейного опробования. Для остальных методов повторного хеширования алгоритмы идентичны:

procedure Clear HTableClose(var A: HTableClose);

{Процедура очистки хеш-таблицы}

var

IndexSeg: integer; begin

for IndexSeg:=0 to B-l do A[IndexSeg]   := empty; end;

function Find HTableClose(x: TypeElem;

var A: HTableClose; var IndexSeg: integer): boolean; {функция поиска элемента x в хеш-таблице. Принимает значение true, если найден элемент, и возвращает номер сегмента, в котором располагается найденный элемент, или принимает значение false и возвращает 0} var

i: integer; begin

i := 0;

repeat

IndexSeg := ((h(x) + c*i) mod B +   {лин.опр.с цикл.переходом} 
(h(x) + c*i) div B   )  {смещение после перехода} 
mod B; {ограничение смещения}

i := i + 1;

until (A[IndexSeg] = x) or {нашли}

(A[IndexSeg] = empty) or       {дальше уже нет} 
(i > MaxCase); {слишком долго ищем}

if A[IndexSeg] = x then begin

Find_HTableClose := true; end else begin

Find_HTableClose := false; IndexSeg := 0;

end; end;

function Add HTableClose(x: TypeElem;

var A: HTableClose): boolean; {Процедура добавления элемента x в хеш-таблицу. Возвращает true, если элемент добавлен, и false - в обратном} var

i,

IndexSeg: integer;    {номер сегмента} begin

if not Find HTableClose(x, A, IndexSeg) then begin {Если в таблице элемент уже есть, то добавлять не надо}

i := 0;

repeat

IndexSeg := ((h(x) + c*i) mod B + (h(x) + c*i) div B   ) mod B;

i := i + 1;

until (A[IndexSeg] = empty) or       {нашли место}

(A[IndexSeg] = deleted) or   {тоже можно занять} 
(i > MaxCase); {слишком долго ищем}

if (A[IndexSeg] = empty) or

(A[IndexSeg] = deleted) then begin A[IndexSeg]   := x; Add_HTableClose := true; end else begin

Add_HTableClose := false; end; end end;

procedure Del HTableClose(x: TypeElem;   var A: HTableClose);

{Процедура удаления элемента x из хеш-таблицы}

var

IndexSeg: integer;    {номер сегмента} begin

if Find HTableClose(x, A, IndexSeg) then begin {Если в таблице элемент уже нет, то удалять не надо}

A[IndexSeg]   := deleted; end end;

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

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

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

В этом случае вероятность коллизий равна B/N. Не приводя дальнейших доказательств, отметим, что среднее число проб на один сегмент при заполнении M сегментов равно (B/M)ln(B/(B - M + 1)). Таким образом, для полного заполнения таблицы (M = B) требуется в среднем ln B проб на один сегмент, или всего Bln B проб.

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

2.3.2.4. Реструктуризация хеш-таблиц

При использовании открытых хеш-таблиц среднее время выполнения операторов возрастает с ростом параметра N/В и особенно быстро растет при превышении числа элементов над числом сегментов. Подобным образом среднее время выполнения операций также возрастает с увеличением параметра N/В и для закрытых хеш-таблиц (но превышение N над В здесь невозможно).

Чтобы сохранить постоянное время выполнения операторов, которое теоретически возможно при использовании хеш-таблиц, можно предложить при достижении N достаточно больших значений, например при N > 0,9B для закрытых хеш-таблиц и N > 2В - для открытых хеш-таблиц, просто создавать новую хеш-таблицу с удвоенным числом сегментов. Перезапись текущих элементов множества в новую хеш-таблицу в среднем займет меньше времени, чем их ранее выполненная вставка в старую хеш-таблицу меньшего размера. Кроме того, затраченное время на перезапись компенсируется более быстрым выполнением всех операций.