Tablica mieszająca
Z Wikipedii
W informatyce tablica mieszająca lub tablica haszująca to struktura danych służąca 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. Położenie informacji w tablicy określa się obliczając wartość funkcji mieszającej dla danego klucza.
Spis treści |
[edytuj] 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 w miejsce wskazywane przez obliczony indeks jest puste, to poszukiwanej informacji nie 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.
[edytuj] 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.
Jeżeli dane, które mają być przechowywane w tablicy mieszającej, są znane zawczasu, można posłużyć się doskonałą funkcją mieszającą. Jest to taka funkcja haszująca, która jest wyliczana na podstawie zadanego zbioru kluczy. Dzięki takiemu podejściu można całkowicie wyeliminować problem kolizji, a rozmiar tablicy jest dokładnie taki, jak liczba danych w niej przechowywanych.
[edytuj] 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.
[edytuj] 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.
Zobacz też: tablica asocjacyjna, tablica.
