====== 11 - Hashovací tabulky I ======
/*
Toto cvičení prochází úpravou, zatím využijte následující zdroj.
{{:courses:a4b33alg:cvi12.pdf| pdf}}
*/
==== Připomenutí teorie ====
Přednáška 12 v oddíle [[courses:b4b33alg:prednasky|Přednášky]].
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á
- Umisťovala prvky cca "náhodně"
- Rovnoměrně využívala adresy - i blízké klíče na vzdálené adresy
- Vedla k minimu //kolizí//
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**.
Kolize lze řešit různými způsoby:
* Zřetězené rozptylová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$.
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).
==== Řešené úlohy ====
**Řešená úloha 1:**
Hashovací (=rozptylovací) funkce \\
**a)** převádí adresu daného prvku na jemu příslušný klíč \\
**b)** vrací pro každý klíč jedinečnou hodnotu \\
**c)** pro daný klíč vypočte adresu \\
**d)** vrací pro dva stejné klíče různou hodnotu
++++ Řešení |
**c)**, je to zobrazení z klíčů do adres (hashů), nevrací jedinečné hodnoty pro každý klíč - mohou nastávat kolize.
++++
-----
**Řešená úloha 2:**
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 3:**
Metoda hashování s vnějším zřetězením \\
**a)** nemá problém s kolizemi, protože při ní nevznikají \\
**b)** dokáže uložit pouze předem známý počet klíčů \\
**c)** ukládá synonyma do samostatných seznamů v dynamické paměti \\
**d)** ukládá synonyma spolu s ostatními klíči v poli \\
**e)** ukládá posloupnosti synonym v souvislém úseku adres
++++ Řešení |
**c)**, kolize vznikají vždy, ostatní možnosti platí pro otevřené rozptylování.
++++
----
**Řešená úloha 4:**
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í |
{{ :courses:b4b33alg:cviceni:11_04_chaining.svg?400 |}}
++++
-----
=== Otevřené rozptylování ===
**Řešená úloha 5:**
V otevřeném rozptylování \\
**a)** je nutno definovat rozsah hodnot klíčů \\
**b)** je počet uložených prvků omezen velikostí pole \\
**c)** je nutno po určitém počtu kolizí zvětšit velikost pole \\
**d)** je možno uložit libovolný počet synonym
++++ Řešení |
**b)**, pole zvětšujeme ne na základě kolizí (obecně) ale na základě naplněnosti. Počet uložitelných klíčů je totiž omezen velikostí pole.
++++
-----
**Řešená úloha 6:**
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:
$$h_1(x) = x \;\mathrm{mod}\; 8, h_2(x) = (x \;\mathrm{mod}\; 7) + 1$$
++++ Ř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 |
++++
-----
==== Další úlohy ====
**Úloha 7:**
Cluster (u metody otevřeného rozptylování)
**a)** je posloupnost synonym uložená v souvislém úseku adres \\
**b)** je posloupnost klíčů uložená v souvislém úseku adres \\
**c)** je posloupnost synonym uložená v dynamické paměti \\
**d)** u otevřeného rozptylování nevzniká
++++ Řešení |
**b)**, nemusí jít o synonyma
++++
-----
**Úloha 8:**
Double hashing
**a)** má stejnou pravděpodobnost vzniku dlouhých clusterů jako linear probing \\
**b)** je metoda ukládání klíčů na dvě různá místa \\
**c)** je metoda minimalizace délky clusterů u metody otevřeného rozptylování \\
**d)** má vyšší pravděpodobnost vzniku dlouhých clusterů než linear probing
++++ Řešení |
**c)**, protože klíče nemají stejné inkrementy (povětšinou)
++++
-----
=== Zřetězené rozptylování ===
**Úloha 9:**
Rozptylovací tabulka o velikosti $m$ se zřetězeným
rozptylováním obsahuje $n$ prvků. Složitost nejhoršího
případu, který může při vložení dalšího klíče nastat, je:
**a)** $\Theta(n)$ \\
**b)** $\Theta(m)$ \\
**c)** $\Theta(m/n)$ \\
**d)** $\mathrm{Ο}(1)$ \\
**e)** $\Theta(\log n)$
----
**Úloha 10:**
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 11:**
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 12:**
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 13:**
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$.
----