Adresowanie otwarte.
Adresowania otwarte to inny sposób realizacji "tablicy z haszowaniem".
W adresowaniu otwartym używamy jednej dużej tablicy wskazań do elementów
(klucz, wartość).
struct Elem { char *klucz; int wartosc; };
Elem *T[m];
Niech "U" będzie zbiorem kluczy. Używamy następującej dwuargumentowej funkcji
haszującej "h":
h: U x {0, ..., m-1} --> {0, ..., m-1}
przy czym ciąg:
<h(k,0), h(k,1), ... , h(k,m-1)>
musi być permutacją ciągu <0,1, ... ,m-1>.
Ciąg <h(k,0), h(k,1), ... , h(k,m-1)> nazywamy ciągiem kontrolnym
klucza "k".
Operacje wstawiania i wyszukiwania implementujemy następująco:
-
void Wstaw(Elem *e);
ciąg kontrolny klucza "e->klucz" wyznacza kolejność w jakiej poszukujemy
w tablicy T elementu o wartości NULL, któremu można przyporządkować "e"
-
Elem *Szukaj(char *klucz);
ciąg kontrolny klucza "klucz" wyznacza kolejność w jakiej przeszukujemy
tablicę T aby znaleźć element o kluczu "klucz"
(Zauważmy że w wypadku adresowania otwartego tablica T musi być większa
niż liczba wstawianych elementów).
Niech "h2" będzie zwykłą funkcją haszującą, przyjmującą wartości ze
zbioru {0, ..., m-1}.
Można przy jej pomocy skonstruować funkcję "h" na następujące sposoby:
-
adresowanie liniowe;
h(k,i) = (h2(k) + i) mod m
-
adresowanie kwadratowe;
h(k,i) = (h2(k) + c1*i + c2*i^2) mod m
-
adresowanie podwójne;
h(k,i) = (h2(k) + i*h3(k)) mod m
gdzie "h3" jest także zwykłą funkcją haszującą
UWAGA:
musimy zapewnić że "h3(k)" i "m" są względnie pierwsze, np
h2(k)=k mod m; h3(k)=1 + k mod (m-1); gdzie "m" jest liczbą pierwszą
Zadanie 33
Zaimplementuj tablicę z haszowaniem przy pomocy adresowania otwartego,
oraz oblicz:
-
maksymalny czas wyszukiwania elementu o zadanym kluczu
-
średni czas wyszukiwania elementu o zadanym kluczu
dla wszystkich 3 rodzajów funkcji "h(k,i)":
-
adresowanie liniowe
-
adresowanie kwadratowe
-
adresowanie podwójne
Przez "czas" rozumiem liczbę operacji porównywania kluczy. Należy obliczyć
ten czas dla każdego klucza i na tej podstawie wyznaczyć wartość maksymalną
i średnią.
Można użyć (zwykłych) funkcji haszujących z poprzedniej lekcji.
Można także użyć prymitywnej funkcji "suma kodów liter" mod m.
Do testów użyj kluczy z plików "const.txt"
i "modem.txt" oraz losowych napisów.