Funkcje haszujące. Przykłady funkcji haszujących.
Od tej pory będziemy zakładali, że klucze sa liczbami naturalnymi,
Dobra funkcja haszująca powinna spełniać (w przybliżeniu)
czyli U ‚" N.
założenie prostego równomiernego haszowania: losowo wybrany
klucz jest z jednakowym prawdopodobieństwem odwzorowywany
Haszowanie modularne.
na każdą z m pozycji w tablicy, niezależnie od tego, gdzie zostają
W haszowaniu modularnym wartością funkcji haszującej dla klucza
odwzorowane inne klucze.
k jest reszta z dzielenia k przez m.
Niestety spełnienie tego warunku nie jest zazwyczaj możliwe,
k(k) = k mod m
ponieważ rzadko znany jest rozkład prawdopodobieństwa
pojawiania się kluczy, a same klucze mogą nie pojawiać się
niezależnie.
Haszowanie przez mnożenie.
Wartość funkcji haszującej za pomocą mnożenia obliczamy w
Przykład.
dwóch krokach. Najpierw mnożymy klucz k przez stałą A z
Załóżmy, że klucze są losowymi liczbami rzeczywistymi
przedziału (0, 1) i wyznaczamy część ułamkową kA. Następnie
rozłożonymi niezależnie i równomiernie w przedziale [0, 1). Wtedy
mnożymy tą wartość przez m i bierzemy podłogę:
funkcja h : U {0, . . . m - 1} dana wzorem h(k) = mk spełnia
warunek prostego równomiernego haszowania. (Porównaj z
h(k) = m (kA - kA ) .
algorytmem sortowania kubełkowego.)
Haszowanie uniwersalne. Uniwersalna rodzina funkcji haszujÄ…cych.
Jeśli wyobraz
my sobie, że klucze wstawiane do tablicy z
Niech H będzie skończoną rodziną funkcji, które odwzorowują
haszowaniem są dobierane przez  złośliwego przeciwnika , to nie
dane uniwersum kluczy U w zbiór {0, . . . , m - 1}.
można wykluczyć sytuacji, w której wszystkich n kluczy jest
Taką rodzinę będziemy nazywać uniwersalną, jeśli dla każdej pary
odwzorowywanych na tÄ™ samÄ… pozycje w tablicy.
różnych kluczy k, l " U liczba funkcji h " H, dla których
Wtedy czas działania operacji wyszukiwania w tablicy z
h(k) = h(l), wynosi co najwyżej |H|/m.
haszowaniem wynosi Åš(n).
Innymi słowy, jeśli losowo wybierzemy funkcję haszującą h z
Każda ustalona funkcja haszująca jest podatna na tego typu
rodziny H, to prawdopodobieństwo kolizji między k a l (jeżeli
zagrożenie. Skutecznym sposobem na  złośliwego przeciwnika
k = l) wynosi co najwyżej 1/m.

jest losowe dobieranie funkcji haszującej w sposób niezależny od
wstawianych do tablicy kluczy.
Jest ono zatem nie większe niż prawdopodobieństwo kolizji, gdyby
h(k) i h(l) były wybierane losowo i niezależnie ze zbioru
W haszowaniu uniwersalnym funkcja haszujÄ…ca jest dobierana
{0, . . . , m - 1}.
losowo z rodziny funkcji, która ma szczególne własności.
Dowód Twierdzenia 13.1
Przypomnijmy, że ni oznacza długość listy T [i], a ą oznacza
współczynnik zapełnienia tablicy n/m.
Dla każdej pary różnych kluczy k, l przyjmujemy

Twierdzenie 13.1
1 jeśli h(k) = h(l)
Xkl =
Niech h będzie funkcją wybraną losowo z uniwersalnej rodziny
0 jeśli h(k) = h(l)

funkcji haszujących i załóżmy, że h zostaje użyta do rozproszenia n
kluczy w tablicy T [0..m - 1], przy czym do rozwiÄ…zywania kolizji
Z definicji uniwersalnej rodziny funkcji haszujÄ…cych mamy
zastosowano metodę łańcuchową. Wówczas, jeśli klucza k nie ma
E[Xkl] d" 1/m.
w tablicy, to oczekiwana długość listy E[nh(k)] wynosi co najwyżej
Niech Yk będzie zmienną losową równą liczbie kluczy różnych od
ą. Jeśli k jest w tablicy, to oczekiwana długość listy E[nh(k)],
k, które znalazły się w tablicy T na pozycji h(k), czyli
zawierającej k, wynosi co najwyżej 1 + ą.

Yk = Xkl.
Uwaga.
l"T
l=k

Wartości oczekiwane, o których mowa w twierdzeniu, są średnimi
liczonymi po wszystkich możliwych wyborach funkcji haszującej.

1
E[Yk] = E Xkl = E[Xkl] d" .
Zauważmy, że nie przyjmujemy żadnych założeń co do rozkładu
m
l"T l"T l"T
kluczy.
l=k l=k l=k

Wniosek 13.2
Jeśli klucza k nie ma w tablicy, to
Załóżmy, że wykonano dowolny ciąg n operacji SEARCH, DELETE
nh(k) = Yk i |{l : l " T , l = k}| = n. i INSERT na tablicy o m pozycjach z haszowaniem uniwersalnym,

przy rozwiązywaniu kolizji metodą łańcuchową. Wówczas, jeśli
Wówczas
liczba operacji INSERT wynosi O(m), to średni, łączny czas
E[nh(k)] = E[Yk] d" n/m = Ä….
wykonania wszystkich operacji wynosi Åš(n).
Dowód:
Jeśli klucz k jest w tablicy, to ponieważ k jest na liście T [h(k)] i
Ponieważ liczba wstawień do tablicy wynosi O(m), więc ą = O(1).
nie został policzony w zmiennej Yk, wiec
Czasy wykonania pojedynczych operacji INSERT i DELETE sÄ…
nh(k) = Yk + 1 i |{l : l " T , l = k}| = n - 1.

stałe.
Wówczas
Z Twierdzenia 13.1 wynika, że średni czas każdego wyszukiwania
(SEARCH) wynosi O(1).
E[nh(k)] = E[Yk] + 1 d" (n - 1)/m + 1 = 1 + Ä… - 1/m < 1 + Ä….
Z liniowości wartości oczekiwanej otrzymujemy zatem, że
oczekiwany czas wykonania całego ciągu operacji wynosi O(n).
Konstrukcja uniwersalnej rodziny funkcji haszujÄ…cych.
Dla dowolnej pary a " Z", b " Zp definiujemy funkcjÄ™
Wybierzmy liczbę pierwszą p, tak żeby każdy klucz k należał do
p
ha,b : Zp Zm wzorem
przedziału [0..p - 1]. Rozważmy zbiory:
ha,b(k) = ((ak + b) mod p) mod m.
Zp = {0, 1, . . . , p - 1}, Z" = {1, 2, . . . , p - 1}.
p
Na przykład, dla p = 17 i m = 6 mamy h3,4(8) = 5.
RodzinÄ… wszystkich takich funkcji jest
Przypomnienie:
Zbiór Zp tworzy ciało z działaniami dodawania i mnożenia modulo
Hp,m = {ha,b : a " Z", b " Zp}.
p
p. W szczególności, dla dowolnego a " Z" istnieje element
p
odwrotny a-1 " Z", taki że a · a-1 = 1 mod p.
p
Ponieważ parametr a można wybrać na p - 1 sposobów, a b na p
sposobów, więc |Hp,m| = p(p - 1).
Wniosek 13.3
Dla dowolnej pary a " Z", b " Zp funkcja Õa,b : Zp Zp dana
p Twierdzenie 13.4.
wzorem
Hp,m jest uniwersalnÄ… rodzinÄ… funkcji haszujÄ…cych.
Õa,b(k) = ak + b mod p
jest bijekcjÄ…. Istotnie, funkcjÄ… odwrotnÄ… do Õa,b jest Õa-1 .
,-a-1b
Dowód Twierdzenia 13.4
Powyższa bijekcja przeprowadza zbiór X na równoliczny z nim zbiór
Ustalmy parę różnych kluczy k, l z Zp. Musimy wykazać, że
Y = {(r, s) " Zp × Zp : r = s, r = s mod m}.

|{ha,b " Hp,m : ha,b(k) = ha,b(l)}| d" |Hp,m|/m = p(p - 1)/m.
Pozostaje wykazać, że |Y | d" p(p - 1)/m.
Zauważmy, że zbiór po lewej stronie nierówności jest równoliczny
Ustalmy r " Zp i niech i oznacza resztÄ™ z dzielenia r przez m.
ze zbiorem
Elementy Zp, które dają resztę i z dzielenia przez m to:
X = {(a, b) " Z" × Zp : Õa,b(k) = Õa,b(l) mod m}.
p i, i + m, i + 2m, . . . , i + nm,
PrzyporzÄ…dkowanie (a, b) (Õa,b(k), Õa,b(l)) jest bijekcjÄ… zbioru
gdzie i + nm d" p - 1 < i + (n + 1)m. Wśród tych n + 1
Z" × Zp na zbiór wszystkich par (r, s) " Zp × Zp, takich że r = s.

p elementów, n jest różnych od r. Mamy
Istotnie, skoro k = l, to Õa,b(k) = Õa,b(l) na mocy Wniosku 13.3;

ponadto dla dowolnej pary (r, s) " Zp × Zp, takiej że r = s z n d" (p - 1 - i)/m d" (p - 1)/m,

układu kongruencji
czyli zbiór Y zawiera co najwyżej (p - 1)/m par (r, s). Sumując
r = ak + b mod p
po wszystkich r otrzymujemy |Y | d" p(p - 1)/m.
s = al + b mod p
można jednoznacznie wyznaczyć a i b: a = (r - s)(k - l)-1,
Zatem rodzina Hp,m jest uniwersalna.
b = r - ak.