Adresowanie otwarte. CiÄ…g kontrolny.
W adresowaniu otwartym używamy dwuargumentowej funkcji
W metodzie adresowania otwartego wszystkie elementy sÄ…
haszujÄ…cej.
przechowywane wprost w tablicy.
h : U × {0, 1, . . . , m - 1} {0, 1, . . . , m - 1}
Każda pozycja w tablicy zawiera albo element zbioru
Drugi argument oznacza numer (poczÄ…wszy od 0) w ciÄ…gu pozycji
dynamicznego, albo stałą NIL.
rozpatrywanych w czasie wyszukiwania wolnego miejsca dla klucza
będącego pierwszym argumentem.
Współczynnik zapełnienia ą nie może nigdy przekroczyć 1, aby nie
nastąpiło  przepełnienie tablicy.
Od funkcji h wymaga się, żeby dla każdego klucza k ciąg pozycji
(ciÄ…g kontrolny klucza k)
Wstawianie do tablicy wymaga znalezienia w niej wolnej pozycji.
Kolejność, w jakiej sprawdzamy pozycje w tablicy, zależy od
h(k, 0), h(k, 1), . . . , h(k, m - 1)
wstawianego klucza.
był permutacją pozycji 0, 1, . . . , m - 1 .
W poniższej procedurze zakładamy, że elementami
Wstawianie.
przechowywanymi w tablicy T są same klucze. Na każdej pozycji
znajduje się albo pewien klucz, albo stała NIL (jeśli pozycja jest
Załóżmy, że chcemy stawić element o kluczu k do tablicy T ,
wolna).
używając adresowania otwartego.
HASH-INSERT(T , k)
W tym celu obliczamy pierwszÄ… pozycjÄ™ jego ciÄ…gu kontrolnego:
1. begin
h(k, 0). Jeśli ta pozycja jest wolna, to umieszczamy na niej nasz
2. i := 0
element.
3. repeat
4. j := h(k, i);
Jeśli pozycja jest zajęta, to obliczamy następną pozycję ciągu
5. i := i + 1;
kontrolnego: h(k, 1) i jeśli jest ona wolna, to umieszczamy na niej
6. until T [j] = NIL lub i = m;
nasz element. Jeśli ta pozycja również jest zajęta to sprawdzamy
7. if T [j] = NIL
następną: h(k, 2).
8. then begin
9. T [j] := k;
Postępujemy w ten sposób tak długo, aż znajdziemy wolną pozycję,
10. return j;
na którą możemy wstawić element, albo aż sprawdzimy wszystkie
11. end
pozycje ciągu kontrolnego h(k, 0), h(k, 1), . . . , h(k, m - 1) i okaże
12. else error  przepełnienie ;
się, że w tablicy nie ma wolnego miejsca.
13. end;
Wyszukiwanie.
Poniższa procedura dla danej tablicy T i klucza k daje w wyniku
liczbę j, jeśli na pozycji j-tej w tablicy T znajduje się k, albo stałą
Algorytm wyszukiwania klucza k przeglÄ…da ten sam ciÄ…g pozycji,
NIL, jeżeli k nie występuje w ogóle w tablicy T .
które odwiedził algorytm wstawiania, gdy klucz k był dodawany do
tablicy. HASH-SEARCH(T , k)
1. begin
Dlatego wyszukiwanie można przerwać, gdy napotkamy na pustą
2. i := 0
pozycję, ponieważ klucz k byłby wstawiony na tą pozycję i na
3. repeat
pewno nie na żadną dalszą pozycję w jego ciągu kontrolnym.
4. j := h(k, i);
5. i := i + 1;
Zauważmy, że to rozumowanie jest uzasadnione tylko jeśli
6. until T [j] = k lub T [j] = NIL lub i = m;
założymy, że w międzyczasie nie usuwamy żadnych elementów z
7. if T [j] = k
tablicy.
8. then return j
9. else return NIL;
W zastosowaniach, które wymagają usuwania kluczy, do
10. end;
rozwiązywania kolizji używa się raczej metody łańcuchowej.
Równomierne haszowanie. Adresowanie liniowe
Dla celów analizy przyjmujemy, że spełniony jest warunek
W metodzie adresowania liniowego stosuje siÄ™ funkcjÄ™
równomiernego haszowania: zakładamy, że dla każdego klucza
wszystkie m! permutacje zbioru {0,1,. . . ,m-1} sÄ… jednakowo h(k, i) = (h (k) + i) mod m
prawdopodobne jako jego ciÄ…gi kontrolne.
dla i = 0, 1, . . . , m - 1, gdzie
Warunek ten jest uogólnieniem pojęcia prostego równomiernego
haszowania na sytuację, w której wartościami funkcji haszującej nie
h : U {0, 1 . . . , m - 1}
są same pozycje, ale całe ciągi kontrolne.
jest zwykłą funkcją haszującą, zwaną pomocniczą funkcją
W praktyce trudno jest spełnić warunek równomiernego
haszujÄ…cÄ….
haszowania.
Dla danego klucza k, jego ciąg kontrolny ma postać:
Zwykle stosuje się jeden z trzech sposobów obliczania ciągów
h (k), h (k) + 1, . . . , m - 1, 0, 1, . . . , h (k) - 1
kontrolnych: adresowanie liniowe, kwadratowe i haszowanie
dwukrotne. Żadna z tych metod nie spełnia warunku
Ponieważ pierwsza pozycja wyznacza cały ciąg jednoznacznie, więc
równomiernego haszowania, ponieważ wszystkie mogą generować
w metodzie adresowania liniowego jest generowanych tylko m
co najwyżej m2 różnych ciągów kontrolnych, podczas gdy
różnych ciągów kontrolnych.
równomierne haszowanie wymaga m! ciągów.
Adresowanie liniowe - przykład
Wstawiamy klucze do początkowo pustej tablicy T [0..10] używając
adresowania liniowego, z funkcjÄ… pomocniczÄ…
Adresowanie liniowe jest bardzo proste, ale ma poważną wadę
polegającą na grupowaniu się zajętych pozycji.
h (k) = k mod 11
klucz sprawdzane pozycje pozycja końcowa Grupy zajętych pozycji pojawiają się, ponieważ pusta pozycja
43 h(43, 0) = 10 10 poprzedzona przez i zajętych pozycji jest następnie zapełniana z
prawdopodobieństwem (1 + i)/m.
12 h(12, 0) = 1 1
10 h(10, 0) = 10, h(10, 1) = 0 0
Spójne ciągi zajętych pozycji powiększają się, co powoduje wzrost
16 h(16, 0) = 5 5
średniego czasu wyszukiwania.
33 h(33, 0) = 0, h(33, 1) = 1, h(33, 2) = 2 2
34 h(34, 0) = 1, h(34, 1) = 2, h(34, 2) = 3 3
Tablica T :
i 0 1 2 3 4 5 6 7 8 9 10
T [i] 10 12 33 34 16 43
Adresowanie kwadratowe Adresowanie kwadratowe - przykład
Wstawiamy klucze do początkowo pustej tablicy T [0..10] używając
W adresowaniu kwadratowym stosuje siÄ™ funkcje postaci
adresowania kwadratowego
h(k, i) = (h (k) + c1i + c2i2) mod m,
h(k, i) = ((k mod 11) + i + i2) mod 11
gdzie h jest pomocniczÄ… funkcjÄ… haszujÄ…cÄ…, c1 i c2 = 0 sÄ…

klucz sprawdzane pozycje pozycja końcowa
pewnymi stałymi, a i = 0, 1, . . . , m - 1.
43 h(43, 0) = 10 10
12 h(12, 0) = 1 1
Aby mieć gwarancję, że w razie potrzeby zostanie przeszukana cała
10 h(10, 0) = 10, h(10, 1) = 1, h(10, 2) = 5 5
tablica, liczby c1, c2 i m muszą być odpowiednio dobrane, tak żeby
16 h(16, 0) = 5, h(16, 1) = 7 7
ciąg kontrolny każdego klucza był permutacją ciągu
33 h(33, 0) = 0 0
0, 1, . . . , m - 1 .
34 h(34, 0) = 1, h(34, 1) = 3 3
Tablica T :
Ponieważ pierwsza pozycja wyznacza jednoznacznie cały ciąg
kontrolny, więc korzysta się tylko z m różnych ciągów.
i 0 1 2 3 4 5 6 7 8 9 10
T [i] 33 12 34 10 16 43
Haszowanie dwukrotne
Aby mieć gwarancję, że w razie potrzeby przeszukana zostanie cała
W haszowaniu dwukrotnym funkcja haszująca ma postać
tablica, musimy zapewnić, że wartość h2(k) jest względnie
pierwsza z rozmiarem tablicy m.
h(k, i) = (h1(k) + ih2(k)) mod m,
Warunek ten można łatwo spełnić dobierając pewną potęgę 2 jako
gdzie h1 i h2 sÄ… pomocniczymi funkcjami haszujÄ…cymi.
m oraz taką funkcję h2, która daje tylko wartości nieparzyste.
PierwszÄ… pozycjÄ… w ciÄ…gu kontrolnym klucza k jest h1(k); kolejne
Inny sposób polega na wyborze liczby pierwszej jako m oraz takiej
pozycje sÄ… oddalone od poczÄ…tkowej o h2(k) modulo m.
funkcji h2, której wartościami są liczby dodatnie mniejsze niż m.
Tutaj ciąg kontrolny zależy na dwa sposoby od k, tj. sama pozycja
Na przykład dla liczby pierwszej m można przyjąć
początkowa nie określa go jednoznacznie.
h1(k) = k mod m, h2(k) = 1 + (k mod m ),
Haszowanie dwukrotne ma tÄ™ przewagÄ™ nad adresowaniem
liniowym i kwadratowym, że dopuszcza użycie m2 różnych ciągów
gdzie m jest nieco mniejsze niż m (np. m - 1).
kontrolnych (a nie tylko m), ponieważ każda para (h1(k), h2(k))
wyznacza inny ciÄ…g kontrolny.
Haszowanie dwukrotne - przykład
Lemat 14.1
Dla dowolnej rodziny zdarzeń A1, A2, . . . , An zachodzi
Wstawiamy klucze do początkowo pustej tablicy T [0..10] używając
haszowania dwukrotnego
Pr(A1 )" A2 )" · · · )" An) =Pr(A1) · Pr(A2|A1) · Pr(A3|A1 )" A2) · · ·
h(k, i) = ((k mod 11) + i(1 + (k mod 10))) mod 11 · · · Pr(An|A1 )" A2 )" · · · )" An-1)
klucz sprawdzane pozycje pozycja końcowa
Dowód. Przekształcamy prawą stroną korzystając z definicji
43 h(43, 0) = 10 10
prawdopodobieństwa warunkowego.
12 h(12, 0) = 1 1
10 h(10, 0) = 10, h(10, 1) = 0 0
Pr(A1) · Pr(A2|A1) · Pr(A3|A1 )" A2) · · ·
16 h(16, 0) = 5 5
· · · Pr(An|A1 )" A2 )" · · · )" An-1) =
33 h(33, 0) = 0, h(33, 1) = 4 4
Pr(A1 )" A2) Pr(A1 )" A2 )" A3)
34 h(34, 0) = 1, h(34, 1) = 6 6
= Pr(A1) · · · · ·
Pr(A1) Pr(A1 )" A2)
Tablica T :
Pr(A1 )" A2 )" · · · )" An)
· · · = Pr(A1 )" A2 )" · · · )" An)
i 0 1 2 3 4 5 6 7 8 9 10
Pr(A1 )" A2 )" · · · )" An-1)
T [i] 10 12 33 16 34 43
Lemat 14.2 Analiza adresowania otwartego.
Jeżeli zmienna losowa X przyjmuje wartości ze zbioru liczb
naturalnych, to
"

AnalizÄ™ adresowania otwartego przeprowadzimy dla ustalonego
E[X] = Pr(X e" i).
współczynnika zapełnienia ą = n/m.
i=1
Ponieważ na każdej pozycji może znajdować się co najwyżej jeden
Dowód:
element, więc n d" m, czyli ą d" 1.
"

Zakładamy, że spełniony jest warunek równomiernego haszowania:
E [X] = iPr(X = i) =
prawdopodobieństwo wystąpienia każdego ciągu kontrolnego jest
i=0
"
takie samo.

= i(Pr(X e" i) - Pr(X e" i + 1)) =
i=0
Twierdzenie 14.3
"

Jeśli ą < 1, to oczekiwana liczba sprawdzanych pozycji w czasie
= Pr(X e" i),
wyszukiwania elementu, którego nie ma w tablicy, jest nie większa
i=1
niż 1/(1 - ą).
ponieważ każdy składnik Pr(X e" i) jest dodany i razy i odjęty
i - 1 razy (oprócz składnika Pr(X e" 0), który jest dodany 0 razy i
nie odjęty w ogóle).
Dowód. Niech X będzie zmienną losową równą liczbie
sprawdzanych pozycji i niech Ai będzie zdarzeniem, że wykonywane
jest i-te sprawdzenie, a sprawdzana pozycja jest zajęta.
Zauważmy, że n < m daje (n - j)/(m - j) d" n/m dla 0 d" j d" m.
Wówczas zdarzenie X e" i jest iloczynem zdarzeń
Zatem dla 1 d" i d" m mamy
A1 )" A2 )" · · · )" Ai-1.
i-1
n n - 1 n - 2 n - i + 2 n
Na mocy Lematu 14.1 mamy
Pr(X e" i) = · · · · · d" = Ä…i-1.
m m - 1 m - 2 m - i + 2 m
Pr(A1 )" A2 )" · · · )" Ai-1) =Pr(A1) · Pr(A2|A1) · Pr(A3|A1 )" A2) · · ·
StÄ…d i z Lematu 14.2 mamy
· · · Pr(Ai-1|A1 )" A2 )" · · · )" Ai-2)
" " "

1
Pr(A1) = n/m, bo jest n elementów i m pozycji. E[X] = Pr(X e" i) d" ąi-1 = ąi = .
1 - Ä…
i=1 i=1 i=0
Dla j > 1 prawdopodobieństwo, że wykonywane jest j-te
sprawdzenie, a sprawdzana pozycja jest zajęta, przy założeniu że
pierwszych j - 1 pozycji było zajętych, wynosi
(n - j + 1)/(m - j + 1), bo na niesprawdzonych m - j + 1
pozycjach jest n - j + 1 elementów.
Jeśli tablica jest wypełniona w połowie, to oczekiwana liczba
porównań jest nie większa niż 2, a jeśli jest wypełniona w 90
Twierdzenie 14.5
procentach, to średnia liczba porównań jest nie większa niż 10.
Załóżmy, że ą < 1. Wtedy oczekiwana liczba sprawdzeń pozycji w
tablicy wykonywanych w czasie wyszukiwania elementu, który
1 1
Wniosek 14.4
znajduje się w tablicy, jest nie większa niż ln , zakładając,
Ä… 1 - Ä…
Wstawianie elementu wymaga średnio co najwyżej 1/(1 - ą)
że każdy klucz znajdujący się w tablicy jest z jednakowym
sprawdzeń pozycji w tablicy.
prawdopodobieństwem tym wyszukiwanym.
Dowód. Element może zostać wstawiony tylko wtedy, kiedy jest w
Dowód: Wyszukiwanie elementu k wymaga wykonania takiego
niej wolne miejsce, czyli Ä… < 1.
samego ciągu sprawdzeń, jak w czasie jego wstawiania.
Wstawienie elementu wymaga znalezienia w tablicy wolnej pozycji,
Z wniosku 14.4 wynika, że jeśli k był (i + 1)-szym elementem
na której będzie można go zapisać.
wstawianym do tablicy, to oczekiwana liczba sprawdzeń
potrzebnych do jego odszukania jest nie większa niż
Aby znalez
ć takie wolne miejsce, wystarczy wykonać procedurę
1/(1 - i/m) = m/(m - i).
wyszukiwania wstawianego elementu, co wymaga średnio co
najwyżej 1/(1 - ą) sprawdzeń pozycji na mocy Twierdzenia 14.3.
Uśredniając po wszystkich n kluczach znajdujących się w tablicy,
otrzymujemy
n-1 n-1 m

1 m m 1 1 1
= =
n m - i n m - i Ä… k
i=0 i=0 k=m-n+1

m
1 dx 1 m 1 1
d" = ln = ln
Ä… x Ä… m - n Ä… 1 - Ä…
m-n
Jeśli tablica jest wypełniona w połowie, to oczekiwana liczba
porównań jest mniejsza niż 1,387, a jeśli jest wypełniona w 90
procentach, to średnia liczba porównań jest mniejsza niż 2,559.