Tablice z haszowaniem.

(klucz, wartość)

struct Elem { char *klucz; int wartosc; /* ... */ };
  // zawiera parę (klucz, wartość)

void Wstaw(Elem *e);
  // wstawianie pary (klucz, wartość) 

void Usun(Elem *e);
  // usuwanie pary (klucz, wartość)

Elem *Szukaj(char *klucz);
  // znajdowanie pary z podanym kluczem

Uwaga 1: powyżej założyliśmy że klucz jest napisem a wartość jest liczbą całkowita; ta konwencja obowiązuje we wszystkich zadaniach z tej lekcji.

Zauważmy że jeśli zbiór wszystkich kluczy nie jest zbyt duży, to prawdopodobnie możemy każdy klucz utożsamić z pewną liczbą całkowitą, i użyć tej liczby jako indeksu do tablicy wskazującego element zawierający wartość odpowiadająca kluczowi. Co jednak zrobić jeśli zbiór wszystkich kluczy jest "gigantyczny" ? Nie możemy przecież używać "gigantycznej tablicy" !!!

Wtedy problem można rozwiązać przy pomocy tzw funkcji haszującej:

h : "zbiór wszystkich kluczy" |---> {0, ..., m-1}

Dobra funkcja haszująca to taka, że przeciwobrazy elementów ze zbioru {0, ..., m-1} są "w miarę" równej mocy.

Uwaga 2: w poniższych zadaniach często traktujemy "klucz" jako dużą liczbę całkowitą: litery klucza (duże i małe) należy traktować jako "cyfry" z zakresu [0 .. 2*26-1], jest to więc liczba zapisana przy podstawie 2*26=52.
 

Zadanie 32

struct Elem { char *klucz; int wartosc; /* ... */ };
void Wstaw(Elem *e);
void Usun(Elem *e); // ma działać w stałym czasie !!!
Elem *Szukaj(char *klucz);

1. haszowanie przez mnożenie + suma kodów

kluczowi przyporządkowujemy liczbę (int)floor( m * modf(s*A, &x) )
gdzie s = suma kodów liter klucza
oraz gdzie A = (sqrt(5)-1)/2
floor() - zwraca podłogę;  modf() - zwraca część ułamkową
.
2. haszowanie modularne + komb. liniowa kodów i liczb pierwszych

kluczowi przyporządkowujemy liczbę s % m (czyli "s mod m")
gdzie "m" jest liczbą pierwszą
oraz gdzie  s = k_1*a_1 + ... + k_q*a_q  przy czym "k_i" to kody liter klucza
natomiast "a_i" to różne liczby pierwsze (ustalone pierwotnie)
.
3. haszowanie uniwersalne

podobne do poprzedniego, z tym że :
"m" jest liczbą pierwszą >=2*26-1
"a_i" to wybrane losowo elementy zbioru {0, ..., m-1} (wybrane na początku działania programu)
.
4. "prawdziwe"  haszowanie modularne

klucz "k" traktujemy jako dużą liczbę całkowitą (patrz Uwaga 2);
kluczowi przyporządkowujemy k % m

Wskazówka: jak obliczyć wartość "k % m" jeśli "k" jest bardzo dużą liczbą całkowitą ?
niech "k_i" oznacza kolejne cyfry klucza (i=0, ..., q-1), zapisanego przy podstawie "b", przy czym "k_0" jest najbardzej znaczącą cyfrą; możemy obliczyć wartość liczbową klucza następująco:
        s:=k_0;
        for i:=1 to q-1 do s := s*b + k_i
        // "s" zawiera wartość liczbową "k"
okazuje się że wartość "k % m" można obliczyć analogicznie (oczywiscie wymaga to dowodu !?!):
        s:=k_0;
        for i:=1 to q-1 do s := ( s*b + k_i ) mod m
        // "s" zawiera wartość liczbową "k % m"
        // unikamy dużych wartości "s" !!!
.

każde słowo traktujemy jako "klucz", natomiast jego nr porządkowy jako "wartość"

dla danego "pliku ze słowami" należy wypróbować wszystkie funkcje haszujące wymienione wyżej

dla każdej funkcji haszującej należy wykonać następujące czynności:

1. sprawdzić czy nasza tablica z haszowaniem działa poprawnie na dostarczonych danych (czy dla danego klucza zwraca odpowiednią wartość)
2. obliczyć maksymalną długość listy elementów, średnią długość oraz odchylenie standardowe