Хеш-таблицы.

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

Введение

Начать, наверно, нужно с самого определения хеширования и хеш-таблиц.
Хешированием называется преобразование ключа элемента в значение индекса, выполняется данный процесс при помощи функции хеширования. Эта функция определяет местоположение элемента в таблицы на основе значения данного элемента.
Хеш-таблица, соответственно, массив, используемый для хранения элементов, с которым используется значения индекса.
Для того что бы лучше понять предназначение хеш-таблиц, давайте вспомним алгоритмам поиска в отсортированном массиве. Там функция делала предположение о возможном местонахождении элемента, и если получала положительный результат, то возвращала индекс элемента, если же найденный ключ не являлся нужным, то делалось следующее предположение уже с учётом, предыдущего. В хеш-таблице, мы будем заранее определять местоположение элемента, чтобы при необходимости его найти, мы не тратили много времени на перебор всех значений, а находили элемент с первой попытки, однако следует отметить, что это бывает возможно не всегда. В лучшем варианте время выполнения будет равно О(1) в худшем О(n), где n - это количество элементов в таблице.
Итак, рассмотрим следующий случай. Предположим, что нам надо разместить числа от 1 до 1000 в хеш-таблице. Для начала вы создаёте массив длинной 1000 элементов и каждое его значение устанавливаете равным нулю. Теперь для того, чтобы добавить в таблицу число 112, вы находите соответствующий элемент в таблице и присваиваете ему значение равное 112. Чтобы найти, вставленный элемент вам надо всего лишь обратиться к нужной записи в массиве. Таким образом вы сможете вставлять, удалять и находить нужные элементы всего за один шаг.
К сожалению, в реальной жизни значения чисел намного больше, чем в рассмотренном выше примере и выделить для массива необходимую память не всегда будет рационально. Так например, если у нас есть 10 000 чисел в пределе от 0 до десяти миллиардов, то создавать таблицу с таким количеством элементов будет не то что не актуально, но по крайней мере глупо. И если бы нам удалось взглянуть на такой массив, то он оказался бы пустым больше чем на 99%.
Избежать подобной ситуации и найти наиболее оптимальное отношение длины таблицы к количеству записей в ней позволяет специальная хеш функция. Если в вашей фирме 300 работников и вы хотите сохранить личный номер каждого, то можете объявить массив из 450 элементов, куда и внести все данные. Но почему именно 450, ведь можно было бы создать хеш-таблицу из 300, куда тоже всё поместиться. Однако на практике оказывается, что чем больше пустых ячеек в хеш таблице тем больше её производительность, наилучшим соотношением считается 2 : 3, или на две заполненные ячейки одна пустая. Но никто вам не мешает поэкспериментировать и с другим коэффициентом загруженности.
Ещё одна проблема, с которой мы столкнёмся, это то что у двух различных ключей значение хеша совпадут и возникнет так называемая конфликтная ситуация
Из всего вышесказанного, становиться ясно, для того чтобы построить полноценную хеш-таблицу нужно два алгоритма, первый, это сам алгоритм хеширования, а второй алгоритм для разрешения возможных конфликтных ситуации. По понятным причинам, нам придётся производить и ряд других действий: вставлять, удалять, искать элементы или выяснять их отсутствие. Хеш-таблица позволяют делать это очень быстро, если конечно она не перегружена элементами. Всё это мы и рассмотрим с данной статье, но алгоритм который необходимо рассмотреть в первую очередь это хеширование.

Функции хеширования.

Этой функцией будем называть подпрограмму, которая будет принимать значение ключа и возвращать его хеш. Притом, если у нас таблица состоит из n элементов, то хеш должен быть в пределах от 0 до n-1. Очевидно, что возвращаемое значение должно быть целым не отрицательным число. Однако о типе данных, которые будут передаваться в функцию пока ничего, не говорилось, и действительно они могут быть любые.
Функция хеширования должна для похожих элементов, создавать разные значения хеша, внешне совершенно не похожие на исходный результат. Иными словами функция хеширования должна быть подобна функции генерации случайного числа и к тому же универсальна.
Простейшим случаем будет нахождения хеша от простого числа. Самое первое что приходит на ум в этом случае это использование оператора деления по модулю. В случае, если таблица содержит n значений и надо туда добавить число k, то необходимо найти значение k mod n и если оно отрицательное, то прибавить n. Для того чтобы элементы были распределены более однородно в качестве длинны таблицы нужно использовать простое число.
Но как поступать, если значение индекса является не числом, а скажем строкой? Для этого необходимо преобразовать строку в целочисленное значение и после чего использовать полученное число для деления по модулю. Самый простой способ это получить длину строки, однако у него есть свой недостаток. Так как, большинство слов состоят из 4-12 букв, то это повлечет за собой появление большого количество повторяющихся значений хеша и как следствие снижение производительности всей таблицы, что недопустимо для серьёзных проектов. Вследствие чего необходимо как-то изменить функцию хеширования.
Более лучший результат даст функция, которая для деления по модулю использует сумму всех ASCII-значения слова. Данная функция называется простой функцией хеширования.

Простая функция хеширования.

Как и было сказано выше подпрограмма будет получать в качестве параметра какое-либо слово и количество элементов таблицы, а в итоге мы будем получать хеш этого слова.


function SimpleHashFunc(Key: string; HTableHigh: integer): integer;
var
Hash: longint;
i: integer;
begin
Hash:=0;
for i:=0 to length(Key) do
Hash:=((Hash*19) + ord(Key)) mod HTableHigh;
Result:=Hash;
if Hash<0 then
Hash:=Hash+ HTableHigh;
end;


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

Функции хеширования PJV

Рассмотренная хеш функция на практике, даёт довольно неплохой результат, однако существует несколько других функций, которые превосходят данную по количеству производимых математических операций, и как следствие к лучшему результату.
Одной из таких функций является функция хеширования созданная П.Дж.Вейнбергером. Её также называют ELF-хешем (Executаble and Linking Format или формат исполняемых и компонуемых модулей).


function TForm1.PJWHash(const Key: String; TableHigh: Integer): integer;
var
Hash, G: Longint;
i: integer;
begin
hash:=0;
for i:=1 to length(Key) do begin
Hash:=(Hash shl 4)+ord(Key);
G:=Hash and longint($F0000000);
if (G<>0) then
Hash:=(Hash xor (G shl 24) xor G);
end;
Result:=hash mod TableHigh;
end;


И хотя код этой функции длиннее, она содержит много операций AND, XOR, MOD, которые быстро выполняются процессором. Поэтому проблем с производительностью этой функции возникнуть не должно.
Но даже столь сложная функция, может сгенерировать для различных ключей одинаковые значения хеш, поэтому алгоритм обработки конфликтов не отпадает.
Тут может возникнуть вопрос, а можно ли написать функцию которая для определённого значения ключей будет генерировать только уникальные значения. Теоретически, это возможно. Однако, как узнать что функция не возвращает повторяющихся значений? Только из практики. К тому же, если изменяться входящие значения, функция может оказаться вовсе не универсальной. Так что проще написать алгоритм обработки конфликтов, чем ломать голову над идеальной функцией хеширования.

Разрешение конфликтов посредством линейного зондирования.

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

96: пусто
97: Максим
98: пусто

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

96: пусто
97: Максим
98: Иван
99: пусто

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

Кластеры

Появление кластеров влечет за собой один неприятный эффект - снижение производительности всей таблицы, и чем их больше и они массивнее, тем больше это заметно. Поэтому очень важно иметь хорошую функцию хеширования, которая позволит сократить их появление. Однако полностью устранить их невозможно и чем таблица больше, тем больше шанс появления кластеров.
Это очень легко доказывается математически.
Предположим, что у вас есть пустая хеш таблиц из N элементов, вероятность того что первый элемент займёт любую позицию m равно 1/N. При вставке второго элемента, вероятность того что два элемента образуют кластер, будет равна сумме вероятностей, то что элемент m-1, m+1, или элемент попадёт в позицию m и займёт место m+1 или 1/N+1/N+1/N=3/N. Продолжая подобные рассуждения, найдём, что вероятность образования кластера из 3-х элементов - 5/N, из 4-х - 7/N, и так далее.
Так, например, если таблица заполнена на половину, то вероятность того что мы попадём с первого раза в незанятую ячейку 50% и вероятность, того что мы найдём свободное место со второй попытки тоже 50%. Но если в таблице один большой кластер, то вероятность попадание в пустую ячейку по-прежнему 50%, а вот если попадём в кластер, то свободное место будем искать очень долго.
Дональд Кнут в своих книгах показал, что общее количество зондирования до обнаружения свободного элемента приблизительно равно ?(1+1/(1-k), где коэффициент k есть отношения числа элементов в таблице к общему размеру таблицы.

Удаление элементов из хеш таблицы с линейным зондированием.

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

86: пусто (-)
87: Максим (87)
88: Иван (87)
89: Сергей (88)
90 пусто (-)

Теперь удалим из таблицы имя Иван, для этого как и говорилось ранее при помощи специальной функции получим его и хеш 87 и позицию в таблице 88. После чего 88 записи хеш-таблицы присвоим пустую строку. И наша таблица будет выглядеть следующим образом:

86: пусто (-)
87: Максим (87)
88: пусто (-)
89: Сергей (88)
90: пусто (-)

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

Изменение размера хеш-таблиц.

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

Практическая реализация.

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

Перед тем, как приступить к написанию вышеописанных функции, надо сделать некоторые приготовления - объявить две глобальных переменных:


HashTable: array of String;
KeyCount: Integer;


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


function TForm1.IndexOf(const key: String): Integer;
var
index, FirstIndex: Integer;
begin
index:=PJWHash(key, high(HashTable)+1);
FirstIndex:=index;
while true do begin
if HashTable[index]=′′ then begin
Result:=-1;
exit;
end
else begin
if key=HashTable[index] then begin
Result:=index;
exit;
end;
end;
index:=index+1;
if index=high(HashTable)+1 then
index:=0;
if index=FirstIndex then begin
result:=-1;
exit;
end;
end;
end;


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

Функция вставки нового элемента.

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


function TForm1.InsertK(const key: string): integer;
var
index, hashValue, i: Integer;
begin
index:=IndexOf(key);
Result:=-1;
if index<>-1 then begin
Showmessage(′Элемент уже содержится в таблице!!′);
exit;
end;
hashValue:=PJWHash(key, high(hashTable)+1);
if HashTable[hashValue]<>′′ then begin
for i:=hashValue+1 to high(HashTable) do begin
if HashTable=′′ then begin
hashValue:=i;
Break;
end;
end;
end;
HashTable[hashValue]:=key;
result:=hashValue;
KeyCount:=KeyCount+1;
if hashValue=high(HashTable) then
ResizeHTable(High(HashTable)+10);
end;


В функции объявлены три переменные числового типа: index - для того чтобы можно было своевременно узнать о том, что элемент уже содержится в таблице, hashValue - для хранения хеша вставляемого элемента и переменная i для запуска цикла for. В случае, если элемент уже содержится в таблице то функция вернёт -1 и выведет соответствующее сообщение.
Далее мы получаем хеш элемента и если нужная позиция уже занята, то следуем вниз по таблице, до того момента пока не найдём пустую позицию и не займём её.
В конце следует проверка того не достигнут ли конец таблицы, тогда увеличиваем её размер.
В сущности, мы написали функцию, которая в точности повторяет, всё то что было сказано о ней в теоретической части.

Удаление элемента из таблицы.

Эта функция удалит не нужный нам элемент из таблицы и вернёт его бывший индекс в таблице.


function TForm1.DeleteK(const key: string): Integer;
var
i, index:integer;
tmp: String;
begin
index:=IndexOf(key);
Result:=-1;
if index=-1 then begin
exit;
end;
if HashTable[index]=′′ then begin
Result:=-2;
exit;
end;
HashTable[index]:=′′;
Result:=index;
KeyCount:=KeyCount-1;
for i:=index+1 to high(hashTable) do begin
if HashTable=′′ then exit;
tmp:=HashTable;
HashTable:=′′;
InsertK(tmp)
end;
end;


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

Хочу заметить, что писать ещё одну процедуру поиска не имеет смысла, так как она уже написана и остаётся, только передать нужный параметр в функцию IndexOf и получить результат.

Изменение размера таблицы.

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


procedure TForm1.ResizeHTable(newSize: integer);
var
TmpTable: array of string;
i, index: integer;
begin
if newSize then begin
ShowMessage(′Размер новой таблицы должен быть′#13′больше чем количество элементов в ней′);
exit;
end;
SetLength(TmpTable, KeyCount);
index:=0;
for i:=0 to high(HashTable) do begin
if HashTable<>′′ then begin
TmpTable[index]:=HashTable;
index:=index+1;
end;
end;
ClearHTable;
SetLength(HashTable, NewSize);
for i:=0 to high(TmpTable) do
InsertK(TmpTable);
end;


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

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