Tablice haszujące

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

Do przygotowania - teoria na temat:

  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

Do pobrania:

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).

Ćwiczenia i zadania implementacyjne

Punkty oznaczone 8-) należy samodzielnie wykonać w domu, pozostałe punkty stanowią opis, wprowadzenie, zachętę do samodzielnych testów.

Zadanie 1

  • 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.
  • 8-) 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ść.
  • 8-) Dla drugiej funkcji haszującej też bez problemu można wyznaczyć zestaw danych pesymistycznych → JAK? Proszę dopisać operację „psującą” dane dla drugiej funkcji.
  • 8-) Proszę „zepsuć” dane dla pierwszej i drugiej funkcji jednocześnie. Jak teraz poprawić rozłożenie danych w tablicy haszującej?

Zadanie 2

8-) 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, ";
pl/dydaktyka/asd/cwiczenia/2012-hashing.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0