Tablice haszujące

Termin zajęć: 8./9. maja 2012

1. Rodzaje haszowania
   • haszowanie bezpośrednie
   • haszowanie modularne
   • haszowanie przez mnożenie
   • haszowanie uniwersalne
2. Problem konfliktów podczas haszowania
3. Sposoby rozwiązywania konfliktów
   • Metoda łańcuchowa
   • Metoda adresowania otwartego

Proszę pobrać archiwum hashing.zip, w którym znajdują się pliki potrzebne do wykonania ćwiczeń na zajęciach.

Oto krótki opis plików:

• finduniversumsize.cpp - program obliczający optymalną wielkość tablicy haszującej na podstawie przewidywanej ilości danych i średniej długości łańcucha.
• findnextprime.cpp - program wyszukujący kolejną liczbę pierwszą.
• hchain.h + hchain.cpp - moduł zawierający klasę implementującą tablicę haszującą z łańcuchową metodą rozwiązywania konfliktów.
• hopen.h + hopen.cpp - moduł zawierający klasę implementującą tablicę haszującą z metodą adresowania otwartego. Moduł ten nie wspiera poprawnie usuwania/usuniętych wartości - uzupełnienie będzie jednym z zadań.
• mainmodular.cpp - niezobowiązujący plik pokazujący przykładowe wykorzystanie klas.

Proszę zapoznać się ze strukturą i działaniem poszczególnych klas, przetestować kod i w miarę możliwości przynieść na zajęcia laptopy wraz z wszystkimi plikami (można umówić się na pracę w parach/trójkach i na zajęciach pracować we 2-3 osoby przy jednym komputerze).

• W pobranej paczce jest program finduniversumsize.cpp który służy do wyznaczania wartości m na podstawie ilości przechowywanych danych i zakładanej średniej długości listy.
• Jest też moduł hchain który jest klasą realizującą tablicę haszującą z łańcuchową metodą rozwiązywania konfliktów.
• Zadaniem jest praktyczne przetestowanie tej metody rozwiązywania konfliktów w tablicy o rozmiarze 3584 w której zakładamy że średnia długość listy wynosi 7.
• Proszę zmodyfikować istniejący program, który:
  • tworzy dwie globalne funkcje haszujące typu:

    int f(int val)

  • Obie funkcje obliczają indeks w tablicy haszującej przy pomocy działania modulo:

    return val%m

    gdzie:

    • w pierwszej funkcji haszującej m = 512 (3584/512 = 7),
    • wartość m w drugiej funkcji wyliczona jest przy pomocy programu finduniversumsize.
  • tworzy dwa obiekty klasy hash_chain, których konstruktor przyjmuje następujące wartości:
    • W pierwszym obiekcie:
      • jako rozmiar tablicy: 512,
      • wskaźnik do pierwszej funkcji haszującej.
    • W drugim obiekcie:
      • jako rozmiar tablicy: wartość obliczoną wcześniej przy pomocy programu finduniversumsize,
      • wskaźnik do drugiej funkcji haszującej.
• Do każdego obiektu należy wstawić 3584 losowych wartości z przedziału [0 do np. 10000].
• Po wstawieniu należy wyświetlić informacje o stanie tablicy przy pomocy metody:

  hash_chain::printInfo()

• Powyższe dwie czynności można powtórzyć kilkakrotnie obserwując rozmieszczenie elementów w tablicy, oraz średnie odchylenie od średniej.
• Można zauważyć że w takim przypadku obie funkcje haszujące są mniej więcej tak samo dobre (jednak minimalnie lepsze rezultaty daje ta z obliczoną wartością m).
• Można także próbować manewrować parametrami i obserwować co się dzieje.
• Kolejnym krokiem zadania jest wygenerowanie pesymistycznego przypadku dla pierwszej funkcji haszującej: po wylosowaniu wartości przesuwamy jej bity o np. 2 w lewo i ustawiamy najmniej znaczący
• Obserwujemy co się dzieje. W obiekcie pierwszym rozmieszczenie wartości jest dużo mniej równomierne → wzrasta średnie odchylenie.
  • Można było się tego spodziewać ponieważ reszta z dzielenia przez wartość będącą p-tą potęgą 2 to nic innego jak p najmniej znaczących bitów liczby. Zatem wszystkie generowane indeksy mają takie same wartości dwóch ostatnich bitów.
• Proszę analogicznie przesunąć i dowolnie ustawić 4 bity → wynik: jeszcze gorsza jakość.
• Dla drugiej funkcji haszującej też bez problemu można wyznaczyć zestaw danych pesymistycznych → JAK? Proszę dopisać operację „psującą” dane dla drugiej funkcji.
• Proszę „zepsuć” dane dla pierwszej i drugiej funkcji jednocześnie. Jak teraz poprawić rozłożenie danych w tablicy haszującej?

W paczce znajdują się pliki hopen.cpp i hopen.h które zawierają definicję klasy realizującej tablicę haszującą w której konflikty są rozwiązywane metodą adresowania otwartego. W tej klasie brakuje obsługi wartości usuniętych. Zadanie polega na uzupełnieniu podanej klasy o obsługę tych wartości.
Rozwiązanie jest krótkie: należy:

1. W pliku nagłówkowym dopisać definicję nowej wartości np.

   #define STS_DLTD 2

2. W pliku cpp uzupełnić:
   1. Metodę insert
   2. Metodę remove
   3. Ewentualnie w metodzie wypisującej wartości printValues dopisać jeden warunek:

      else if(_ststab[i] == STS_DLTD)
           cout << "DLTD, ";