W strukturach drzewiastych takich jak drzewa binarnych poszukiwań czy kopce, pozycja elementu w drzewie zależy od relacji zachodzącej między nim, a innymi elementami. W metodach haszujących (mieszających) pozycja elementu jest wyliczana na podstawie wartości elementu lub tzw. klucza, związanego z elementem.  Funkcję wyliczającą pozycję elementu w zbiorze nazywa się funkcją mieszającą lub haszującą (od ang. hash function). Własnością szczególną metod haszowania jest, że pozwalają one wykonać operacje wstawiania, usuwania i wyszukiwania elementu, z kosztem niezależnym od liczby elementów w zbiorze, tzn. z kosztem stałym ze względu na rozmiar danych. Struktury danych oparte na metodach haszowania nazywamy tablicami haszującymi (lub tablicami z haszowaniem, tablicami z mieszaniem). Są one najczęściej używanymi modelami abstrakcyjnej struktury słownika, o której była mowa w poprzednim punkcie wykładu.

Przykład 4.1

Niech nr będzie funkcją przypisującą literom alfabetu kolejno liczby od 1 - 26, np. nr(a) = 1, nr(b) = 2 itd. Określimy funkcję h ze zbioru słów w zbiór liczb naturalnych jako sumę wartości przypisanych literom modulo 13: dla dowolnego słowa w =(e₁e₂ ... e_n)

h(w) = (nr(e₁) + nr(e₂) +...+ nr(e_n)) mod 13.

Niech zbiór elementów X składa się z następujących słów:

{antek, piotr, olek, asia, adam, basia, ola, ina}

Wtedy  h(antek) = (1+15+20+5+11) mod 13 = 52 mod 13 = 0 , h(piotr) = (17+9+16+20+18) mod 13 = 80 mod 13 = 2, h(ola) = (16+12+1) mod 13 = 3, itd. Do zapamiętania zbioru X użyjemy tablicy TAB o  13 pozycjach. Wartość funkcji h dla słowa w traktujemy jako adres tego słowa w tablicy TAB. Tablica haszująca reprezentująca zbiór X jest przedstawiona na rysunku 10.2. Pozycje 1, 8, 10, 11 tej tablicy nie są zajęte.

Jeśli pytamy, czy słowo w należy do zbioru reprezentowanego przez tablicę TAB, to wystarczy dla tego słowa wyliczyć wartość funkcji h i sprawdzić co znajduje się na pozycji TAB(h(w)). Jeśli pozycja jest pusta lub znajduje się tam inne, niż w, słowo, to słowo w nie należy do zbioru X. W przeciwnym przypadku w należy do X. Proces dołączenia nowego elementu do zbioru X zaczynamy od wyliczenia adresu, np. dla słowa  "hania", h(hania) = 8. Następnie sprawdzamy, czy wyliczona pozycja jest wolna i, o ile tak jest, wstawiamy nowy element do zbioru. Problem pojawia się wtedy, gdy pod wyliczonym adresem słowa znajduje się już inne słowo. Na przykład, gdybyśmy do naszego zbioru X chcieli dołączyć słowo "kasia", to powstaje tzw. problem kolizji, ponieważ h(kasia)= (11+1+19+9+1) mod 13 = 2, a pozycja TAB(2) jest aktualnie zajęta przez słowo "piotr". Problemom kolizji poświęcimy więcej uwagi w dalszej części wykładu.  J

Przy założeniu, że zbiór elementów nie jest duży i że klucze tych elementów są liczbami naturalnymi {0,1,...,m} i rozróżniają elementy, zbiór dynamiczny możemy reprezentować za pomocą zwykłej tablicy, umieszczając elementy na pozycjach wskazanych przez klucze. Taka reprezentacja zbioru dynamicznego nazywa się adresowaniem bezpośrednim. Po prostu, element o kluczu 2 jest umieszczony bezpośrednio na pozycji drugiej tablicy, albo znajduje się tam referencja do tego elementu. Operacje insert, delete, member, struktury słownika, można  w takim modelu zaimplementować bardzo prosto sprawdzając zawsze najpierw pozycję wskazaną przez klucz. Koszt tych operacji jest więc stały.

Metody haszowania są stosowane zwykle wtedy, gdy zbiory skończone, które chcemy reprezentować są nieduże, ale  uniwersum, z którego pochodzą, jest bardzo duże i nie wchodzi w grę adresowanie bezpośrednie. Jeśli zbiór elementów E składa się ze wszystkich co najwyżej pięcioelementowych słów, a zbiory X z którymi mamy rzeczywiście do czynienia nie są większe niż 13, to nie ma sensu tworzyć tablicy  o (26⁶-1)/25 pozycjach (dla każdego elementu zbioru E osobna pozycja), nawet gdyby to było możliwe, bo taka tablica byłaby prawie pusta. Wystarczy nam tablica 13 elementowa i rozsądny sposób umieszczania elementów w tej tablicy, tak by nie trzeba było jej za każdym razem przeglądać w całości. Musimy więc umieć przypisać elementom konkretnego zbioru X pozycję w tej tablicy.

Ogólnie, niech E będzie uniwersum kluczy, a m przewidywanym rozmiarem podzbioru X używanych przez nas kluczy, przy czym  m < |E|. Funkcją mieszającą (lub haszującą) nazywamy dowolną funkcję z E w {1,..., m}

h : E ® {1,...,m}. 

Tablica z haszowaniem jest uogólnieniem zwykłej tablicy. Jest to para (T, h), gdzie T jest tablicą o m elementach,  h jest funkcją haszującą taką, że h(e) jest tzw. pierwszym adresem elementu e w tablicy T. Wartość h(e) jest używana zawsze wtedy, gdy chcemy sprawdzić, czy element e należy do  zbioru  reprezentowanego przez tablicę haszującą, gdy chcemy dołączyć do zbioru nowy klucz, lub gdy chcemy usunąć klucz. Zatem wybór funkcji haszującej ma znaczenie podstawowe. Zależy nam na tym, by taka funkcja równomiernie rozrzucała elementy uniwersum E w tablicy o m elementach, tzn. aby liczba tych elementów uniwersum E, którym funkcja h przypisuje ten sam adres, odpowiadała stosunkowi |E|/m. W terminologii rachunku prawdopodobieństwa, chcemy aby dla wszystkich x, P(h(x)=i) = 1/m. Są wtedy duże szanse, że nie zdarzy się sytuacja, w której dwa różne elementy zbioru X, którego rozmiar oszacowaliśmy z góry przez m, mają ten sam adres w tablicy haszującej.  Mówimy, że wystąpiła wtedy kolizja.

Oczywiście, jeśli funkcja mieszająca jest różnowartościowa na interesującym nas zbiorze kluczy, to problem kolizji nie wystąpi. Niestety, nigdy nie mamy gwarancji, że nie zdarzy się kolizja. Zanim przystąpimy do rozważań, jak rozwiązać problem kolizji, przedstawimy przykłady funkcji haszujących.

Pytanie 4: Jakie jest prawdopodobieństwo, że dana jednorodna funkcja haszująca, h : {1,...n} ®{1,...m},  jest różnowartościowa?

« poprzedni punkt

następny punkt »