11 - Hashovací tabulky I

Přednáška 12 v oddíle 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:

1. Byla rychlá
2. Umisťovala prvky cca “náhodně”
3. Rovnoměrně využívala adresy - i blízké klíče na vzdálené adresy
4. 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á ú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í

Ř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í

Ř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í

Ř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í

Ř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í

Ř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í

Ú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í

Ú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í

Ú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$

Ú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$.