Hash Table Implementation

До скоро не знаех начина на работа на хеш таблиците и принципът ми се струваше “магически”. Как така, като имаме само линейни структури от данни, а търсим, добавяме и трием с константа сложност? По случай започването на новият курс по Структури данни и алгоритми, реших да разуча въпроса по-подробно. Естествено, най-добре се учи с писане – в тази статия ще обясня начинът на работа на моята имплементация на хеш таблица и основните принципи в тях.

Как работи?

В основата си хеш таблицата е масив от двойки ключ и стойност. Когато добавяме елемент се взима ключа и върху него се прилага хеш-функция. Целта й е да създаде уникална стойност от подаденият ключ и даже да имаме два ключа, които се различават само по един символ те да произведат различни числа. Начинът по който се създава също е много важен. Да приемем, че ключът е някакъв стринг и нашата хеш-функция събира char стойностите, ще имаме много еднакви резултати. Причината е, че много стрингове могат да направят сбор от 500, примерно. Има и други параметри, като сигурност, бързина и др. и тн, и др. Като цяло препоръчително е да използваме вече написан алгоритъм и .NET предлага много възможности в неймспейса System.Security.Cryptography. За примерите и моята имплементация използвам .GetHashCode(), понеже за обучение върши работа. Вече имаме хеш-стойността на ключа. Следващата стъпка е съотнасянето на хеша към индекс в масива. Това също може да се направи по много начини. Важно е да се съобразява с дължината на масива, както и разбира се детерминистичен резултат. Най-лесният начин да направим нещо подобно е като разделим по модул хеша и дължината масива, и вземем абсолютната стойност. Ето как изглежда добавянето(търсене и триене се извършват по аналогичен начин):


hashTable.Add(entryName.GetHashCode(), entryName);

------------

public void Add(K key, V value)
{
    int index = GetIndex(key);
    array[index] = new KeyValuePair<K,V>(key, value);
}

private int GetIndex(K key)
{
    return Math.Abs(key.GetHashCode() % Capacity);
}

Това обаче не е всичката функционалност, която ни е нужна. Досега обясненото се счита по-скоро за асоциативен масив и използването му в този силно опростен вид би донесло единствено болка на дивелъпъра.

Fill Factor

This is what happens to hash tables when they fill up.

Съществува време, когато всяка малка хеш-таблица пораства и става голяма хеш-таблица. Понеже масивът е със статична големина рано или късно той се запълва и обикновено не се чака до последното празно поле, за да направим нов, защото колкото по-пълна е таблицата толкова по-голям е шансът за колизии. Fill factor-а(или load factor) е число между 0 и 1, което индикира до каква степен можем да добавяме в таблицата, преди да се наложи да създадем по-голям масив.

maxItemsAtCurrentSize = (int)(array.Length * fillFactor) + 1;

След това създаваме двойно по-голям масив и преместваме всички елементи от стария със същите методи с които добавяме и в таблицата. Тук е момента да спомена и за бързината на хеш-функцията. Ако трябва да преместим 1 000 000 елемента, използвайки SHA1/2 за хеш, може да мине време. Същото важи, ако въвеждаме по много елементи и затова хеширащият алгоритъм трябва да е подбран в съответствие с нуждите на приложението.

Collisions

Дори и с идеална хеш-функция няма начин от време на време да не уцелваме индекс, който вече е зает. Хвърлянето на ексепшън не е вариант, защото тогава този елемент никога няма да може да се добави, а ние не правим краш-таблица. Двата най-популярни метода за справяне с този проблем са open addressing и separate chaining. При първият, когато срещнем заета позиция проверяваме дали i+1 не е празно, ако е слагаме елемента там, ако не е продължаваме към следващият. Когато използваме separate chaining в масива не слагаме директно key-value-pairs, а List<key-value-pairs>. Така, когато уцелим вече заета позиция добавяме втори елемент към листа и когато търсим на тази позиция трябва да обходим този лист, за да намерим търсеният. Обръщам внимание, че всички са с различен key, но се намират на един и същи индекс, защото GetIndex(Key k) ги е поставил там. Съществуват още начини за справяне с колизии, но те са по-скоро техни вариации или хибриди.

Това е основната теория. В wikipedia има много добри статии, но когато ги четох за първи път нещата по-горе не ми бяха ясни и нещо не ги схванах. Hash tables, associative arrays, hash functions.

Hash Table Implementation

HashTableSolution

В моята имплементация съм използвал separate chaining за колизиите и lazy initialization при създаването на листи, защото при големи таблици определено удря в пърформънса инициализирането им наведнъж. HashTable е таблицата, освен публичните методи за работа с нея, се следи за load factor-а и създаването на по-голям масив при нужда. HashTableArray е обектът за работа с асоциативният масив. ArrayNode е листът от двойки ключ-стойност, нужен за прилагане на separate chaining. И KeyValuePair са двойките. Като цяло кодът е доста прост и лесен за разбиране, затова смятам да ви оставя да си го изтеглите и разцъкате. Няма нищо сложно и до голяма степен нещата се припокриват с горните параграфи. Всички тестове се инициализират в Utilites.AddEntries(). Сега като се замисля не би било зле всички записи да се създават наведнъж и след това да се подава заявената от теста бройка, защото в момента за всеки тест се създават нови.

Posted in C#, Programming Tagged with: , , , , , , , , , , , , , ,

Leave a Reply

Your email address will not be published.