Haszowanie | Informatyka MIMUW

Czy możemy wykorzystać adresowanie bezpośrednie do dowolnych zbiorów? Okazuje się, że tak. Co prawda w pesymistycznym przypadku koszt jednej operacji może wynosić nawet \( O(n) \), jednak w praktycznych zastosowaniach ta metoda sprawuje się doskonale.

W tym rozdziale będziemy zakładać, że elementy uniwersum \( U \) to dodatnie liczby całkowite. Dodatkowo zakładamy, że dysponujemy tablicą \( A[0,\ldots,m-1] \).

Ponieważ elementami mogą być bardzo duże liczby całkowite, nie możemy zastosować metody adresowania bezpośredniego. Jednak możemy wybrać funkcję haszującą:

\( h : U \rightarrow\{ 0,\ldots,m-1\} \)

Funkcja każdemu elementowi uniwersum przypisuje odpowiednie miejsce w tablicy \( A \). Jeśli \( |U|>m \), to z oczywistych względów znajdą się takie pary różnych elementów \( x,y\in U \), dla których \( f(x)=f(y) \). W takim przypadku mówimy o istnieniu kolizji. Właśnie ze względu na ryzyko wystąpienia kolizji musimy nieznacznie zmodyfikować metodę adresowania bezpośredniego - zamiast przechowywać w tablicy wartość logiczną (prawda/fałsz), musimy zapisywać wartość przechowywanego elementu.

Rozwiązywanie kolizji metodą łańcuchową

Jedną z metod rozwiązywania kolizji jest utrzymywanie w każdej komórce tablicy listy elementów do niej przypisanych. Początkowo tablica \( A \) wypełniona jest wartościami nil.

procedure Inicjalizacja; 
begin 
    for i:=0 to m-1 do A[i]:=nil; 
end;

Dodanie elementu \( x \) do tablicy wymaga odczytania jego adresu z funkcji haszującej, a następnie dodania go na początek listy \( A[h(x)] \)

procedure Dodaj(x); 
begin 
    dodaj element  x  na początek listy A[h(x)]  
end;

Sprawdzenie, czy element \( x \) jest w zbiorze, wymaga w pesymistycznym przypadku sprawdzenia całej listy \( A[h(x)] \)

function Szukaj(x); 
begin 
    l:=A[h(x)]; 
    while (l!=nil) do begin 
        if (l.wartość=x) then return element istnieje 
        l:=l.nast; 
    end; 
    return brak elementu 
end;

Usuwanie elementu z tablicy jest bardzo podobne do wyszukiwania i również w pesymistycznym przypadku wymaga sprawdzenia całej listy.

  procedure Usuń(x); 
  begin 
    l:=A[h(x)];p:=nil; 
    while (l!=nil) do begin 
      if (l.wartość=x) then begin 
        { usuwamy element l z listy A[h(x)] } 
        if p=nil then A[h(x)]:=l.nast; 
        else p.nast:=l.nast; 
        return; 
      end 
      p:=l; l:=l.nast; 
    end; 
end;

Analiza metody łańcuchowej

Haszowanie to metoda, która bardzo dobrze sprawdza się w praktyce, zastanówmy się przez chwilę, czy dobre własności tej metody można udowodnić.
Niech:

m oznacza rozmiar tablicy,
n oznacza liczbę elementów, które przetrzymujemy w tablicy,
przez \( \alpha \) oznaczamy współczynnik zapełniania tablicy \( \frac{n}{m} \)

Załóżmy, że dysponujemy idealną funkcją haszującą, dla której przypisanie każda wartość \( h(x) \) jest równie prawdopodobna, czyli \( P(\{h(x)=i\})=\frac{1}{m} \).

Przy takim założeniu oczekiwana długość listy elementów \( A[h(x)] \) ma długość \( \frac{n}{m} \) (oczekiwana liczba sukcesów w n próbach Bernoulli'ego).

Stąd oczekiwana złożoność operacji Szukaj, Dodaj, Usuń wynosi:

\( T(n,m)=\frac{n}{m}+O(1) \)

Wybór funkcji haszujących

Od wyboru dobrej funkcji haszującej w dużej mierze zależy efektywność naszej struktury danych. Niestety, nie można podać ścisłej procedury wyboru takiej funkcji.
Dla liczb całkowitych możemy przykładowo wybrać jedną z następujących funkcji (\( m \) oznacza rozmiar tablicy):

\( f(x)=(x\,\mod\, p)\ \mod\ m \) (gdzie \( p>m \) jest liczbą pierwszą);
\( f(x)=(qx\,\mod\, p)\ \mod\ m \) (gdzie \( p,q \) są liczbami pierwszymi);
\( f_{a,b}(x)=((ax+b)\,\mod\, p)\ \mod\ m \) (gdzie \( p \) jest liczbą pierwszą, \( 1\le a < p \), \( 0 \le b < p \)).

Jeśli nie dysponujemy żadną dodatkową wiedzą na temat elementów które będzie zawierać tablica, rozsądnym rozwiązaniem jest wybór funkcji \( f_{a,b} \) dla losowych wartości \( a,b \).

Adresowanie otwarte

Adresowanie otwarte jest metodą pozwalającą uniknąć utrzymywania list elementów w tablicy haszującej. Oczywiście wymaga to opracowania innej metody rozwiązywania konfliktów. Każda komórka tablicy zawiera teraz wartość NIL lub element zbioru.
Niech \( m \) oznacza rozmiar tablicy haszującej. Zdefiniujmy funkcję \( H(x,k) \), wyznaczającą listę pozycji \( H(x,0),\ldots,H(x,m-1) \), na których może znajdować się element \( x \).
Mając daną funkcję \( h(x) \), możemy zdefiniować \( H(x,k) \), jako:

\( H(x,k)=(h(x)+k)\ \mod\ m \) --- adresowanie liniowe;
\( H(x,k)=(h(x)+a_1\cdot k+a_2\cdot k^2)\ \mod\ m \) --- adresowanie kwadratowe;
\( H(x,k)=(h(x)+h_2(x)\cdot k)\ \mod\ m \) --- podwójne haszowanie, przy czym \( h_2(x) \) jest funkcją haszującą, która przyjmuje wartości z zakresu \( 1,\ldots,m-1 \).

Wyszukiwanie elementów możemy wykonać nieznacznie modyfikując poprzednie rozwiązanie -- zamiast przeszukiwać listę elementów, musimy przeszukać ciąg pozycji zdefiniowany przez funkcję \( H(x,k) \).

function Szukaj(x); 
begin 
   k:=0; 
   while (A[H(x,k)!=nil) do begin 
      if (A[H(x,k)].wartość=x) then return element istnieje 
      k:=k+1; 
   end; 
   return brak elementu 
 end;

Wstawianie elementów możemy wykonać przez analogiczne modyfikacje; usuwanie jest zwykle znacznie trudniejsze.

Filtry Bloom'a

Ciekawym połączeniem adresowania bezpośredniego z haszowaniem są filtry Bloom'a. Polegają one na rozlużnieniu założeń naszej struktury:

ograniczamy się do operacji Dodaj i Szukaj,
pozwalamy na nieprawidłowe odpowiedzi dla operacji Szukaj (jednak z małym prawdopodobieństwem).

Nasza struktura to bitowa tablica o rozmiarze m, początkowo tablica jest wypełniona zerami. Zakładamy również, że mamy do dyspozycji k funkcji haszujących \( h_i(x) : U arrow \{ 0,\ldots,m-1\} \).

Dodanie elementu x sprowadza się do ustawienia wszystkich bitów \( A[h_i(x)] \) dla \( i=1,\ldots,k \) na wartość 1.

 procedure Dodaj(x); 
 begin 
   for i:=1 to k do A[h_i(x)]:=1; 
 end;

Analogicznie, sprawdzenie, czy element x należy do zbioru, wymaga sprawdzenia bitów \( A[h_i(x)] \) dla \( i=1,\ldots,k \). Jeśli wszystkie mają wartość 1, to uznajemy, że element należy do zbioru. Oczywiście powoduje to pewien odsetek błędnych odpowiedzi. Jeśli jednak dobrze dobierzemy funkcje, a wypełnienie tablicy nie będzie zbyt duże, to taka struktura będzie dobrze sprawować się w praktyce.

 function Szukaj(x); 
 begin 
   for i:=1 to k do 
     if A[h_i(x)]=0 then return brak elementu 
   return element istnieje 
 end;