5. Przykłady funkcji mieszających

Funkcja haszująca została zdefiniowana jako odwzorowanie przypisujące kluczom adresy, tzn. pozycje w tablicy haszującej. Jeśli liczba elementów, które chcemy zapamiętać w tablicy haszującej, wynosi n, a liczba możliwych adresów wynosi m, to liczba funkcji mieszających wynosi mⁿ. Liczba funkcji ze zbioru n elementowego w zbiór m elementowy jest, jak widać, bardzo duża. Nie wszystkie jednak z tych funkcji nadają się do naszych celów. Nawet jeśli ograniczymy się do tzw. funkcji doskonałych, tzn. różnowartościowych, to większość z nich nie jest przydatna. Funkcja haszująca, której wartość wylicza się bardzo często, musi mieć prostą defincję a jej wyliczanie powinno być szybkie. Co więcej, zależy nam na tym, by równomiernie rozrzucała elementy danego zbioru kluczy w tablicy.

Zwykle będziemy zakładać, że klucze są liczbami naturalnymi identyfikującymi w pewien sposób elementy rozważanych przez nas zbiorów. Wybór funkcji haszującej zależy od zbioru kluczy, z którymi pracujemy. Kilka, ogólnie znanych i często stosowanych, przykładów funkcji mieszających jest treścią tego punktu.

Dzielenie

Najprostszym przykładem funkcji mieszającej jest funkcja postaci

h(x) = x mod m,

o ile uniwersum kluczy składa się z liczb naturalnych, a m jest rozmiarem tablicy haszującej. Jest to łatwa i szybka funkcją haszująca. Jeśli elementami uniwersum są słowa, to możemy również użyć funkcji mieszającej zdefiniowanej przez dzielenie, ponieważ słowa są reprezentowane przez ciągi bitów, a te z kolei możemy potraktować jako binarną reprezentację pewnej liczby, którą użyjemy jako klucza.

Jeśli litera A jest reprezentowana przez ciąg binarny 00001, B przez 00010,..., L przez 01100,.. to słowo ALA jest reprezentowane przez 000010110000001 (konkatenacja reprezentacji liter). Liczbą odpowiadającą temu ciągowi bitów jest 1409. Zakładając, że tablica haszująca ma 13 elementów, słowo ALA powinno się znaleźć na pozycji piątej, bo 1409 mod 13 = 5.

Przy takiej funkcji mieszającej trzeba unikać pewnych wartości m. Na przykład, gdyby m = 2^p, to wartość h(k) zależałaby tylko od p ostatnich bitów rozwinięcia dwójkowego liczby k. Na przykład, gdybyśmy przyjęli m=16, to wszystkie słowa reprezentowane przez liczby parzyste, znajdowałyby się na pozycjach parzystych, a pozycja słowa zależałaby tylko od czterech ostatnich bitów. Dobra liczba m powinna, w przypadku funkcji mieszającej za pomocą operacji modulo, być liczbą pierwszą, niezbyt bliską potędze dwójki.

Jeśli nic szczególnego nie wiemy o kluczach, to zwykle stosujemy tę właśnie metodę.

Mnożenie

Dla danego parametru q, 0<q<1 niech funkcja mieszająca ma postać:

h(x) = ë(( q ´ x) mod 1) mû.

Wartością funkcji h jest tym razem część dziesiętna iloczynu x i q, wynik mnożymy przez m, i ostatecznie część całkowita wyniku będzie adresem klucza x.

Na przykład, jeśli q = 0.511 oraz m = 13, to słowo ALA, reprezentowane przez ciąg bitów 000010110000001,

h(ALA) = ë(1409´ q) mod 1 )´ mû = ë(719,999 mod 1) ´ mû = ë0,999 ´ m û= 12

zostanie umieszczone na pozycji 12.

Przy takiej funkcji haszującej wartość m nie ma wielkiego znaczenia. Istotna jest natomiast wartość parametru q, która na podstawie teoretycznych badań nie powinna być ani bliska zeru, ani bliska jedności, powinna być natomiast oddalona od nich o (Ö5 -1)/2.

Wycinanie

W tej metodzie do obliczenia adresu wykorzystuje się tylko część klucza. Może to być np. fragment środkowy, albo ostatnie cztery pozycje, albo konkretnie wskazane pozycje. Na ogół pomijamy te fragmenty klucza, które nie rozróżniają dostatecznie dobrze elementów.

Na przykład, gdybyśmy chcieli zapamiętać telefony naszych znajomych z Warszawy, to nie ma sensu brać pod uwagę prefiksu 22, gdyż jest on identyczny dla wszystkich telefonów warszawskich. Jeśli nasz zbiór składa się z imion dziewcząt (Polek), to przy wyliczaniu adresu elementu, nie będziemy brali pod uwagę ostatniej litery, gdyż na ogół jest to litera 'a'.

Kompresja

Załóżmy, że elementy rozważanego uniwersum są reprezentowane przez ciągi bitów. W tej metodzie rozrzucania używamy wszystkich bitów. Dzielimy natomiast cały ciąg na odcinki równej długości i wykonujemy operację XOR na odpowiadających bitach.

Na przykład, jeśli elementami interesującego nas uniwersum są słowa i przypisaliśmy literom liczby, np. tak jak w przykładzie 4.1, to adresem słowa może być suma binarnych reprezentacji liter w sensie operacji XOR traktowana jako liczba z przedziału 0-31. Mamy wtedy

h(antek) = 00001 XOR 01111 XOR 10100 XOR 00101 XOR 01011 = 10100 = (20)₁₀

h(piotr) = 10001 XOR 01001 XOR 10000 XOR 10100 XOR 10010 = 01110 = (14)₁₀.

Zwróćmy uwagę, że operacja XOR jest łączna i przemienna. Wynika stąd, że wszystkie słowa o takich samych literach otrzymają ten sam adres.

Nie będziemy się tu zajmować głębiej funkcjami mieszającymi. Wiele innych przykładów można znaleźć w literaturze. Zauważmy tylko na zakończenie tego punktu, że niezależne od tego, jak zdefiniujemy funkcję mieszającą, zawsze może się zdarzyć, że wystąpi kolizja: różne elementy otrzymają ten sam adres.

Pytanie 5: Jaki jest koszt wyszukania słowa w zbiorze reprezentowanym przez tablicę z haszowaniem stosującą mieszanie opisane w ostatnim przykładzie (kompresja), a jakie gdybyśmy te same elementy umieścili po prostu na kolejnych pozycjach w zwykłej tablicy (zakładamy, że nie wystąpił problem kolizji)?

« poprzedni punkt następny punkt »