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:

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 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).

Anglicky coalesced hashing, je hashování podobné otevřenému, kde vkládáme prvky do jedné tabulky a v případě kolizí je pak vkládáme odzadu. Každý prvek má navíc ještě ukazatel, který ukazuje na pozici dalšího prvku kde hledat v případě kolize. V tomto je srůstající hashování zase podobné zřetězenému. Jednotlivé metody můžeme dělit podle toho, zda je na konci pole tzv. sklep, tedy část pole kterou nelze adresovat pomocí hashovací funkce (lze do ní vkládat jen při kolizích).

Ř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á úloha 3: Doplňte implementaci zřetězeného hashování v Jupyter notebooku.

Ř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á úloha 5: Doplňte implementaci otevřeného hashování v Jupyter notebooku.

Řešená úloha 6: Uvažujte hash funkci $h(x) = x \ \textrm{mod} \ 9$. Vložte do hashovací tabulky čísla z posloupnosti:

$9, 11, 18, 27, 29, 36, 43, 45, 50$

Jak bude tabulka vypadat pro EISCH a jak pro LISCH?

Řešená úloha 7: Doplňte implementaci metody get pro srůstající hashování v Jupyter notebooku.

Řešená úloha 8: Doplňte implementaci metody insert pro LISCH hashovací tabulku v Jupyter notebooku.

Řešená úloha 9: Doplňte implementaci metody insert pro EISCH hashovací tabulku v Jupyter notebooku.

Řešená úloha 10: Uvažujte hash funkci $h(x) = x \ \textrm{mod} \ 7$ a sklep o velikosti 2. Vložte do hashovací tabulky čísla z (stejné) posloupnosti:

$9, 11, 18, 27, 29, 36, 43, 45, 50$

Jak bude tabulka vypadat pro EICH, LICH a jak pro VICH?

Řešená úloha 11: Co musíme změnit na implementaci LISCH hashovací tabulky, abychom dostali LICH hashovací tabulku v Jupyter notebooku.

Řešená úloha 12: Co musíme změnit na implementaci EISCH hashovací tabulky, abychom dostali EICH hashovací tabulku v Jupyter notebooku.

Řešená úloha 13: Projděte implementaci metody insert pro VICH hashovací tabulku v Jupyter notebooku.

⭐ Úloha 16: 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$

Úloha 17: 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 18: 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 19: 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$.

Úloha 20:

Uvažujte hash funkci $h(x) = x \ \textrm{mod} \ 10$. Vložte do hashovacích tabulek čísla z posloupnosti:

$10, 12, 20, 23, 32, 39, 40$

Jak bude tabulka vypadat pro EISCH a jak pro LISCH?

⭐ Úloha 21:

Uvažujte hash funkci $h(x) = x \ \textrm{mod} \ 8$ a sklep o velikosti 2. Vložte do hashovacích tabulek čísla z (té samé) posloupnosti:

$10, 12, 20, 23, 32, 39, 40$

Jak bude tabulka vypadat pro EICH, LICH a jak pro VICH?

⭐ Úloha 22:

Předpokládejme, že v tabulkách získaných v příkladech 1 a 2, (případně 3 a 4) vyhledáváme pouze klíče v nich uložené a každý klíč stejně často. Která z těchto tabulek je nejvýhodnější?