Tablica mieszająca

Tablica mieszająca lub tablica z haszowaniem (ang. hash table, niekiedy błędnie^{[potrzebny przypis]} tłumaczone jako „tablica haszująca”) – struktura danych, która jest jednym ze sposobów realizacji tablicy asocjacyjnej, tj. abstrakcyjnego typu danych służącego do przechowywania informacji w taki sposób, aby możliwy był do nich szybki dostęp. Tablica mieszająca umożliwia również szybkie porównywanie danych, np. fragmentów tekstów, plików.

Odwołania do przechowywanych obiektów dokonywane są na podstawie klucza, który dany obiekt (informację) identyfikuje.

Podstawowe informacje

Tablice mieszające opierają się na zwykłych tablicach indeksowanych liczbami – dostęp do danych jest bardzo szybki, nie zależy od rozmiaru tablicy ani położenia elementu (przynajmniej teoretycznie, patrz sekcja Wady). W tablicy mieszającej stosuje się funkcję mieszającą, która dla danego klucza wyznacza indeks w tablicy; innymi słowy przekształca klucz w liczbę z zadanego zakresu.

Funkcje te są zwykle nieskomplikowane, tak aby czas ich wykonywania nie dominował w operacjach na tablicy.

Funkcję mieszającą dobiera się do klucza; inaczej będzie zbudowana funkcja dla tablic przechowujących nazwiska (dowolnie długie łańcuchy znaków), inaczej dla współrzędnych (ciągi liczb rzeczywistych), inaczej dla numerów seryjnych (ciągi liczb i cyfr o określonej długości). Istnieją również funkcje uniwersalne, które można stosować dla dowolnych danych.

W najprostszym przypadku wartość funkcji mieszającej, obliczona dla danego klucza, wyznacza dokładnie indeks szukanej informacji w tablicy. Jeżeli miejsce wskazywane przez obliczony indeks jest puste, to poszukiwanej informacji nie ma w tablicy. W ten sposób wyszukiwanie elementu ma złożoność czasową $O(1).$ Jednak w sytuacji tej pojawia się problem kolizji, to znaczy przypisania przez funkcję mieszającą tej samej wartości dwóm różnym kluczom.

Jednak jeżeli dane, które mają być przechowywane w tablicy mieszającej, są znane zawczasu (np. nazwy państw, miast, słowa kluczowe jakiegoś języka programowania), można posłużyć się doskonałą funkcją mieszającą albo minimalną doskonałą funkcją mieszającą, które nigdy nie spowodują kolizji. Doskonała funkcja mieszająca odwzorowuje $n$ kluczy na różne wartości z przedziału $[0,m-1],$ gdzie $m\geqslant n;$ w przypadku funkcji minimalnych zachodzi równość $m=n.$

Istnieją algorytmy, które wyznaczają takie funkcje, np. algorytm Cichelliego, FHCD (oba dla napisów), CHD (dla dowolnych danych). Programy, które znajdują funkcje minimalne to np. gperf lub cmph.

Rozwiązywanie problemu kolizji

W sytuacji gdy wartość funkcji mieszającej obliczonej dla klucza elementu wstawianego do tablicy pokrywa się z wartością funkcji obliczoną dla klucza jakiegoś elementu już znajdującego się w tej tablicy, mówimy o kolizji. Istnieje kilka sposobów rozwiązywania tego problemu. Najprostszym sposobem jest zastąpienie elementu znajdującego się w tablicy przez nowy element lub ewentualnie rezygnacja ze wstawiania nowego elementu. Na ogół jednak wymagane jest, aby oba elementy znalazły się w tablicy, co pociąga za sobą konieczność zastosowania innej metody.

Metoda łańcuchowa

Metoda łańcuchowa polega na przechowywaniu elementów nie bezpośrednio w tablicy, lecz na liście związanej z danym indeksem. Wstawiane elementy dołącza się do jednego z końców listy. Średnia złożoność wyszukiwania jest złożonością liniowego wyszukiwania elementu na liście i zależy od współczynnika wypełnienia listy, czyli stosunku liczby elementów do wielkości tablicy. Ponieważ złożoność pesymistyczna wyszukiwania wynosi $\mathrm {O} (n),$ czasami zamiast list stosuje się drzewa. Zaletą metody łańcuchowej jest szybkość i prostota usuwania elementów z listy.

Adresowanie otwarte

Inny sposób rozwiązywania problemu kolizji to 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:

szukanie liniowe, dla funkcji przyrostu postaci $p(i)=i,$
szukanie kwadratowe, dla $p(i)=i^{2},$
mieszanie podwójne, dla $p(i)=i\cdot h'(K),$ gdzie $h'$ jest dodatkową funkcją mieszającą od klucza $K.$

W przypadku szukania liniowego może pojawić się problem grupowania, to znaczy koncentracji miejsc zajętych w pewnych zakresach indeksów przy małej zajętości innych obszarów tablicy. Problem ten jest w znacznym stopniu zredukowany w przypadku szukania kwadratowego, chociaż w tej metodzie występuje analogiczny problem grupowania wtórnego, natomiast praktycznie wyeliminowany dla mieszania podwójnego.

Innym kłopotem jest skomplikowanie procesu usuwania elementu, w sytuacji gdy w tablicy znajdują się inne, o tej samej wartości funkcji mieszającej. Wymusza to rozróżnianie trzech stanów elementów tablicy: zajęta, wolna, wolna po usunięciu.

Współczynnik wypełnienia

Współczynnik wypełniania (ang. load factor) jest definiowany jako iloraz liczby elementów zapisanych w tablicy mieszającej $(m)$ do fizycznego rozmiaru tablicy $(n).$ Jeśli rozkład prawdopodobieństwa wartości funkcji skrótu jest jednostajny, wówczas przeciętnie dla $\alpha =m/n$ elementów wystąpią kolizje.

Przy inicjalizacji tablicy mieszającej podaje się początkowy rozmiar $n$ (lub jest ona niejawnie określona przez implementację). Natomiast podczas pracy z tablicą sprawdzany jest aktualny współczynnik wypełnienia i gdy jest za duży, rozmiar fizyczny tablicy zostaje odpowiednio korygowany.

W praktyce przyjmuje się wartość współczynnika na poziomie $\alpha =0{,}7\ldots 0{,}8.$

Haszowanie kukułcze

Haszowanie kukułcze, zwane też niegramatycznie haszowaniem kukułkowym, rozwiązuje problem kolizji poprzez zastosowanie dwóch tablic i dwóch odpowiadających im funkcji haszujących. Dopóki nie występuje kolizja, dodawane elementy są umieszczane w pierwszej tablicy pod indeksem wyznaczonym przez pierwszą funkcję mieszającą. Jeśli jednak wystąpi kolizja (w miejscu wyznaczonym przez pierwszą funkcję już znajduje się inny obiekt), to wstawiany element jest umieszczany w drugiej tablicy na pozycji wyznaczonej przez drugą funkcję. Jeśli pod tamtym indeksem także znajdował się jakiś obiekt, to zostaje on stamtąd usunięty i dla niego rekurencyjnie zostaje uruchomiona procedura wstawiania, przy czym tym razem zostanie on na siłę wstawiony do pierwszej tablicy. Proces ten jest powtarzany do momentu, w którym przy wstawianiu elementu nie wystąpi kolizja. W przypadku zapętlenia się algorytmu, losowane są nowe funkcje haszujące i wszystkie elementy tablicy zostają ponownie przemieszane. Jeśli został osiągnięty ustalony współczynnik wypełnienia, to przed wybraniem nowych funkcji należy powiększyć rozmiar tablicy mieszającej.

Haszowanie kukułcze gwarantuje odczyt elementu z tablicy w czasie stałym (gdyż wymagane jest jedynie sprawdzenie dwóch indeksów), a przy losowaniu funkcji mieszających z odpowiedniej rodziny, oczekiwany zamortyzowany koszt wstawienia elementu jest również stały^[1].

Zastosowania

Tablice mieszające są szeroko stosowane do implementacji wielu algorytmów i aplikacji. Są szeroko stosowane w kompilatorach, interpreterach (szczególnie dynamicznych języków obiektowych, jak Python, Perl, JavaScript, Lua), bazach danych (indeksowanie, łączenie, agregacja / grupowanie), analizie i agregacji danych, trasowaniu (routowaniu), systemach cachowania (pamięć podręczna), monitorowaniu, implementacji zbiorów, mapowań dwukierunkowych (bijekcja), kompresji danych, wyszukiwaniu wzorców i wielu innych.

Większość języków programowania posiada implementację tablicy mieszającej w ramach standardowej biblioteki. Ponadto większość języków interpretowanych, takich jak PHP, Ruby czy Smalltalk posiada specjalną składnię do tworzenia tego typu struktur.

Ciekawym przykładem zastosowania rozproszonej tablicy mieszającej jest protokół Kademlia stosowany w niektórych sieciach typu peer-to-peer.

Przy wyszukiwaniu wzorca w tekście:

Definiujemy $h(s[i..j])=(s[i]+s[i+1]*p^{1}+s[i+2]*p^{2}+\ldots +s[j]*p^{j-i})\mod q$

gdzie h() – tablica mieszająca, s – słowo, p – baza (najczęściej przyjmuje się liczbę ~30), q – liczba, przez którą dzielimy (najczęściej 2e9+29)

Funkcję h można obliczać ze wzoru rekurencyjnego

h(n+1)=0

h(i)=(h(i+1)*p+s[i])\mod q

A dla danego podciągu w czasie stałym

h(s[i..j])=(h(i)-p^{j-i+1}*h(j+1))\mod q

Wartość $p^{j-i+1}$ dla dużych wartości wykładnika musimy policzyć zgodnie z arytmetyką modularną, tj. w pseudokodzie:

 tp := 1
 for k := 1 to j-i+1 do
  tp := tp*p
  tp := tp mod q

Wady

Podstawową wadą klasycznych tablic mieszających jest duża złożoność pesymistyczna wyszukiwania, wynosząca $O(n).$ Ponadto kosztowne może być także obliczanie wartości dobrej funkcji mieszającej.

Kolejna wada wiąże się z architekturą współczesnych procesorów, które wykorzystują pamięć podręczną. Ponieważ pamięć podręczna przyspiesza odwołania do komórek pamięci operacyjnej, gdy są one zgrupowane blisko siebie, zastosowanie tablicy mieszającej dla zbyt małej liczby elementów może być wolniejsze niż zastosowanie zwykłej tablicy przeszukiwanej sekwencyjnie.

Praktyczne implementacje szybkich tablic mieszających stosują różne techniki hybrydowe, aby zminimalizować lub wyeliminować te problemy.

Zobacz też

Przypisy

↑ Haszowanie 2: haszowanie doskonałe i kukułkowe.

Bibliografia

Hashowanie. W: Donald Ervin Knuth: Sztuka programowania. T. 3: Sortowanie i wyszukiwanie. Warszawa: Wydawnictwa Naukowo-Techniczne, 2002, s. 552–601. ISBN 83-204-2554-9.
Mieszanie. W: Adam Drozdek: Wprowadzenie do kompresji danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 1999, s. 412–450. ISBN 83-204-2303-1.
Romuald Jagielski: Tablice rozproszone. Warszawa: Wydawnictwa Naukowo-Techniczne, 1982. ISBN 83-204-0247-6.

[1] Haszowanie 2: haszowanie doskonałe i kukułkowe.

[1]