Slovník

• dynamický datový typ pro reprezentaci množiny objektů s operacemi
  • Insert(S,c) do množiny $S$ přidá objekt $x$
  • Search(S,x) zjistí, zda množina $S$ obsahuje objekt $x$
  • Delete(S,x) z množiny S odstraní objekt $x$
• vhodné datové struktury
  • seznam: složitost $\mathcal{O}(n)$
  • vyhledávací strom: lze-li porovnat, složitost $\mathcal{O})\log n)$
• cíl: složitost všech
  • v nejhorším případě $\mathcal{\theta}(n)$
  • v očekávaném případě$\mathcal{O}(1)$ (Složitost operací může být konstantní až lineární, když jsi uděláme sekvenci a udělám průměr → bude směřovat ke konstantní složitosti)

Přímé adresovaní

• předpoklad:
  • každý objekt reprezentované množiny prvků má unikátní klíč z univerza $U = {0,1,…,m-1}$
• implementace
  • tabulka (pole) $T[0…m-1]$
  • každý slot (pozice) v $T$ odpovídá jednomu klíči z $U$
  • když reprezentovaná množina obsahuje objekt $x$ s klíčem $k$, tak $T[k]$ obsahuje ukazatel na $x$
  • v opačném případě je $T[k]$ prázdné (None)
• složitost operací je konstantní
• výhody
  • konstantní složitost operací
  • jednoduchá implementace
• nevýhody
  • v případě, že univerzum $U$ je veliké, tak uchovávání tabulky velikosti univerza je neefektivní / nemožné
  • v případě, že množina aktuálně uložených klíčů je malá ve srovnání s velikostí univerza, tak větší část paměti alokované pro tabulku T je nevyužita
  • problém objeků se stejným klíčem

Hašovací tabulka

• předpoklady
  • každý prvek reprezentované množiny má klíč z univerza $U$
  • hašovací funkce $h : U \rightarrow {0,1,…,m-1}$
• implementace
  • tabulka (pole) $T[0…m-1]$
  • když reprezentovaná množina obsahuje prvek $x$ s klíčem $k$, tak $T[h(k)]$ obsahuje ukazatel na $x$
  • rozdíl mezi přímou adresací a hašovací tabulkou je v určení na pozice kterou se uloží prvek $x$ s klíčem $k$: $\color{orange} T[k] vs T[h(k)]$
  • při hašování může být $\color{orange} |U| >> m$

Problémy k řešení

• řešení kolize
  • kolizí je situace, kdy prvky $x$ a $x’$ s klíči $k$ a $k’$ zahašujeme na stejnou pozici, tj. $h(k)==h(k’)$ (mají stejný otisk)
  • zřetězené hašování (chaining)
  • otevřená adresace (open adressing)
• výběr hašovací funkce
  • minimalizovat počet kolizí
  • efektivní výpočet funkce

Vlastnosti hašovacích funkcí

• problém
  • ani nejlepší haš. funkce negarantuje dobré chování v případě, že klíče jsou vybrány nejhorším možným způsobem (útočník pozná hašovací funkce a může dát takové klíče, že vznikne kolize)
• řešení
  • při každém použití hašovacího programu vybereme náhodně jinou hašovací funkci ze zvolené množiny hašovacích funkcí
• složitost
  • volba množiny hašovacích funkcí a způsob výběru hašovací funkce určují složitost (v nejhorším i očekávaném případě) jednotlivách operací

možina $\mathcal{H}$ hašovacích funkcí z $U$ do ${0,1,…,m-1}$ je

• uniformní když pro uniformně vybranou funkci z $\mathcal{H}$ a každý klíč $k \in U$ je pravděpodobnost zahašování klíče na každou z pozic tabulky stejná, $Pr_{h \in \mathcal{H}}[h(k)=i]=\frac{1}{m} \text{pro všechna} k \in U \text{a} i \in {0,1,…,m-1}$
• univerzální když pro každou dvojici klíčů je pravděp. kolize co nejmenjší …
• téměř univerzální …
• r-uniformní když pro každých $r$ vzájemně různých klíčů $k_1,…,k_r$ a pozic $i_1,…,i_r$ je pravděpodobnost kolize stejná …

Zřetězené hašování

• každá položka z tabulky obsahuje (ukazatel na) seznam prvků zahašovaných na stejnou pozici
• seznam je prázdný právě když žádný prvek nebyl zahašovaný na danou pozici
• vkládání prvku $x$ do hašovací tabulky $T$ se realizuje jako přidání prvku na začátek seznamu $T[h(x.key)]$
• prvek $x$ vyhledáme v seznamu $T[h(x.key)]$
• prvek $x$ odstraníme vymazáním ze seznamu $T[h(x.key)]$

Složitost

• složitost v nejhorším případě
  • Insert - konstantní (za předpokladu, že vkládaný prvek není v tabulce)
  • Search - $\mathcal{O}(s+|T[h(x)]|)$ (složitost výpočtu $h(x)$ plus složitost prohledání seznamu $T[h(x)]$)
  • Delete - asymptoticky stejná jako složitost Search (za předpokladu dvousměrného seznamu)
• složitost v očekávaném případě
  • záleží od výběru hašovací funkce
  • …

Příklady hašovacích funkcí

Metoda dělení

• předpoklad: klíčem je číslo
• $h(k) = k \mod m$
• výhody
  • rychlost
• nevýhody
  • závislost na volbě $m$
  • pro $m = 2^p$ je hodnota $h(k)$ vždy $p$ nejpravějších bitů z $k$
  • když $k$ je znakový řetězec interpretovaný při základě $2^p$, tak hodnota $m = 2^p - 1$ není vhodná, protože po permutaci řetězce se hodnota hašovací funkce nezmění
  • dobrou volbou pro $m$ je prvočíslo

Metoda binárního násobení

• předpoklady
  • reprezentujeme množinu binárních čísel délky $w$
  • velikost tabulky (univerza) je mocninou dvojky, $m = 2^p$
• cílem je zahašovat $w$-bitové čísla na $p$-botivé čísla
• pro zvolenou konstantu $A, 0 < A < 1, {\color{Red} h_A(k) = \lfloor m \cdot (k \cdot A \mod 1) \rfloor}$
• postup výpočtu
  • vynásob klíč $k$ konstantou $A$ a ze součiny vezmi desetinnou část
  • výsledek vynásob číslem $m$ a ze součinu celou část
• zvolíme $A$ ve tvaru $s/2^w$
  • vynásobíme čísla $k$ a $s$
  • výsledkem násobení je $2w$ bitové číslo, kde $r_1$ je celočíselná část součinu $kA$ a $r_0$ je desetinná část součinu
  • pro další výpočet potřebujeme pouze $r_0$
  • potřebujeme celou část součinu čísel $r_0$ a $m$
  • protože $m = 2^$, násobení znamená posun $p$ bitů doleva
  • ve skutečnosti nemusíme vůbec násobit a stačí vzít $p$ nejvýznamnějších bitů čísla $r_0$

Metoda násobení

• zvolíme prvočíslo $p$ takové, že žádný klíč není větší než $p$
• pro libovolná čísla $a \in {1,2,…,p-1}$ a $b \in {0,1,…,p-1}$ definujeme hašovací funkci přepisem $$\color{Red} h_{ab}(k) = ((ak + b) \mod p) \mod m)$$
• množina $\mathcal{H} = {h_{ab}: a\ in {1,2,…,p-1}, b \in {0,1,…,p-1}}$ je univerzální množinou hašovacích funkcí

Klíče jako přirozené čísla

• většina hašovacích funkcí je navržená pro univerzum - množinu přirozených čísel $\mathbb{N}$
• když klíče nejsou přirozená čísla, můžeme je interpretovat jako přirozená čísla použitím vhodného kódování

Otevřená adresace

• všechny klíče ukládáme přímo do tabulky (počet klíčů nemůže přesáhnout velikost tabulky)
• hašovací funkce je typu $h : S \times {0,1,…,m-1} \rightarrow {0,1,…,m-1}$, přičemž pořadujeme, aby pro každý klíč $k \in S$ sekvence sond $$\langle h(k,0), h(k,1), …, h(k,m-1) \rangle$$ byla permutací posloupnosti $\langle 0,1,…,m-1 \rangle$
• při vyhledávání se systematicky zkoumají (sondují) pozice tabulky, dokud není nalezen hledaný klíč nebo není jasné, že klíč v tabulce není
• “pro každý možný objekt mám uspořádanou posloupnost hašovacích funkcí”
• prvek nemá pouze jednu pozici, ale posloupnost pozicí na kterých může být

Vyhledávání

• zkouším postupně všechny pozice posloupnosti
• dokud buď nenajdu daný klíč
• nebo nenajdu prázdnou hodnotu tabulky (None) -> klíč není v tabulce

Vkládání

• analogicky jako při hledání najdeme volnou pozici v tabulce
• vkládání skončí úspěchem když je nalezena volná pozice, na kterou se klíč vloží
• když počet testů dosáhne $m$, tak vkládání skončí neúspěchem

Odstranění klíče k

• při ostranění by mohlo nastat, že uvolním buňky z tabulky pro posloupnost, které je před nějakou hodnotou v tabulce
• → Místo hodnoty None do pozice v tabulce dám hodnotu Deleted
  • Insert pozažuje Deleted z prázdnou hodnotu
  • Search považuje za plnou s jinou hodnotou

Sekvence sond

• lineární adresace (linear probing)
• kvadratická adresace (quadratic probing)
• dvojité hašování (double hashing)

Lineární

• využívá pomocnou funkci $h’ : U \rightarrow {0,1,…,m-1}$
• hašovací funkce $h$ je definována přepisem $$\color{Red} h(k,i) = (h’(k) + i) \mod m$$
• problémem je primární shlukování - může zvýšit složitost operací

Kvadratická

• pomocná $h’$ a konstanty $c_1$, $c_2$
• hašovací funkce $h$ je definována předpiesm $$\color{Red} h(k,i) = (h’(k) + c_1i + c_2i^2) \mod m$$

Dvojité hašování

• dvě pomocné funkce $h_1$,$h_2$
• hašovací funkce $h$ je definována předpisem $$\color{Red} h(k,i) = (h_1(k) + ih_2(k)) \mod m$$

Složitost

• při neúspěšném hledání nejvýše $\frac{1}{1 - \alpha}, \alpha = \frac{n}{m} < 1$
• při úspěšném hledání $

Kukaččí hašování (Cuckoo hashing)

• dvě tabulky velikosti $m$ a dvě hašovací funkce $h_1,h_2$
• každý klíč $k$ je zahašovaný buď na pozici $h_1(k)$ v první tabulce, anebo na pozici $h_2(k)$ v druhé tabulce
• Search je jednoduchá - kouknu na obě tabulky
• Delete je jednoduchý obdobně Search
• Insert je složitý
  • Musím prvek vložit aspoň od jedné tabulky, co když jsou obě místa obsazena?
  • vloží do první tabulku a prvek z toho místa vložíme do druhé
  • je-li obsazen opakujeme obdobně dokud nevložíme do prázdného místa

Perfektní hašování (perfect hashing)

• hašování, které má konstantní složitost i v nejhorším případě
• předpokladem je statická množina klíčů
• využívá dvě úrovně hašování
• první úroveň
  • zřetězené hašování
  • velikost tabulky je lineární vůči počtu klíčů
• druhá úroveň
  • místo seznamů použijeme sekundární hašovací tabulky $S_j$ s asociovanou hašovací funkcí $h_j$, přičemž vhodným výběrem můžeme zajistit, aby na druhé úrovni nebyly žádné kolize
  • velikost $m_j$ tabulky $S_j$ je kvadratická vůči počtu klíčů zahašovaných na pozici $j$