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

Termin zajęć: 10/11 maj 2011

**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

===== Przykładowe zadania =====
Poniżej mają Państwo przykładowe zadania z haszowania. W razie znalezienia błędów, prosimy o informację.

**Zadanie 1** \\
Tablica ''TAB'' jest tablicą haszującą w której konflikty są rozwiązywane za pomocą liniowego adresowania otwartego. Zakładamy że tablica ma rozmiar ''m=7'' i jest początkowo pusta. Pomocnicza funkcja haszująca jest funkcją haszowania modularnego, natomiast funkcja obliczająca klucz na podstawie wartości elementu jest dana wzorem: ''k(x) = x*4''. Napisz wzór pomocniczej funkcji haszującej oraz przedstaw stan tablicy ''TAB'' po każdym wstawieniu wartości w następującej kolejności: ''5, 3, 7, 10, 2''. \\
**Rozwiązanie** \\
  * ''h(k,i) = (h'(k)+i)%m''
  * ''h'(k) = k%m''
  * ''TAB = 7, 10, 2, NIL, NIL, 3, 5''

**Zadanie 2** \\
Tablica ''TAB'' jest tablicą haszującą w której konflikty są rozwiązywane za pomocą liniowego adresowania otwartego. Zakładamy że tablica ma rozmiar ''m=7'' i jest początkowo pusta. Pomocnicza funkcja haszująca jest funkcją haszowania modularnego, natomiast funkcja obliczająca klucz na podstawie wartości elementu jest dana wzorem: ''k(x) = 3x+1''. Napisz wzór pomocniczej funkcji haszującej oraz przedstaw stan tablicy ''TAB'' po każdym wstawieniu wartości w następującej kolejności: ''2, 5, 9, 1, 3''. \\
**Rozwiązanie** \\
  * ''h(k,i) = (h'(k)+i)%m''
  * ''h'(k) = k%m''
  * ''TAB = 2, 9, 5, 3, 1, NIL, NIL''

**Zadanie 3** \\
Tablica ''TAB'' jest tablicą haszującą w której konflikty są rozwiązywane za pomocą kwadratowego adresowania otwartego ''h(k,i) = (h'(k) + i² + i)%m''. Zakładamy że tablica ma rozmiar ''m=8'' i jest początkowo pusta. Pomocnicza funkcja haszująca jest funkcją haszowania modularnego, natomiast funkcja obliczająca klucz na podstawie wartości elementu jest dana wzorem: ''k(x) = 2x+1''. Przedstaw stan tablicy ''TAB'' po każdym wstawieniu wartości w następującej kolejności: ''2.5, 2, 9, 5, 1''. \\
**Rozwiązanie** \\
  * ''h'(k) = k%m''
  * ''TAB = NIL, 5, NIL, 9, NIL, 2, 2.5, 1''

**Zadanie 4** \\
Dane jest uniwersum możliwych kluczy: ''U = {2,3,4,5,6,7,8}''. Zaproponuj funkcję ''k(x)'' wyliczającą klucz na podstawie wartości elementu, której przeciwdziedziną jest zbiór ''Y=U''. Następnie wyznacz uniwersalną klasę funkcji haszujących. Dla wybranej funkcji należącej do wyznaczonej rodziny oblicz jej wartości dla każdego klucza należącego do uniwersum. Zakładamy że wartościami elementów mogą być tylko liczby naturalne oraz że rozmiar tablicy haszującej wynosi ''m=8''.\\
**Przykładowe rozwiązanie**
  * ''k(x) = (x%7)+2''
  * ''p = 11''
  * ''Zp = {0,1,...,10}''
  * ''Z*p = {1,2,...,10}''
  * Wybieramy np. ''a=3'', ''b=1''.
    * ''h(k)=[(3*k+1)%11]%8''

**Zadanie 5** \\
Tablica ''TAB'' jest tablicą haszującą o rozmiarze ''m=12'' w której konflikty są rozwiązywane metodą łańcuchową. Funkcja haszująca jest modularną funkcją haszującą. Zakładając że indeksowanie tablicy rozpoczyna się od ''1'' oraz że funkcja obliczająca klucz ma postać ''k(x)=2x+4'' podaj przynajmniej ''5'' różnych wartości elementów, które mogą być zapisane w tablicy pod indeksem ''7''. \\
**Rozwiązanie** \\
  * ''h(k) = (k%12)+1''
  * ''(k%12)+1 = 7''
  * ''k%12 = 6 ⇒ k = 12i+6'', gdzie ''i={0,1,...}''
  * ''12i+6 = 2x+4''
  * ''12i+2 = 2x''
  * ''6i+1 = x'', gdzie ''i={0,1,...}''
  * Co nam generuje ciąg wartości których docelowy indeks to ''7''.

**Zadanie 6** \\
Tablica ''TAB'' jest tablicą haszującą w której konflikty są rozwiązywane za pomocą metody łańcuchowej. Haszowanie jest wykonywane przez mnożenie dla ''A=0.4''. Zakładamy że tablica ma rozmiar ''m=8'' i jest początkowo pusta. Funkcja obliczająca klucz na podstawie wartości elementu jest dana wzorem: ''k(x)=x+8''. Napisz wzór funkcji haszującej oraz przedstaw stan tablicy ''TAB'' po każdym wstawieniu wartości w następującej kolejności: ''3, 1, 7, 11, 4''. \\
**Rozwiązanie** \\
 * Po przetworzeniu powyższych wartości przez funkcję ''k(x)'', powstaje następujący zbiór kluczy \\ ''k = {11,9,15,19,12}''
  * ''h(k) = floor(8*(0.4k%1))''
  * ''TAB = [7], NIL, NIL, [3], [1, 11], NIL, [4], NIL''