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é rozptylová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 je \(\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).
Z pohledu aplikace hashování musíme uvažovat ještě jeden aspekt vkládání, co když je cílové pole již plné? Poté pro vložení nového prvku musíme zvětšit celé pole. Jenže změna velikosti celého pole znamená, že musíme přehashovat všechny prvky. Toto je velmi drahá operace, která nás stojí lineární čas v počtu vložených prvků. V praxi typicky zvětšujeme pole na dvojnásobnou velikost a nečekáme, až bude plné, ale zvětšujeme, jakmile je zaplněno nad určitou hranici. Například v případě zřetězeného hashování ani není možné, aby se pole zaplnilo.
Provádění občasné drahé operace snižuje hodnotu běžné asymptotické složitosti pro určení časové náročnosti postupů využívajících hashovací tabulky. Nejhorší případ je vždy \(\mathrm{O}(n)\), protože může být nutné zvětšit velikost pole. Lepší pohled na složitost těchto postupů nám dává amortizovaná složitost.
Amortizovaná složitost
Amortizovaná složitost je cena nejhorší možné posloupnosti \(n\) instrukcí, rozpočítaná na jednu instrukci. Posloupností instrukcí v tomto případě rozumíme souvislou posloupnost prvních \(n\) operací od začátku výpočtu, nikoliv libovolný úsek uprostřed běhu. Jestliže \(n\) opakování v nejhorším případě vyžaduje čas \(\mathrm{O}(T(n))\), pak na jedno provedení instrukce připadá v průměru přes celou posloupnost čas \(\mathrm{O}(\frac{T(n)}{n})\), a to je amortizovaná složitost jedné instrukce.
Pro určení amortizované složitosti existují tři základní přístupy.
-
Agregační metoda - postupujeme přímo dle definice
-
Účetní metoda - Každému provedení instrukce přiřadíme kredit (amortizovanou cenu) a nespotřebované kredity ukládáme do "banky". Provedení každé instrukce nás něco stojí a tuto cenu musíme pokrýt kredity a zůstatkem v bance. Počáteční zůstatek v bance je 0 a nikdy nemůžeme jít do mínusu.
-
Potenciálová metoda - Nejobecnější, ale také nejsložitější metoda. Každá instrukce pracuje nad nějakou datovou strukturou (polem, stromem, spojovým seznamem, …), před a po provedení každé instrukce je tato struktura v nějakém stavu. Počáteční stav označíme \(D_0\) a stav po provedení \(i\)-té instrukce označíme \(D_i\), každému stavu přiřadíme nezáporné číslo, tzv. potenciál \(\Phi(D_i)\), potenciály musí splňovat \(\Phi(D_i) \geq \Phi(D_0)\). Následně definujeme amortizovanou cenu i-té instrukce jako \(\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})\), kde \(c_i\) je skutečná cena provedení i-té instrukce. Sečteme-li amortizované ceny přes celou posloupnost, tak dostaneme: \(\sum_{i=1}^{n} \hat{c}_i = \sum_{i=1}^{n} (c_i + \Phi(D_i) - \Phi(D_{i-1})) = \sum_{i=1}^{n} c_i + \Phi(D_n) - \Phi(D_0)\). Protože jsme volili potenciály \(\Phi(D_i) \geq \Phi(D_0)\), tak nám součet amortizovaných cen poskytuje horní odhad na součet skutečných cen.
Všechny tři metody si ukážeme na jednoduchém příkladu. Uvažujme vkládání prvků do pole fixní velikosti, jakmile je pole plné, tak při vložení dalšího prvku musíme vytvořit nové pole. Při prvním vložení vytvoříme pole o velikosti \(1\), každé další zvětšení vytvoří dvakrát větší pole a stávající prvky do něj přesuneme. Cena za vložení jednoho prvku a přesun jednoho prvku je \(1\). Počáteční stav je prázdné pole velikosti \(0\) a budeme postupně vkládat \(n\) čísel. Velikost pole po vložení \(i\)-tého prvku označme \(k_i\) a počet prvků v něm označme \(p_i\).
Agregační metoda
V každém kroku platíme \(1\) za vložení nového prvku a navíc platíme za přesun prvků do nového většího pole při zaplnění pole. Zvětšení pole nastane při vloženích číslo \(1, 2, 3, 5, 9, 17, \dots\) a přesouvá se postupně \(0, 1, 2, 4, 8, \dots\) prvků. Celkový počet přesunů při \(n\) vloženích je tedy nejvýše \(1 + 2 + 4 + \dots + 2^{\lfloor \log_2 (n - 1) \rfloor} < 2n\). K tomu připočteme \(n\) samotných vložení a dostáváme \(T(n) < 3n\). Amortizovaná složitost jednoho vložení je tedy \(\mathrm{O}(\frac{3n}{n}) = \mathrm{O}(1)\).
Účetní metoda
Každému vložení přiřadíme kredit \(3\): jedna jednotka zaplatí vložení samotného prvku, jedna se uloží na budoucí přesun tohoto prvku a jedna na přesun jednoho prvku z první poloviny pole, který svůj kredit utratil už při minulém zvětšování. Zvětšujeme-li pole z velikosti \(k\) na \(2k\), přišlo od minulého zvětšení \(\frac{k}{2}\) nových prvků, které v bance nastřádaly \(2 \cdot \frac{k}{2} = k\) jednotek, což přesně pokryje přesun \(k\) prvků. V případě prvního zvětšení zvyšujeme velikost pole z \(0\) na \(1\), nepřesouváme tedy žádné prvky. Banka tedy nikdy nejde do mínusu a amortizovaná složitost vložení je \(\mathrm{O}(1)\).
Potenciálová metoda
Zvolme potenciál \(\Phi(D_i) = 2p_i - k_i\). Ten je nezáporný, protože pole je vždy zaplněné alespoň z poloviny, a platí \(\Phi(D_0) = 0\), takže podmínka \(\Phi(D_i) \geq \Phi(D_0)\) je splněna. Rozlišíme tři případy:
Při prvním vložení vytváříme pole velikosti \(1\). Poté \(c_1 = 1\), \(\Phi(D_0) = 0\) a \(\Phi(D_1) = 2 - 1 = 1\), neboť \(p_1 = 1\) a \(k_1 = 1\), tedy \(\hat{c}_1 = 1 + 1 = 2\).
Pokud se pole nezvětšuje, je \(c_i = 1\) a potenciál vzroste o \(2\), neboť \(p_i = p_{i-1} + 1\) a \(k_i = k_{i-1}\), tedy \(\hat{c}_i = 1 + 2 = 3\).
Pokud se pole zvětšuje z velikosti \(k\) na \(2k\), je \(c_i = k + 1\) (\(k\) přesunů a jedno vložení), \(\Phi(D_{i-1}) = 2k - k = k\) a \(\Phi(D_i) = 2(k+1) - 2k = 2\), tedy \(\hat{c}_i = (k + 1) + 2 - k = 3\).
Ve všech případech je \(\hat{c}_i \leq 3\), amortizovaná složitost vložení je tedy \(\mathrm{O}(1)\).
Amortizovaná vs. průměrná složitost
Průměrná složitost je pravděpodobnostní tvrzení, je to střední hodnota času instrukce s ohledem na očekávané pravděpodobnostní rozdělení vstupů. Ve smyslu průměrné složitosti uvažujeme průměr přes možné vstupy. I když máme vynikající průměrnou složitost, například konstantní, tak klidně může přijít špatný "málo pravděpodobný" vstup, který bude mít mnohem horší složitost.
Amortizovaná složitost je průměr přes posloupnost opakovaných instrukcí, pravděpodobnost v ní nehraje roli, je deterministická a rovnou uvažuje nejhorší možný čas posloupnosti opakovaných instrukcí. Ve smyslu amortizované složitosti uvažujeme průměr přes onu posloupnost. Pokud máme vynikající amortizovanou složitost, tak jedna instrukce může být hodně drahá, ale posloupnost \(n\) instrukcí nebude v průměru horší než amortizovaná složitost.
U hashovacích tabulek se oba pohledy potkávají. Nad kolizemi argumentujeme pravděpodobnostně, nad zvětšováním tabulky amortizovaně. Výsledná záruka pro vložení je proto průměrná amortizovaná \(\Theta(1)\).
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ásledující posloupnost prvků do hashovací tabulky o velikosti \(m = 11\), pomocí otevřeného rozptylová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 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\).