BPC-ALD - Skripta_rev2019_2
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
Hašovací funkce
určuje, na které
místo v tabulce
má být prvek
uložen.
− 83 −
503
mod
)
)
(
)
(
31
)
(
127
(
)
...
(
2
1
2
1
k
z
asc
z
asc
z
asc
z
z
z
h
k
k
+
+
∗
+
∗
=
Příklad. Do tabulky velikosti 11 budeme ukládat řetězce. Hašovací funkci zvolíme
11
mod
)
...
(
)
...
(
1
2
1
2
1
k
k
z
z
z
c
z
z
z
h
=
,
kde
k
z
asc
z
asc
z
asc
z
z
z
c
k
k
+
+
∗
+
∗
=
)
(
)
(
3
)
(
7
)
...
(
2
1
2
1
.
Do tabulky uložíme jména
h(Eva) = (7
∗69+3∗118+97+3) mod 11 = 2
h(Irena) = (7
∗73+3∗114+97+5) mod 11 = 9
h(Pavel) = (7
∗80+3∗97+108+5) mod 11 = 7
h(Marta) = (7
∗77+3∗97+97+5 mod 11 = 8
h(Ivan) = (7
∗73+3∗118+110+4) mod 11 = 0
h(Nina) = (7
∗78+3∗105+97+4) mod 11 = 5
Číslo řádku
Uložený prvek
0
Ivan
1
2
Eva
3
4
5
Nina
6
7
Pavel
8
Marta
9
Irena
10
Kdybychom nyní chtěli do tabulky uložit jméno Helena, jehož hodnota hašovací funkce je
h(Helena) = (7
∗72+3∗101+97+6) mod 11 = 8 ,
zjistíme, že tato pozice už je obsazená jménem Marta. Takové kolize, kdy více prvků se
zobrazuje na stejný řádek hašovací tabulky, se v hašování vyskytují zcela běžně. Uvedeme si
nyní nejpoužívanější způsoby jejich řešení.
4.4.1 Otevřené adresování
Metoda otevřeného adresování počítá v případě, kdy pozice v tabulce vypočítaná hašovací
funkcí je obsazena, další pozice tak dlouho, dokud se nenajde volná pozice anebo se nezjistí, že
tabulka už je zaplněna. Nejjednodušší je lineární hledání, kdy nové pozice počítáme funkcí
m
i
x
h
i
x
H
mod
)
)
(
(
)
,
(
+
=
,
kde h(x) je výchozí hašovací funkce, i je celočíselný parametr a m je rozsah tabulky. Je-li tedy
primární pozice (h(x) = H(x,0)) obsazena, prohledávají se postupně další pozice
Jednou z
možností řešení
konfliktů je
otevřené
adresování.