Struktury danych/Tablice z haszowaniem

Spis treści
Wstęp	Wstęp - Konwencje
Struktury danych	Podstawy - Tablice - Listy - Stosy - Kolejki - Drzewa - Zbiory - Kopce - Find-Union - Tablice z haszowaniem - Grafy
Dodatki	Złożoność obliczeniowa - Implementacje w C++ - Implementacje w Pascalu - Bibliografia - Dla twórców podręcznika

Tablice z haszowaniem

Przykładowe zastosowanie haszowania - książka telefoniczna

W wielu zastosowaniach potrzebne są zbiory, na których najczęściej wykonywanymi operacjami są INSERT, SEARCH, DELETE i tylko w przypadku tych operacji zależy nam żeby były wykonywane jak najszybciej. Zbiory tego typu nazywa się słownikami. Można bardzo łatwo znaleźć przykład z codziennego życia,w którym świetnie dałoby się wykorzystać taką strukturę - a mianowicie w przypadku książki telefonicznej. W tym przypadku staramy się wyszukać numer przypisany do konkretnego nazwiska, a nie na odwrót. W przypadku kompilatorów potrzebna jest tablica symboli, w której kluczami elementów są dowolne ciągi znaków odpowiadające identyfikatorom. Tablica mieszająca jest strukturą, która efektywnie implementuje słowniki. Chociaż w niektórych przypadkach wyszukiwanie może zachowywać się w najgorszym wypadku jak w liście w czasie $\Theta (n)$, w praktyce jednak haszowanie zachowuje się naprawdę dobrze. Przy pewnych założeniach można wykazać, że średni czas wyszukiwania elementu w tablicy z haszowaniem wynosi $O(1)$.

Słownik

• SEARCH(k: klucz) wyszukiwanie elementu o kluczu k.
• INSERT(d:Data, k:klucz) dopisywanie elementu d o kluczu k
• DELETE(d:Data, k:klucz) usuwanie elementu d o kluczu k

Tablica z haszowaniem jest uogólnieniem zwykłej tablicy. Można wysnuć pewną definicję ogólną korzystając ze szczególnego przypadku jakim jest zwykła tablica. Rozważając ją mamy strukturę, w której dla każdego elementu istnieje pewien klucz - indeks tablicy - który zazwyczaj jest liczbą z zakresu $[0,n]$ dla n będącego dowolną liczbą naturalną odpowiadającą wielkości tablicy. Można mówić, że nasze uniwersum kluczy - zbiór zawierający wszystkie możliwe wartości indeksów jest jakimś podzbiorem $\mathbb {N}$. Takie podejście nazywane jest również adresowaniem bezpośrednim.

Tablice z adresowaniem bezpośrednim

Stosowanie adresowania bezpośredniego jest bardzo prostą metodą, zakładając, że nasze uniwersum kluczy $U$ nie jest bardzo duże. Przyjmując takie założenia : $U=\{0,1,...,n\}$ dla n które jest rozsądnie małe oraz żadne dwa elementy nie mają identycznych kluczy można skorzystać ze zwykłej tablicy, która jest obecna w większości języków programowania jako struktura wbudowana w język. Takie podejście jest zastosowane na rysunku obok: na k-tej pozycji znajduje się wskaźnik do elementu o kluczu k. Jeśli w zbiorze nie znajduje się żaden element o kluczu k, to wskaźnik z tej pozycji jest równy null.

W takim wypadku implementacja operacji słownikowych jest zdecydowanie prosta oraz wszystkie funkcje działają w czasie $O(1)$:

template <typename T> 
//zakładamy, że T to pewien 
//typ wskaźnikowy
T direct_search(T[] array, int k){
    return array[k];
}

template <typename T>
void direct_insert(T[] array, T x, int k){
    array[k] = x;
}

template <typename T>
void direct_delete(T[] array, int k){
    array[k] = nullptr;
}

Tablice z haszowaniem

W przypadku adresowania bezpośredniego nasz zbiór kluczy U może być bardzo duży, jeżeli będziemy chcieli stworzyć tablicę wielkości U może się okazać to niesamowicie nieoptymalne pod względem zużycia pamięci lub co gorsza nawet nie możliwe do zaalokowania. Dodatkowo może się okazać, że spośród wszystkich kluczy, zbiór faktycznie wykorzystywanych kluczy K będzie bardzo mały względem rozmiarów U, co doprowadzi w konsekwencji do kolejnej sytuacji, gdzie będzie marnowana pamięć.

Rozwiązaniem tych problemów jest tablica z haszowaniem. W tym wypadku okaże się, że zużycie pamięciowe będzie $\Theta (|K|)$, czyli optymalne dla zbioru kluczy faktycznie wykorzystywanych, co więcej wyszukiwanie w tej tablicy w przypadku średnim będzie dalej działać w czasie $O(1)$. Niestety, w przypadku pesymistycznym może się okazać, że będzie wyższe, natomiast adresowanie bezpośrednie nadal będzie rzędu $O(1)$.

Podstawą działania tablic z haszowaniem są funkcje haszujące, które nazywa się również funkcjami skrótu. Ogólnie wszystkie działają w dość podobny sposób, dla danych dowolnej wielości w rozsądnym czasie przekształcają dane w jakąś liczbę. W adresowaniu bezpośrednim braliśmy k - klucz ze zbioru U i w tablicy umieszczaliśmy dane na pozycji k-tej. W adresowaniu z haszowaniem mamy do czynienia z krokiem pośrednim - haszowaniem, w tym wypadku będziemy dla klucza k znajdować pozycję h(k). W tym wypadku funkcja h będzie odwzorowywać nasze uniwersum kluczy U w zbiór pozycji tablicy o rozmiarze n.

$h:U\rightarrow \{0,1,2,...,n-1\}$

Problem kolizji

Za oszczędności pamięciowe musimy jednak płacić tym, że nie można stworzyć funkcji, która dla dowolnych danych będzie znajdować różne pozycje w tablicy, niektóre dane będą ze sobą kolidować. Oznacza to, że dla dwóch różnych kluczy funkcja mieszająca przypisuje tę samą pozycję w tablicy.

Na szczęście istnieją efektywne sposoby rozwiązywania tego problemu. Najważniejszy jest tu dobór funkcji haszującej. Jednym ze sposobów jest korzystanie z funkcji haszujących, które wydają się być losowe. Oczywiście, muszą dla konkretnych danych zwracać te same wartości, więc muszą być deterministyczne. Jednak ze względu na fakt, że $|U|>n$ U na pewno zawiera dwa takie klucze, dla których funkcja zwróci te same wartości haszujące całkowite usunięcie problemu kolizji nie jest więc możliwe, można tylko minimalizować jego skutki.

Metoda łańcuchowa

Podstawową metodą rozwiązywania problemu kolizji jest utworzenie tablicy wskaźników jako podstawy dla naszej tablicy z haszowaniem oraz umieszczanie poszczególnych elementów w liście, na którą będzie wskazywać wskaźnik na pozycji j. Jeżeli nie zdarzy się kolizja pod danym rekordem j w tablicy będzie znajdować się wskaźnik na początek jednoelementowej listy, mamy więc dostęp w czasie $O(1)$. W przypadku, w którym nastąpi kolizja i w liście znajdzie się kilka elementów sytuacja diametralnie się zmieni. Na przykład mając jakąś funkcję $h$ dla kluczy $k_{1},k_{2},k_{3}$ i otrzymamy $j=h(k_{1})=h(k_{2})=h(k_{3})$, w pod jednym rekordem w tablicy znajdzie się trójelementowa lista, więc dostęp do poszczególnego rekordu się wydłuży do $\Theta (l)$, gdzie $l$ to długość listy. Należy pamiętać, że aby można było dostać się do poprawnych danych należałoby przechować w danym ogniwie łańcucha trzeba również wartość klucza. Natomiast jeśli w zbiorze nie ma jeszcze elementów, które znajdowały by się pod pozycją j-tą, to warość wskaźnika będzie równa null.

Modyfikacja metody łańcuchowej za pomocą drzew BST

Można nieco przyspieszyć działanie struktury w przypadku, gdy kolizji będzie na tyle dużo, że działanie w czasie liniowym będzie występować nagminnie. Jeżeli czas będzie naprawdę ważnym czynnikiem, a metoda łańcuchowa okaże się z jakichś względów korzystna można zamiast z list skorzystać z drzew wyszukiwań binarnych. Co prawda powoduje to dodatkowe problemy związane z ich balansowaniem, ale w średnim przypadku otrzymamy złożoność wyszukiwania $O(log(n))$, która jest zdecydowanie lepsza od czasu liniowego. Dodatkowym warunkiem, który musi zostać spełniony jest możliwość określenia jakieś relacji porządku pomiędzy kluczami, tak by drzewo BST miało w ogóle rację bytu.

Funkcje haszujące

Haszowanie modularne

Haszowanie modularne przyjmuje funkcję haszującą w postaci $h(k)=k\mod m$, gdzie $m$ jest rozmiarem tablicy z haszowaniem. Jest to jedna z najprostszych funkcji haszujących, która wylicza pozycję w przestrzeni adresowej dzieląc modularnie wartość klucza przez rozmiar tablicy. Aby zmniejszyć ryzyko kolizji najlepiej jest używać wartości $m$ będących liczbami pierwszymi, które nie leżą zbyt blisko potęg $2$.

Adresowanie otwarte

W podejściu tym nowy element wstawia się w innym miejscu niż wynikałoby to z wartości funkcji mieszającej. Nowa lokalizacja określana jest przez dodanie do wartości funkcji mieszającej wartości tzw. funkcji przyrostu $p(i)$, gdzie i oznacza numer próby (to znaczy ile razy wstawienie się nie powiodło ze względu na kolizję). Ze względu na rodzaj funkcji przyrostu wyróżnia się różne metody adresowania otwartego opisane poniżej.

Adresowanie liniowe

(ang.linear probing)

Adresowanie kwadratowe

(ang. Quadratic probing)