wyklad12 drukuj, WIMiIP IS, Algorytmy i Struktóry Danych, Wykłady
[ Pobierz całość w formacie PDF ]
Tablicezhaszowaniem.
Tablicazhaszowaniem
jest uogólnieniem zwykłej tablicy. Jest to
struktura danych słu»¡c¡ do reprezentacji dynamicznych zbiorów
danych, na których wykonywane s¡ operacje słownikowe: INSERT
(wstaw), SEARCH (szukaj) i DELETE (usu«).
Implementacja operacji słownikowych dla tablicy z adresowaniem
bezpo±rednim jest trywialna:
INSERT(
T
,
x
) // dodaj do
T
element
x
T
[
key
[
x
]] :=
x
;
Załó»my, »e mamy dany zbiór dynamiczny, którego ka»dy element
x
ma klucz
key
[
x
]
nale»¡cy do pewnego zbioru
U
zwanego
uniwersum kluczy.
DELETE(
T
,
x
) // usu« z
T
element
x
T
[
key
[
x
]] :=
NIL
;
Je»eli
U
=
{
0
,
1
,...,
m
−
1
}
, gdzie
m
jest niewielk¡ liczb¡
naturaln¡ oraz »adne dwa ró»ne elementy nie maj¡ identycznych
kluczy, to zbiór dynamiczny mo»emy reprezentowa¢ za pomoc¡
tablicyzadresowaniembezpo±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
.
SEARCH(
T
,
k
) // wyszukaj w
T
element o kluczu
k
return
T
[
k
]
;
Ka»da z tych operacji jest szybka - działa w czasie
O
(
1
)
.
Adresowanie bezpo±rednie ma jedn¡ podstawow¡ wad¦: je±li zbiór
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
elementów zbioru dynamicznego mo»e by¢ tak małym podzbiorem
uniwersum
U
, »e wi¦kszo±¢ pami¦ci zarezerwowanej dla
T
b¦dzie
si¦ marnowa¢.
W tablicy z haszowaniem element o kluczu
k
zostaje umieszczony
na pozycji
h
(
k
)
, gdzie
Rozwi¡zywaniekolizjimetod¡ła«cuchow¡.
W
metodzieła«cuchowej
wszystkie elementy, których klucze sa
odwzorowywane przez
h
na t¡ sama pozycj¦ w tablicy, zostaj¡
umieszczone na jednej li±cie. Na pozycji
i
w tablicy jest pami¦tany
wska¹nik do pocz¡tku listy tych wszystkich elementów, dla których
funkcja
h
daje warto±¢
i
. Je±li w zbiorze nie ma takich elementów,
to
T
[
i
] =
NIL
.
Implementacja operacji słownikowych:
INSERT(
T
,
x
)
wstaw
x
na pocz¡tek listy
T
[
h
(
key
[
x
])]
;
DELETE(
T
,
x
)
usu«
x
z listy
T
[
h
(
key
[
x
])]
;
SEARCH(
T
,
k
)
wyszukaj element o kluczu
k
na li±cie
T
[
h
(
k
)]
;
h
:
U
!{
0
,...,
m
−
1
}
jest
funkcj¡haszuj¡c¡
odwzorowuj¡c¡ uniwersum kluczy
U
w
zbiór pozycji tablicy z haszowaniem
T
[
0
..
m
−
1
]
.
Funkcje haszuj¡ce wprowadza si¦, aby zmniejszy¢ liczb¦
potrzebnych pozycji w tablicy z
|
U
|
do
m
. Cen¡ jak¡ płacimy za
oszcz¦dno±¢ pami¦ci jest mo»liwo±¢
kolizji
, tj. sytuacji, w której
funkcja haszuj¡ca przypisuje dwu ró»nym elementom t¡ sam¡
pozycj¦ w tablicy.
Przykład
Analizahaszowaniametod¡ła«cuchow¡
Rozwa»my zbiór dynamiczny o elementach
x
1
,...,
x
8
, których
klucze oznaczamy odpowiednio
k
1
,...,
k
8
.
Je±li
h
:
U
!
[
0
..
9
]
jest funkcj¡ haszuj¡c¡, tak¡ »e
Przypomnienie z wykładu o listach: operacje dodania elementu
oraz usuni¦cia danego elementu z listy dwukierunkowej zajmuj¡
czas
O
(
1
)
, natomiast pesymistyczny czas potrzebny na wyszukanie
elementu o danym kluczu zale»y liniowo od długo±ci listy.
h
(
k
1
) =
h
(
k
4
) =
1
,
h
(
k
2
) =
h
(
k
5
) =
h
(
k
8
) =
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
tablicy z haszowaniem wykorzystuj¡cym ła«cuchow¡ metod¦
rozwi¡zywania kolizji wynosi
O
(
1
)
, natomiast pesymistyczny czas
potrzebny na wyszukanie elementu o kluczu
k
zale»y liniowo od
długo±ci
n
h
(
k
)
listy
T
[
h
(
k
)]
.
h
(
k
3
) =
h
(
k
7
) =
8
,
h
(
k
6
) =
6
,
to tablica z haszowaniem
T
[
0
..
9
]
ma posta¢:
x
8
"
x
4
x
2
x
7
" " "
x
1
x
5
x
6
x
3
T
=
[ /
" "
/ / /
"
/
"
/ ]
Dla danej tablicy
T
[
0
..
m
−
1
]
, w której znajduje si¦
n
elementów,
jest
współczynnikzapełnienia
okre±lamy jako
n
/
m
.
Zauwa»my, »e
mo»e by¢ mniejsza, równa lub wi¦ksza ni» 1.
Prosterównomiernehaszowanie
Niech
x
i
b¦dzie
i
-tym w kolejno±ci elementem wstawionym do
tablicy i niech
k
i
=
key
[
x
i
]
, dla
i
=
1
,...,
n
, i przyjmijmy
k
0
=
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
tablicy, niezale»nie od tego, gdzie trafiaj¡ inne elementy. Je±li
spełnione b¦dzie to zało»enie, to b¦dziemy mówi¢ o
prostym
równomiernymhaszowaniu
.
(
1
je±li
h
(
k
i
) =
j
0
je±li
h
(
k
i
)
6
=
j
X
ij
=
Na mocy zało»enia o prostym równomiernym haszowaniu mamy
Wyznaczymy ±redni czas działania operacji SEARCH wyszukiwania
elementu o zadanym kluczu
k
w dwóch przypadkach. W
pierwszym wyszukiwanie ko«czy si¦ pora»k¡ - szukany element nie
zostaje odnaleziony (»aden element w tablicy nie ma klucza
k
). W
drugim przypadku wyszukiwanie ko«czy si¦ sukcesem - element o
kluczu
k
zostaje znaleziony w tablicy.
m
2
dla
i
6
=
p
.
Dla
j
=
0
,
1
,...,
m
−
1 oznaczmy przez
n
j
długo±¢ listy
T
[
j
]
.
Zatem
n
=
n
0
+
···
+
n
m
−
1
a warto±ci¡ ±redni¡
n
j
jest
1
"
n
X
#
n
X
E
[
X
ij
] =
n
E
[
n
j
] =
E
X
ij
=
m
=
.
i
=
1
i
=
1
E
[
X
ij
] =
1
m
oraz
E
[
X
ij
X
pr
] =
Przy wyszukiwaniu zako«czonym pora»k¡, procedura wyszukuj¡ca
porównuje
k
z kluczami wszystkich elementów na li±cie
T
[
h
(
k
)]
.
Oczekiwana ilo±¢ porówna« w tym przypadku wynosi
Załó»my, »e wyszukiwanie ko«czy si¦ sukcesem. Przyjmujemy, »e
k
jest z jednakowym prawdopodobie«stwem równe dowolnemu
spo±ród kluczy
k
1
,...,
k
n
. Dla
i
=
1
,...,
n
definiujemy
(
1
je±li
k
i
=
k
0
je±li
k
i
6
=
k
E
[
n
h
(
k
)
] =
E
2
4
m
−
X
X
0
j
n
j
3
5
.
Y
i
=
j
=
0
Mamy
E
[
Y
i
] =
1
/
n
.
Dla dwóch ró»nych kluczy
k
i
i
k
j
definiujemy
Poniewa» zmienne
X
0
j
i
n
j
=
n
X
X
ij
s¡ niezale»ne, wi¦c
i
=
1
(
1
je±li
h
(
k
i
) =
h
(
k
j
)
0
je±li
h
(
k
i
)
6
=
h
(
k
j
)
2
4
m
−
X
3
5
=
m
−
X
E
[
X
0
j
]
E
[
n
j
] =
m
Z
ij
=
E
X
0
j
n
j
m
=
.
j
=
0
j
=
0
Mamy
"
m
−
X
#
m
2
=
1
Doliczaj¡c do tego stały czas potrzebny na obliczenie
h
(
k
)
otrzymujemy, »e całkowity czas wyszukiwania zako«czonego
pora»k¡ wynosi
(
1
+
)
.
E
[
Z
ij
] =
E
X
il
X
jl
m
.
l
=
0
Załó»my ponadto, »e zmienne
Y
i
i
Z
ij
s¡ niezale»ne.
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ó¹niej ni»
x
,
poniewa» nowy element jest zawsze wstawiany na pocz¡tek listy.
St¡d oczekiwana liczba porówna« wynosi
Wniosek
E
2
4
n
X
Y
i
0
@
1
+
n
X
Z
ij
1
A
3
5
=
n
X
E
[
Y
i
] +
n
X
n
X
E
[
Y
i
Z
ij
]
Je±li liczba pozycji w tablicy z haszowaniem jest co najmniej
proporcjonalna do liczby elementów w tablicy, czyli zachodzi
n
=
O
(
m
)
, to jednocze±nie
=
O
(
1
)
. W takim wypadku ±redni
czas wyszukiwania jest ograniczony przez stał¡. Poniewa» czas
dodawania i usuwania równie» wynosi
O
(
1
)
, wi¦c ±redni czas
wszystkich operacji słownikowych na tablicy z haszowaniem za
pomoc¡ ła«cuchowej metody rozwi¡zywania kolizji wynosi
O
(
1
)
.
i
=
1
j
=
i
+
1
i
=
1
i
=
1
j
=
i
+
1
n
X
n
X
1
nm
=
1
+
1
nm
n
X
1
nm
n
X
n
X
!
=
1
+
(
n
−
j
) =
1
+
n
−
j
i
=
1
j
=
i
+
1
i
=
1
i
=
1
i
=
1
2
n
.
Całkowity czas wyszukiwania zako«czonego sukcesem (wliczaj¡c
koszt obliczenia warto±ci funkcji haszuj¡cej) wynosi
(
2
+
/
2
+
/
2
n
) = (
1
+
)
.
=
1
+
1
nm
n
2
−
n
(
n
+
1
)
2
=
1
+
n
−
1
2
m
=
1
+
2
−
=
m
[ Pobierz całość w formacie PDF ]