====== Tablice haszujące ======

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

===== Do przygotowania - teoria na temat: =====
  - Rodzaje haszowania
    * haszowanie bezpośrednie
    * haszowanie modularne
    * haszowanie przez mnożenie
    * haszowanie uniwersalne
  - Problem konfliktów podczas haszowania
  - Sposoby rozwiązywania konfliktów
    * Metoda łańcuchowa
    * Metoda adresowania otwartego

===== Do pobrania: =====
Proszę pobrać archiwum {{:pl:dydaktyka:asd:cwiczenia: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 =====
<WRAP center round info 60%>
Punkty oznaczone 8-) należy samodzielnie wykonać w domu, pozostałe punkty stanowią opis, wprowadzenie, zachętę do samodzielnych testów.
</WRAP>

==== 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:<code c++>int f(int val)</code>
    * Obie funkcje obliczają indeks w tablicy haszującej przy pomocy działania modulo: <code c++>return val%m</code>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: <code c++>hash_chain::printInfo()</code>
  * 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:
  - W pliku nagłówkowym dopisać definicję nowej wartości np.<code c++>#define STS_DLTD 2</code>
  - W pliku ''cpp'' uzupełnić:
    - Metodę ''insert''
    - Metodę ''remove''
    - Ewentualnie w metodzie wypisującej wartości ''printValues'' dopisać jeden warunek:<code c++>else if(_ststab[i] == STS_DLTD)
     cout << "DLTD, ";</code>