Haszowanie
Zadanie AL6.1. Niech m=13. Zdefiniujmy następujące funkcje haszujące:(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:
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