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.
− 84 −
)
1
,
(
,
...
),
2
,
(
),
1
,
(
−
m
x
H
x
H
x
H
Lineární umísťování za sebou vede k vytváření nežádoucích shluků. Shluky zde označují větší
počty za sebou následujících obsazených řádků tabulky. Pokud je vypočítaná primární pozice
obsazená a je přitom uvnitř takového shluku, znamená to při lineárním hledání, že musíme
projít všechny řádky v tomto shluku za primární pozicí, než se dostaneme k nějaké volné
sekundární pozici, abychom prvek do ní mohli uložit. Přitom shluky prodlužují nejen operaci
přidání prvku do tabulky, ale také vyhledávání prvku v tabulce. Při vyhledávání začínáme na
primární pozici a pokud na ní prvek není a tato pozice je přitom obsazena (je na ní jiný prvek),
procházíme sekundární pozice tak dlouho, dokud prvek nenajdeme nebo se nedostaneme
k volné pozici, což je příznakem toho, že hledaný prvek v tabulce není.
Proto místo lineárního hledání se často používá kvadratické hledání. U něho sice také vznikají
shluky, ale už v menší míře. Hašovací funkce používaná pro kvadratické hledání má běžně tvar
m
i
x
h
i
x
H
mod
)
)
(
(
)
,
(
2
+
=
.
U ní je už určitý problém, že během hledání se můžeme touto funkcí dostat znovu na stejnou
pozici, aniž jsme prošli celou tabulku. Nechť například hodnota hašovací funkce h pro nějaký
prvek y je h(y)=3 a mějme tabulku s 5 řádky (m=5). Pak u kvadratického hledání dostáváme
pozice:
H(y,0) = (3+02) mod 5 = 3
H(y,1) = (3+12) mod 5 = 4
H(y,2) = (3+22) mod 5 = 2
H(y,3) = (3+32) mod 5 = 2