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

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