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.
∗74+3∗97+97+4 = 910
U všech je hodnota hašovací funkce rovna 8, přičemž tato pozice je již obsazena. Zvolíme-li
kvadratické hledání, pak další možné pozice jsou
(8+12) mod 11 = 9
(8+22) mod 11 = 3
(8+32) mod 11 = 6
(8+42) mod 11 = 2
(8+52) mod 11 = 1
Z vypočtených pozic jsou volné pozice 3, 6, 1. Do nich umístíme 3 nová jména:
Číslo řádku
Uložený prvek
0
Ivan
1
Jana
2
Eva
3
Helena
4
5
Nina
6
Bohumil
7
Pavel
8
Marta
9
Irena
10
Příklad. Do tabulky ukládáme stejná jména jako v předchozím příkladě, pro výpočet pozic
použijeme dvojí hašování. Sekundární hašovací funkci bude
(
)
10
mod
)
(
1
)
(
2
x
c
x
h
+
=
.
− 86 −
Její hodnota pro ukládaná jména je
h2(Helena) = h2(Bohumil) = h2(Jana) = 1 + 910 mod 10 = 1
Pro vkládaná jména je hodnota primární funkce rovna 8. Z ní vypočítáme hodnotu sekundární
hašovací funkce
h2(Helena) = h2(Bohumil) = h2(Jana) = 1+(8 mod 5) = 4
Sekundární pozice budou
(8+1) mod 11 = 9
(9+1) mod 11 = 10
(10+1) mod 11 = 0
(0+1) mod 11 = 1
(1+1) mod 11 = 2
(2+1) mod 11 = 3
Z vypočtených pozic jsou volné pozice 10, 1, 3. Do nich umístíme 3 nová jména:
Číslo řádku
Uložený prvek
0
Ivan
1
Bohumil
2
Eva
3
Jana
4
5
Nina
6
7
Pavel
8
Marta
9
Irena
10
Helena
Vyhledávání v tabulce
Při vyhledávání v hašovací tabulce nejprve vypočítáme hodnotu hašovací funkce pro hledaný
prvek x. Podíváme se do tabulky na řádek, na který ukazuje hodnota hašovací funkce. Mohou
nastat případy:
a) Řádek je prázdný – hledaný prvek není v tabulce.
b) Na řádku je hledaný prvek x – vyhledávání tím úspěšně končí.
c) Na řádku je jiný prvek než x. Začneme postupně počítat další možné pozice a srovnávat