12 - Hashovací tabulky
Připomenutí teorie
Přednáška 12 v oddíle Přednášky.
Hashing
Hashing (Rozptylování, Hashování) je klíčová metoda pro implementaci slovníku. Slovník (dictionary) je datová struktura sloužící k ukládání různorodých dat tak, abychom je byli schopni rychle nalézt. Jeho rychlost vychází právě z užití rozptylové (hashovací) funkce. Ta vrací adresy na které umisťujeme jednotlivé prvky (za konstantní čas)
Rozptylová (hashovací) funkce je funkce \(h\) která danému datovému bodu \(x\) přiřadí jednoznačně adresu \(h(x)\) (hash). Ideálně chceme aby:
-
Byla rychlá
-
Vedla k minimu kolizí
-
Rovnoměrně využívala adresy (i blízké klíče na vzdálené adresy)
-
Umisťovala prvky cca “náhodně”
Funkce musí pro stejný klíč vrátit stejnou adresu (stejný hash) neboli \(x = y \implies h(x) = h(y)\). Může se ale stát, že dva různé klíče budou mít stejnou adresu \(x \ne y \land h(x) = h(y)\). Tomuto případu se říká kolize a kolidujícím klíčům říkáme synonyma.
Kolize lze řešit různými způsoby:
-
Zřetězené hashování (Chaining) - Na každé adrese tvoříme spojovaný seznam klíčů se stejnou adresou (hashem).
-
Otevřené hashování (Open-address hashing) - vše vkládáme do stejné tabulky, při kolizi zkoušíme pozice o \(i \cdot k\) polí dál, kde \(i\) je počet kolizí daného klíče a \(k\) se určí pomocí:
-
Linear probing - \(k\) je konstanta, tedy zkoušíme vždy pozici o \(k\) dále (modulo velikost tabulky);
-
Double hashing - \(k = h_2(x)\), čili máme další rozptylovací funkci \(h_2\), která nám určí (povětšinou) rozdílná \(k\) pro rozdílná \(x\).
-
-
Srůstající hashování
Z hlediska složitostí se uvažuje že průměrný případ vložení, hledání i mazání klíče jako \(\Theta(1)\), nejhorší případ je ale \(\mathrm{O}(n)\), kvůli kolizím (kromě vkládání do zřetězeného rozptylování, tam je \(\Theta(1)\), protože vkládáme vždy na začátek seznamu).
Jupyter notebook
Některé následující úlohy jsou také v Jupyter notebooku.
Také na Google Colab.
Řešení jsou dostupná v Jupyter notebooku.
Také na Google Colab.
Řešené úlohy
Řešená úloha 1:
Do nejprve prázdné tabulky s rozptylovací funkcí
\(h(x) = x \ \mathrm{mod}\ 6\) byly vloženy následující prvky v
uvedeném pořadí a celkem nastala jedna kolize.
a) \(6, 12, 24\)
b) \(24, 6, 12\)
c) \(1, 7, 6\)
d) \(5, 6, 7\)
e) \(2, 3, 4\)
Řešení
c), kolidují klíče 1 a 7.
Rozptylování s vnějším zřetězením
Řešená úloha 2: Pro danou rozptylovací funkci \(h(k) = k \ \mathrm{mod}\ 5\) zvolte velikost tabulky a nakreslete stav po vložení prvků následující posloupnosti při vnějším zřetězení prvků.
\(20, 9, 0, 17, 22, 15, 23, 18, 8, 7\)
Řešení
Řešená úloha 3: Doplňte implementaci zřetězeného hashování v Jupyter notebooku.
Řešení
Otevřené rozptylování
Řešená úloha 4: Vložte následudící posloupnost prvků do hashovací tabulky o velikosti \(m = 11\), pomocí otevřeného hashování.
\(5, 6, 1, 10, 13, 18, 14, 30, 0, 8, 16\)
Vkládejte najednou do 3 tabulek, ve dvou uvažujte linear probing s inkrementem 1 a 3, v poslední provádějte double hashing. Hashovací funkce:
Řešení
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
Linear +1 |
0 |
1 |
10 |
18 |
8 |
5 |
6 |
13 |
14 |
30 |
16 |
Linear +3 |
18 |
1 |
10 |
0 |
30 |
5 |
6 |
8 |
13 |
14 |
16 |
Double hash. |
0 |
1 |
10 |
16 |
30 |
5 |
6 |
18 |
13 |
14 |
8 |
Počet kolizí při vkládání:
Vkládané číslo |
5 |
6 |
1 |
10 |
13 |
18 |
14 |
30 |
0 |
8 |
16 |
Celkem |
Linear +1 |
0 |
0 |
0 |
0 |
2 |
1 |
2 |
3 |
0 |
4 |
10 |
22 |
Linear +3 |
0 |
0 |
0 |
0 |
1 |
3 |
1 |
3 |
1 |
6 |
7 |
22 |
Double hashing |
0 |
0 |
0 |
0 |
2 |
1 |
3 |
3 |
0 |
5 |
1 |
15 |
Řešená úloha 5: Doplňte implementaci otevřeného hashování v Jupyter notebooku.
Řešení
Hashování objektů
Další úlohy
Zřetězené rozptylování
⭐ Úloha 7: Pro danou rozptylovací funkci \(h(k) = k \ \mathrm{mod}\ 9\) zvolte velikost tabulky a nakreslete stav po vložení prvků následující posloupnosti při vnějším zřetězení prvků.
\(12, 19, 24, 17, 4, 21, 5, 16, 11, 2\)
Otevřené rozptylování
Úloha 8: Do rozptylovací tabulky velikosti 10 s otevřeným rozptylováním a s rozptylovací funkcí \(h(k) = k \ \mathrm{mod}\ 7\) vložte následujících 6 klíčů.
Použijte strategii Linear Probing s inkrementem 1.
\(12, 23, 15, 29, 22, 14\)
Úloha 9: Do rozptylovací tabulky velikosti 11 s otevřeným rozptylováním a s rozptylovací funkcí \(h(k) = k \ \mathrm{mod}\ 8\) vložte následujících 6 klíčů.
Použijte strategii Linear Probing s inkrementem 3.
\(10, 16, 15, 31, 23, 14\)
⭐ Úloha 10: Do do prázdné tabulky velikosti \(N\), vkládejte klíče: \(27, 23, 2, 28, 17, 7, 14, 30, 12, 21, 11, 1\) Určete počet kolizí v uvedených variantách:
a) \(N = 13\), Linear Probing s inkrementem 1.
b) \(N = 17\), Linear Probing s inkrementem 1.
c) \(N = 17\), Linear Probing s inkrementem 5.
d) \(N = 13\), Double Hashing, \(h_2(k) = 1 + k \ \mathrm{mod}\ 3\).
e) \(N = 13\), Double Hashing, \(h_2(k) = 1 + k \ \mathrm{mod}\ 5\).
f) \(N = 17\), Double Hashing, \(h_2(k) = 1 + k \ \mathrm{mod}\ 5\).