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.
k
z
z
z
...
2
1
kde zi jsou jednotlivé znaky v řetězci a k je počet těchto znaků v řetězci (délka řetězce).
Jedna z jednodušších funkcí je
k
z
asc
z
asc
q
z
asc
p
z
z
z
c
k
k
+
+
∗
+
∗
=
)
(
)
(
)
(
)
...
(
2
1
2
1
1
,
kde p a q jsou zvolené konstanty, nejlépe prvočísla (např. p=127, q=31), protože ty mají nejlepší
předpoklady pro rovnoměrné zobrazení do celých čísel. Funkce asc převádí znak na jeho ASCII
hodnotu.
Dokonalejší, ale na druhé straně náročnější na výpočet, je funkce
)
(
)
(
...
)
(
)
(
)
(
)
...
(
1
3
3
2
2
1
1
2
1
2
k
k
k
k
k
k
z
asc
z
asc
p
z
asc
p
z
asc
p
z
asc
p
z
z
z
c
+
∗
+
+
∗
+
∗
+
∗
=
−
−
−
−
,
kde p je konstanta, opět nejlépe prvočíslo (např. p=31). Pro její výpočet je účelné přepsat ji do
tvaru
(
)
(
)
(
)
)
(
)
(
...
)
(
)
(
)
(
...
)
...
(
1
3
2
1
2
1
2
k
k
k
z
asc
z
asc
z
asc
z
asc
z
asc
p
p
p
p
z
z
z
c
+
+
+
+
∗
∗
∗
∗
=
−
Druhá část hašovací funkce, která převádí celé číslo na číslo řádku v hašovací tabulce, je velmi
jednoduchá. Používá se pro ni operace mod, což je zbytek po celočíselném dělení. Obecný zápis
hašovací funkce je
m
x
c
x
h
mod
)
(
)
(
=
,
kde c(x) je první část hašovací funkce, která nám převádí hodnotu prvku na celé číslo, m je
rozsah (počet řádků) hašovací tabulky. Opět je nejlepší zvolit m prvočíslo, protože to nemá
žádného netriviálního vlastního dělitele, čímž poskytuje nejlepší předpoklady pro rovnoměrné
rozmístění prvků v tabulce.
Příklad. Máme navrhnout hašování pro uložení řetězců. Velikost tabulky požadujeme přibližně
500 řádků.
Nebližší prvočísla jsou 499 a 503, velikost tabulky zvolíme třeba 503 řádků. Pro sestavení
hašovací funkce použijeme již uvedenou funkci c1. Hašovací funkce bude mít tvar: