Zapewne wielu z Was korzystało już ze struktury nazywanej Słownikiem (Dictionary, Hash Map itp.), ale ciekawi mnie, czy zastanawialiście się kiedyś jak ta struktura tak naprawdę funkcjonuje. Jeżeli chcecie się tego dowidzieć to zapraszam do lektury 😎. Dla ilustracji przykładów będę używał Swift’a, ale ogólne zasady są takie same dla większości języków programowania.

Podstawową funkcją Hash Table jest przechowywanie danych w oparciu o relację Key: Vaule, polegającą na tym, że pewnemu unikalnemu w skali kolekcji kluczowi zostaje przypisana pewna wartość, która unikalna być nie musi (czyli może powtarzać się w ramach jednej struktury). W przypadku Swfit’a Hash Table zostało wykorzystane do stworzenia Słownika (Dictionary). Prosty przykład dla rozjaśnienia. Proponuję przepisać go sobie do Playground w Xcode:

 

 

W powyższym przykładzie zastosowałem prosty klucz typu String, ale kluczem może być dowolny obiekt, który spełni wymogi protokołu Hashable (jak tego można dokonać będzie trochę później). Typ String domyślnie spełnia wymogi wspomnianego protokołu, tak więc bez problemu może zostać użyty jako klucz w naszym przykładowym słowniku.

W gruncie rzeczy Hash Table jest zwykłą tablicą, która została zaimplementowana w dość specyficzny sposób. Początkowo nasza tablica jest pusta, a kiedy wstawimy do niej wartość na podstawie naszego klucza „bestGameEver” zostanie jej przydzielony odpowiedni numer indeksu. Będzie to wyglądało następująco:

 

 

W powyższym przykładzie klucz „bestGameEver” zostaje przydzielony do indeksu o numerze 1. Zobaczmy co stanie się po dodaniu klucza „bestRPG”:

 

 

Klucz zostaje przypisany do indeksu numer 3. Wszystko bardzo fajnie, ale pewnie zastanawiacie się w jaki sposób indeksy te są obliczane? Tutaj właśnie wchodzi do gry protokół Hashable, którego wymogi spełnia m.in typ String (większość typów wbudowanych w Swift wykorzystuje ten protokół). Wymaga on od danego typu posiadania właściwości (pola) o nazwie hashVaule, która przechowuje reprezentację obiektu w postaci liczbowej. Najlepiej będzie jak to sobie sprawdzicie na przykładzie. Dodajcie poniższy kod do Waszego projektu:

 

 

Wartości liczbowe widoczne w Waszych konsolach mogą różnić się od moich, a nawet mogą się różnić pomiędzy poszczególnymi kompilacjami. Związane jest to dużą ilością zmiennych branych pod uwagę podczas wyliczania wartości hash. Możecie jednak mieć pewność, że w ramach jednej kompilacji wartości te zawsze będą takie same. Obliczanie wartości hash danego obiektu angażuje bardzo zaawansowaną matematykę, ale poznawanie całej logiki nie będzie potrzebne dla zrozumienia idei samych Hash Tables.

Jak sami widzicie wartości hash nie nadają się raczej do wykorzystania jako numery indeksów w tablicy, więc jak się pewnie domyślacie potrzebna jest jeszcze jedna operacja. Numer indeksu zostanie wyliczony z wykorzystaniem reszty z dzielenia (modulo) wartości hash przez rozmiar naszej kolekcji (jej capacity). Będzie wyglądało to tak:

 

 

Nic skomplikowanego prawda? 😅

To właśnie zastosowanie klucza jako wartości hash sprawia, że słowniki są bardziej wydajne niż na przykład standardowe tablice (Arrays). Aby uzyskać dostęp do określonej wartości wystarczy sprawdzić wartość hash jej klucza. Nie ma tutaj znaczenia wielkość danej kolekcji, dlatego operacje takie jak pobranie, usunięcie lub podmiana danych zawsze będą miały taki sam koszt równy O(1). Pojęcie kosztu związane jest z zagadnieniem określanym jako Big-O-Notation, które bliżej postaram się opisać w osobny wpisie. W dużym skrócie chodzi o czas wykonania określonych algorytmów. Im dłuższy czas potrzebny jest na wykonanie wszystkich obliczeń, tym algorytm staje się mniej wydajny.

Jedynym minusem korzystania ze słowników jest fakt, że nie ma możliwości przewidzenia w jakim miejscu zostanie umieszczony dany klucz. Dlatego słowniki nie są dobrym rozwiązaniem jeżeli potrzebujemy kolekcji z uporządkowanymi elementami.

Jak pewnie już się domyślacie przydzielanie numeru indeksu na podstawie wartości modulo bardzo szybko może doprowadzić do sytuacji, w której dwa rożne klucze otrzymają takie same indeksy, co doprowadzi do kolizji. Istnieje kilka możliwości ich rozwiązania. Pierwsza z nich zakłada, że nowy klucz zostanie wstawiony najbliżej, jak to tylko możliwe już istniejącego klucza (biorąc oczywiście pod uwagę wolne miejsca w tablicy). Takie podejście nazywane jest open addressing. Można również utworzyć bardzo duży słownik, ale nawet w takim przypadku kolizja w pewnym momencie nastąpi.

My skupimy się na trzecim rozwiązaniu, które określane jest jako chaining. Do naszej kolekcji dodamy nowy klucz „bestFPS” z wartością „Borderlands”. Po wyliczeniu modulo wyjdzie nam, że musimy umieścić klucz pod indeksem o numerze 3. Tak to będzie wyglądało:

 

 

Metoda chaining zakłada, że klucze wraz ich wartościami nie będą składowane w słowniku bezpośrednio. Każdy element w słowniku (pamiętajcie, że słownik to taka inna wersja tablicy) przechowywany jest jako lista, która zajmuje się przechowywaniem kolekcji składającej się z par Key: Value. Zwykle przyjmuje się, że poszczególne elementy słownika nazywane są wiaderkami (bucket), a listy, które zawierają pary Key: Value są nazywane łańcuchami (chains). W naszym przykładzie mamy 8 wiaderek, a w dwóch z nich dodatkowo przechowywane są łańcuchy.

Załóżmy teraz, ze chcemy pobrać wartość z naszego słownika:

 

 

W pierwszej kolejności system sprawdza jaka jest wartość hash klucza „bestRPG” (można powiedzieć, że obiekt jest hashowany), a następnie oblicza zgodnie z umieszczonym wyżej opisem numer indeksu. Wartość 3 oznacza, że konieczny jest dodatkowy wysiłek, aby znaleźć odpowiednią wartość, ponieważ aktualnie pod numerem 3 znajdują się dwie pary Key: Value. System dokonuje dodatkowego porównania pomiędzy kluczami, które są typu String. Porównanie możliwe jest dzięki temu, że typ String spełnia wymogi protokołu Comparable. Dzięki takiemu porównaniu okazuje się, że poszukiwana wartość znajduje się na samym końcu łańcucha. System do zmiennej bestRPGTitle wstawi wartość „Witcher 3”.

Łańcuchy, w których przechowywane są pary Key: Value nie powinny być jednak zbyt długie, ponieważ operacje wyszukiwania staną się zbyt czasochłonne. Idealnie każdy łańcuch powinien mieć tylko jedną wartość, ale taka sytuacja jest mało prawdopodobna, ponieważ nie da się całkowicie uniknąć kolizji.

 

Słowo na drogę

 

Jak sami widzicie nie jest to jakoś przesadnie skomplikowane jak już uda się wszystko rozłożyć na czynnik pierwsze. Myślę, ze dobrze jest posiadać taką wiedzę, aby podejmować bardziej świadome decyzje podczas wybierania struktury odpowiedniej dla naszego zadania. Ostatecznie zawsze też można błysnąć przed kolegami z pracy 😎. Mam nadzieję, że udało mi się przedstawić działanie Hash Tables w łatwy do przyswojenia sposób.


 

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *