Wolna encyklopedia
W informatyce tablica mieszająca lub tablica haszująca to jeden ze sposobów realizacji tablicy asocjacyjnej, tj. struktury danych służącej do przechowywania informacji, w taki sposób aby możliwy był do nich szybki dostęp.
Odwołania do przechowywanych obiektów dokonywane są na podstawie klucza, który dany obiekt (informację) identyfikuje. Kluczem może być na przykład ciąg znaków zawierający nazwisko pracownika, a wyszukiwaną informacją jego adres domowy.
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. 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 mieszającą dobiera się do klucza; inaczej będzie zbudowana funkcja dla tablic przechowujących nazwiska (łańcuchy znaków), inaczej dla współrzędnych (pary, czy n-tki liczb rzeczywistych), inaczej dla numerów seryjnych (liczby i cyfry). Funkcje są zwykle nieskomplikowane, tak aby czas ich wykonywania nie dominował w operacjach na tablicy.
Spis treści |
Podstawowe informacje
Tablic mieszających używa się do tworzenia struktur danych zawierających informacje, identyfikowane przez pewien klucz. Ze względu na fakt, iż klucz ten może mieć zakres wartości większy niż rozmiar tablicy (np. numer PESEL), lub może mieć postać ciągu znaków (np. nazwisko), potrzebna jest metoda konwersji klucza na indeks w tablicy. Metody takiej dostarcza funkcja mieszająca.
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. 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 
; w przypadku funkcji minimalnych zachodzi równość m = n. Istnieją programy, które potrafią znaleźć takie funkcje, 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ą 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 z 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 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 O(n), czasami zamiast list stosuje się drzewa. Zaletą metody łańcuchowej jest szybkość i prostota usuwania elementów z listy.
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 *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 i praktycznie wyeliminowany dla mieszania podwójnego. Innym problemem jest skomplikowanie procesu usuwania elementu, w sytuacji gdy w tablicy znajdują się inne, o tej samej wartości funkcji mieszającej.
Zastosowania
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.
Wady
Podstawową wadą 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.