Tablice z haszowaniem.
Tablica z haszowaniem jest uogólnieniem zwykłej tablicy. Jest to
Implementacja operacji słownikowych dla tablicy z adresowaniem
struktura danych służącą do reprezentacji dynamicznych zbiorów
bezpośrednim jest trywialna:
danych, na których wykonywane są operacje słownikowe: INSERT
INSERT(T , x) // dodaj do T element x
(wstaw), SEARCH (szukaj) i DELETE (usuń).
T [key[x]] := x;
Załóżmy, że mamy dany zbiór dynamiczny, którego każdy element
DELETE(T , x) // usuń z T element x
x ma klucz key[x] należący do pewnego zbioru U zwanego
T [key[x]] := NIL;
uniwersum kluczy.
SEARCH(T , k) // wyszukaj w T element o kluczu k
Jeżeli U = {0, 1, . . . , m - 1}, gdzie m jest niewielką liczbą
return T [k];
naturalną oraz żadne dwa różne elementy nie mają identycznych
kluczy, to zbiór dynamiczny możemy reprezentować za pomocą
Każda z tych operacji jest szybka - działa w czasie O(1).
tablicy z adresowaniem bezpośrednim T [0..m - 1]: element o
kluczu k umieszczamy na pozycji k w tablicy. Jeżeli do zbioru nie
należy żaden element o kluczu k, to T [k] = NIL.
Adresowanie bezpośrednie ma jedną podstawową wadę: jeśli zbiór
Rozwiązywanie kolizji metodą łańcuchową.
U jest zbyt duży, to przechowywanie w pamięci komputera tablicy
o rozmiarze |U| może być nierealne. Co więcej, zbiór kluczy
W metodzie łańcuchowej wszystkie elementy, których klucze sa
elementów zbioru dynamicznego może być tak małym podzbiorem
odwzorowywane przez h na tÄ… sama pozycjÄ™ w tablicy, zostajÄ…
uniwersum U, że większość pamięci zarezerwowanej dla T będzie
umieszczone na jednej liście. Na pozycji i w tablicy jest pamiętany
się marnować.
wskaz
nik do początku listy tych wszystkich elementów, dla których
W tablicy z haszowaniem element o kluczu k zostaje umieszczony
funkcja h daje wartość i. Jeśli w zbiorze nie ma takich elementów,
na pozycji h(k), gdzie
to T [i] = NIL.
Implementacja operacji słownikowych:
h : U {0, . . . , m - 1}
INSERT(T , x)
jest funkcjÄ… haszujÄ…cÄ… odwzorowujÄ…cÄ… uniwersum kluczy U w
wstaw x na poczÄ…tek listy T [h(key[x])];
zbiór pozycji tablicy z haszowaniem T [0..m - 1].
DELETE(T , x)
Funkcje haszujące wprowadza się, aby zmniejszyć liczbę
usuń x z listy T [h(key[x])];
potrzebnych pozycji w tablicy z |U| do m. Ceną jaką płacimy za
SEARCH(T , k)
oszczędność pamięci jest możliwość kolizji, tj. sytuacji, w której
wyszukaj element o kluczu k na liście T [h(k)];
funkcja haszująca przypisuje dwu różnym elementom tą samą
pozycjÄ™ w tablicy.
Przykład Analiza haszowania metodą łańcuchową
Rozważmy zbiór dynamiczny o elementach x1, . . . , x8, których
Przypomnienie z wykładu o listach: operacje dodania elementu
klucze oznaczamy odpowiednio k1, . . . , k8.
oraz usunięcia danego elementu z listy dwukierunkowej zajmują
czas O(1), natomiast pesymistyczny czas potrzebny na wyszukanie
Jeśli h : U [0..9] jest funkcją haszującą, taką że
elementu o danym kluczu zależy liniowo od długości listy.
h(k1) = h(k4) = 1, h(k2) = h(k5) = h(k8) = 2,
Przyjmijmy, że wartość funkcji haszującej h(k) można obliczyć w
czasie O(1). Wtedy czas działania operacji INSERT i DELETE dla
h(k3) = h(k7) = 8, h(k6) = 6,
tablicy z haszowaniem wykorzystującym łańcuchową metodę
to tablica z haszowaniem T [0..9] ma postać:
rozwiÄ…zywania kolizji wynosi O(1), natomiast pesymistyczny czas
x8
potrzebny na wyszukanie elementu o kluczu k zależy liniowo od
Ä™!
długości nh(k) listy T [h(k)].
x4 x2 x7
Dla danej tablicy T [0..m - 1], w której znajduje się n elementów,
Ä™! Ä™! Ä™!
jest współczynnik zapełnienia ą określamy jako n/m.
x1 x5 x6 x3
Zauważmy, że ą może być mniejsza, równa lub większa niż 1.
T = [ / Ä™! Ä™! / / / Ä™! / Ä™! / ]
Proste równomierne haszowanie
Niech xi będzie i-tym w kolejności elementem wstawionym do
tablicy i niech ki = key[xi], dla i = 1, . . . , n, i przyjmijmy k0 = k.
Dla i = 0, . . . , n i j = 0, 1, . . . , m - 1 definiujemy zmiennÄ… losowÄ…
Załóżmy, że klucz losowo wybranego elementu jest z jednakowym

prawdopodobieństwem odwzorowywany na każdą z m pozycji w
1 jeśli h(ki) = j
Xij =
tablicy, niezależnie od tego, gdzie trafiają inne elementy. Jeśli
0 jeśli h(ki) = j

spełnione będzie to założenie, to będziemy mówić o prostym
Na mocy założenia o prostym równomiernym haszowaniu mamy
równomiernym haszowaniu.
1 1
Wyznaczymy średni czas działania operacji SEARCH wyszukiwania
E[Xij] = oraz E[XijXpr ] = dla i = p.

m m2
elementu o zadanym kluczu k w dwóch przypadkach. W
pierwszym wyszukiwanie kończy się porażką - szukany element nie
Dla j = 0, 1, . . . , m - 1 oznaczmy przez nj długość listy T [j].
zostaje odnaleziony (żaden element w tablicy nie ma klucza k). W
Zatem n = n0 + · · · + nm-1 a wartoÅ›ciÄ… Å›redniÄ… nj jest
drugim przypadku wyszukiwanie kończy się sukcesem - element o

n n

kluczu k zostaje znaleziony w tablicy.
n
E[nj] = E Xij = E[Xij] = = Ä….
m
i=1 i=1
Załóżmy, że wyszukiwanie kończy się sukcesem. Przyjmujemy, że k
Przy wyszukiwaniu zakończonym porażką, procedura wyszukująca
jest z jednakowym prawdopodobieństwem równe dowolnemu
porównuje k z kluczami wszystkich elementów na liście T [h(k)].
spośród kluczy k1, . . . , kn. Dla i = 1, . . . , n definiujemy
Oczekiwana ilość porównań w tym przypadku wynosi

îÅ‚ Å‚Å‚
1 jeśli ki = k
m-1

Yi =
ðÅ‚
0 jeśli ki = k

E[nh(k)] = E X0jnjûÅ‚ .
j=0
Mamy E[Yi] = 1/n.
n

Ponieważ zmienne X0j i nj = Xij są niezależne, więc Dla dwóch różnych kluczy ki i kj definiujemy
i=1

îÅ‚ Å‚Å‚ 1 jeÅ›li h(ki) = h(kj)
m-1 m-1 Zij =

mÄ…
0 jeśli h(ki) = h(kj)

ðÅ‚
E X0jnjûÅ‚ = E[X0j]E[nj] = = Ä….
m
j=0 j=0
Mamy
m-1

m 1
Doliczając do tego stały czas potrzebny na obliczenie h(k)
E[Zij] = E XilXjl = = .
m2 m
otrzymujemy, że całkowity czas wyszukiwania zakończonego
l=0
porażką wynosi Ś(1 + ą).
Załóżmy ponadto, że zmienne Yi i Zij są niezależne.
Wniosek
Liczba porównań w czasie wyszukiwania elementu x jest o 1
większa od liczby elementów poprzedzających x na liście. Elementy
poprzedzające x ma liście zostały wstawione póz
niej niż x,
ponieważ nowy element jest zawsze wstawiany na początek listy.
Stąd oczekiwana liczba porównań wynosi
îÅ‚ ëÅ‚ öÅ‚Å‚Å‚
Jeśli liczba pozycji w tablicy z haszowaniem jest co najmniej
n n n n n

proporcjonalna do liczby elementów w tablicy, czyli zachodzi
ðÅ‚
E Yi íÅ‚1 + ZijÅ‚Å‚ûÅ‚ = E [Yi] + E[YiZij]
n = O(m), to jednocześnie ą = O(1). W takim wypadku średni
i=1 j=i+1 i=1 i=1 j=i+1
czas wyszukiwania jest ograniczony przez stałą. Ponieważ czas

n n n n n

dodawania i usuwania również wynosi O(1), więc średni czas
1 1 1
= 1 + = 1 + (n - j) = 1 + n - j
wszystkich operacji słownikowych na tablicy z haszowaniem za
nm nm nm
i=1 j=i+1 i=1 i=1 i=1
pomocą łańcuchowej metody rozwiązywania kolizji wynosi O(1).

1 n(n + 1) n - 1 Ä… Ä…
= 1 + n2 - = 1 + = 1 + - .
nm 2 2m 2 2n
Całkowity czas wyszukiwania zakończonego sukcesem (wliczając
koszt obliczenia wartości funkcji haszującej) wynosi
Åš(2 + Ä…/2 + Ä…/2n) = Åš(1 + Ä…).