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.
Je zřejmé, že při čtvrtém pokusu (pro i=3) vypočítat novou pozici jsme se dostali na pozici,
která už předtím byla. Dá se ale ukázat, že to nastane (za předpokladu, že m je prvočíslo), až
když prohledáme nejméně polovinu tabulky. V našem příkladu to nastalo, až když jsme
prohledali 3 pozice, což je více než polovina z 5. V běžném použití, pokud už tabulka není
téměř zaplněna, najdeme nějakou volnou pozici většinou dříve, než projdeme polovinu tabulky.
Ještě propracovanější je metoda dvojího hašování. U ní funkce pro hledání má obecný tvar
m
x
h
i
x
h
i
x
H
mod
))
(
)
(
(
)
,
(
2
∗
+
=
kde h2(x) je další (sekundární) hašovací funkce, která ale nabývá jen hodnoty v rozmezí 1 až m-
1 (tedy ne hodnotu 0).
V praxi se sekundární hašovací funkce h2(x) nejčastěji vytváří přímo z primární hašovací h(x),
která sama je sestavena z nějaké výchozí funkce c(x) a má tvar
m
x
c
x
h
mod
)
(
)
(
=
Z ní použijeme její základní část, funkci c(x), a hašovací funkci h2(x) vytvoříme ve tvaru
− 85 −
))
1
(
mod
)
(
(
1
)
(
2
−
+
=
m
x
c
x
h
Funkci
m
x
h
i
x
h
i
x
H
mod
))
(
)
(
(
)
,
(
2
∗
+
=
upravíme na tvar
=
+
∗
−
+
=
m
x
h
x
h
i
x
h
i
x
H
mod
))
(
)
(
)
1
(
)
(
(
)
,
(
2
2
( )
m
x
h
i
x
H
m
x
h
m
x
h
i
x
h
mod
))
(
)
1
,
(
(
mod
))
(
mod
))
(
1
)
(
((
2
2
2
+
−
=
+
∗
−
+
=
.
Pozice vložení nyní můžeme počítat rekurzívně
)
(
)
0
,
(
x
h
x
H
=
m
x
h
i
x
H
i
x
H
mod
))
(
)
1
,
(
(
)
,
(
2
+
−
=
pro i = 1,2,3,….
Příklad. Do tabulky vytvořené v předchozím příkladu chceme uložit další jména
h(Helena) = c(Helena) mod 11 = 8, kde c(Helena) = 7
∗72+3∗101+97+6 = 910
h(Bohumil) = c(Bohumil) mod 11 = 8, kde c(Bohumil) = 7
∗66+3∗111+108+7 = 910
h(Jana) = c(Jana) mod 11 = 8, kde c(Jana) = 7