Haszowanie

Zadanie AL6.1. Niech m=13. Zdefiniujmy następujące funkcje haszujące:
h1(k) = k mod m
h2(k) = 1+ (k mod (m-2)).

(A) Prześledź działanie haszowania z adresowaniem otwartym, wariant z adresowaniem liniowym, z funkcją haszującą h(k,i)=(h1(k)+i) mod m w sytuacji, gdy do początkowo pustej (m-elementowej) tablicy T wstawiamy liczby 6, 19, 28, 41, 54, a następnie usuwamy 41 i szukamy potem 54. "Prześledź działanie" oznacza, że dla każdej wstawianej liczby należy wyliczyć pozycje, na jakich były próby wstawienia i pozycję na której ostatecznie było wstawienie.

(B) Prześledź działanie haszowania z adresowaniem otwartym, wariant z adresowaniem kwadratowym, z funkcją haszującą h(k,i)=(h1(k)+i2) mod m w sytuacji, gdy do początkowo pustej (m-elementowej) tablicy T wstawiamy liczby 6, 19, 28, 41, 54, 67, a następnie usuwamy 54 i szukamy potem 67.

(C) Prześledź działanie haszowania z adresowaniem otwartym, wariant z haszowaniem dwukrotnym, z funkcją haszującą h(k,i)=(h1(k)+i*h2(k)) mod m w sytuacji, gdy do (m-elementowej) tablicy T zawierającej elementy 50 (pozycja 11), 69 (pozycja 4), 72 (pozycja 7), 79 (pozycja 1), oraz 98 (pozycja 5), wstawiamy liczbę 14, a następnie usuwamy 98 i szukamy potem 14.

Zadanie AL6.2. (2 pkt.) Celem zadania jest sprawdzenie ilości kolizji w haszowaniu ciągu kluczy, które są napisami, z łańcuchową metodą usuwania kolizji. W tym celu należy zadeklarować tablicę T[m] liczb całkowitych, gdzie T[i] ma zawierać ilość tych kluczy k, dla których h(k)=i. Czyli najpierw trzeba wyzerować tablicę T, a potem dla kolejnych kluczy k wyliczać h(k) i zwiekszać T[h(k)] o 1. Przeprowadzić testy dla dużych (>1000) wartości m ("korzystnych" - liczba pierwsza i "niekorzystnych"), zakładając, że wstawiamy około 2*m kluczy, i wypisywać, jaka jest:
– ilość zerowych pozycji w tablicy T;
– maksymalna wartość w T;
– średnia wartość pozycji niezerowych.

Klucze-napisy do testowania są w pliku 3700.txt. Wykaz liczb pierwszych (przydatnych przy doborze rozmiaru tablicy): pierwsze.txt.

Przykładowe schematy konwersji napisu na liczbę:

abcdef... -> ((256*a+b) XOR (256*c+d)) XOR (256*e+f) ...

abc...x -> (...((111*a+b)*111+c)*111+ ... )*111 +x

W drugim schemacie "111" to przykładowa stała. Działania wykonujemy na długich liczbach bez znaku, ignorując przepełnienia. (jeśli z jakiegoś powodu powyższa konwersja zwróci liczbę ujemną, jest to błąd).

Zadanie AL6.3. (4 pkt.) Zaprogramować – ZGODNIE Z PRZYDZIELONYM WARIANTEM (zapisanym jako komentarz w formularzu z punktacją) – wybrane operacje na tablicy z haszowaniem z adresowaniem otwartym oraz przeprowadzić testy i pomiary:

  1. Operacje przetestować osobno na małej tablicy, z wydrukiem kontrolnym,
  2. testy/pomiary przeprowadzić na tablicy większego rozmiaru, np. rzędu kilku tysięcy.

W tablicy haszowań mają być struktury zawierające dwa pola:

ilosc – typu int
nazwisko – ciąg znaków

Kluczami mają być nazwiska (patrz schematy zamiany w AL6.2). W tablicy haszowań mogą znajdować się wskaźniki na te struktury bądź całe struktury. W pliku nazwiskaASCII (ściągniętym z nieistniejącej już chyba strony www.futrega.org/etc/nazwiska.html) znajduje się wykaz zapisów postaci: [liczba typu int] [nazwisko], które można wykorzystać.

Warianty operacji i pomiarów

Warianty techniki rozwiązywania kolizji Możliwe kombinacje wariantów: [W+OL], [W+OK], [W+OD], [S+OL], [S+OK], [S+OD], [U+OL], [U+OK], [U+OD].