« poprzedni punkt  « następny punkt 


6. Problem kolizji

Załóżmy, że mamy daną funkcję haszującą jednorodnie rozrzucającą klucze interesującego nas zbioru w tablicy z haszowaniem.

Definicja 4.1   Kolizją nazywamy sytuację, gdy funkcja haszująca  przypisuje ten sam adres więcej niż jednemu elementowi.

W tym punkcie zajmiemy się sprawą rozwiązywania problemów kolizji. Są możliwe różne strategie postępowania, które podzielimy na dwie kategorie: metody, w których klucze o tym samym adresie umieszczamy na specjalnych listach dynamicznych, lub ogólnie, w dodatkowych strukturach,  i metody, w których stosujemy ponowne mieszanie, gdy poprzednie prowadziło do kolizji.

Metoda I Rozwiązywanie kolizji metodą łańcuchową

Metoda ta polega na umieszczaniu kluczy o takim samym adresie na jednej liście wskazywanej przez numer klucza. Tablica haszująca jest w tym przypadku tablicą list. Wyszukiwanie, wstawianie i usuwanie polega na wyliczeniu adresu h(x) klucza x w tablicy, za pomocą funkcji mieszania h, i sprawdzeniu umieszczonej pod tym adresem listy, Tab[h(x)], dowiązaniu nowego klucza lub usunięciu wskazanego klucza z listy. Lista może być zorganizowana jako stos, jako kolejka, czy jako lista uporządkowana. Mogą to być też drzewa BST.

Przykład 6.1

Na rysunku 10.3 przedstawiono tablicę haszującą utworzoną przez sukcesywne wstawianie słów

antek, ola, piotr, asia, adam, ina  basia, aga, jan,  ania,  hela, olek, julka, janek, anna,

których adresy wyliczono zgodnie z funkcją mieszania opisaną w przykładzie 4.1 (suma numerów liter modulo 13), i w której kolizje rozwiązano przez zastosowanie metody łańcuchowej.

                                 
  TAB: 0

 

® antek   ® jan   ® ania   ® hela /  
    1 /                          
    2   ® piotr /                    
    3   ® ola   ® julka   ® janek /        
    4   ® asia /                    
    5   ® olek /                    
    6   ® basia   ® anna /              
    7   ® adam /                    
    8 /                          
    9   ® aga /                    
    10 /                          
    11 /                          
    12   ® ina /                    
                                 
          Rysunek 10.3              
                                 

Ponieważ h(antek) = 52 mod 13 = 0 oraz h(hela) =  h(ania) = h(jan) = 26 mod 13 = 0, więc słowa "hela" "ania" i "jan" spowodowały kolizje i dlatego znalazły się w tej samej liście co "antek". J

Zauważmy, że nadal trzy pozycje są puste.

Załóżmy, że listy kluczy o takich samych adresach są zorganizowane jako kolejki. Algorytmy operacji słownikowych są bardzo proste:

Wynika stąd, że o ile koszt obliczenia wartości funkcji haszującej jest stały, to koszt wykonania operacji zależy od długości kolejek (łańcuchów).

A jak długie mogą być te kolejki? Jeżeli funkcja mieszania jest określona na n elementowym zbiorze kluczy i o wartościach w zbiorze {0,..., m-1},  to w najgorszym razie wszystkie klucze wstawione zostały do tej samej kolejki. Oznaczmy przez a = n/m, współczynnik charakterystyczny funkcji mieszającej. Koszt średni operacji zależy od tego, czy funkcja haszująca równomiernie rozrzuca klucze w tablicy. Załóżmy, że tak jest, tzn. każdy klucz może wpaść pod i-ty adres z jednakowym prawdopodobieństwem.  Wynika stąd, że średnia długość kolejki wynosi a . Zatem koszt średni nieudanego poszukiwania klucza, wymaga, poza wyliczeniem adresu (zakładamy, że ten koszt jest stały), sprawdzenia wszystkich pozycji kolejki. Mamy następujące twierdzenie:

Lemat 6.1   W tablicy z mieszaniem, w której kolizje zostały rozwiązane przez kolejkowanie, a funkcja haszująca równomiernie rozrzuca klucze, zarówno koszt nieudanego poszukiwania jak i koszt skutecznego poszukiwania wynosi średnio Q(1+a), o ile koszt obliczania wartości funkcji mieszającej jest stały.

 Wynika stąd, że koszt operacji słownikowych w tablicach z haszowaniem i kolizjami rozwiązanymi metodą łańcuchową, jest stały.

Metoda II Rozwiązywanie kolizji przez adresowanie otwarte

W tej metodzie zamiast wykorzystywać dodatkową pamięć na elementy, których adresy są takie same, staramy się umieścić je w tablicy na innej pozycji.

W przykładzie 6.1 elementy "jan", "ania" i "hela" możemy umieścić na kolejnych wolnych pozycjach, albo pod adresem wyliczonym za pomocą nowej funkcji mieszającej. Na przykład jeśli numer pierwszej litery słowa potraktujemy jako "awaryjny" adres, to   "jan" zajmie pozycję 10,  "ania" pozycję 1, a "hela" pozycję 8. 

Prostym sposobem na wyszukanie nowego adresu w przypadku kolizji, jest wybranie pierwszego wolnego miejsca. Wymaga to jednak liniowego przeglądania tablicy. Można też wolne miejsca powiązać w łańcuch cykliczny, tak aby zawsze można było szybko dojść do wolnej pozycji, o ile taka istnieje. Jeszcze innym sposobem jest wyliczenie nowej pozycji za pomocą innej funkcji haszującej.  Może się jednak zdarzyć, że otrzymany adres również jest już zajęty. Prowadzi to do ciągu prób, w najgorszym razie o długości równej rozmiarowi tablicy. Oczywiście, jeśli liczba elementów w tablicy jest równa jej wymiarowi, to żadnego nowego elementu nie możemy już wstawić do takiej struktury.

Wiele ciekawych wyników na temat metod rozwiązywania kolizji, wyboru funkcji mieszających, szacowania kosztów operacji  można znaleźć w książkach  Cormen, Leiserson, Rivest, Stein, "Wprowadzenie do algorytmów",  WNT(2004) oraz A. Drozdek, D. Simon "Struktury danych w języku C" WNT(1996). Zainteresowanym polecam tę lekturę.


« poprzedni punkt  « następny punkt