\input lecnotes.tex

\prednaska{13}{Hashování}{(zapsali Martin Francù a Bohdan Maslowski)}

V~pøedchozích kapitolách jsme ukázali, ¾e aèkoliv v~obecném pøípadì
nelze tøídit rychleji ne¾ v~èase $\Theta(n\log n)$, pro nìkteré speciální
druhy hodnot (malá celá èísla, øetìzce apod.) existuje efektivnìj¹í lineární
algoritmus. Nyní si podobným zpùsobem posvítíme na~reprezentaci mno¾in --
navrhneme datovou strukturu, která bude umìt s~vhodnými typy prvkù provádìt
základní mno¾inové operace (\<Insert>, \<Delete>, \<Find>) v~{\I prùmìrnì}
konstantním èase (pomocí vyhledávacích stromù jsme to zatím umìli v~èase $\O(\log n)$
na operaci).

Jaké máme mo¾nosti? Zaènìme od~tìch nejjednodu¹¹ích a oznaème si~$n$ velikost
mno¾iny a $U$ velikost univerza, z~nìj¾ prvky mno¾iny vybíráme.

\s{1. Pole indexované od $0$ do $U-1$}

\indent \<Insert>, \<Delete> i \<Find> pracují v~èase $\O(1)$, ale platíme za~to
pamì»ovou slo¾itostí $\Theta(U)$.

\s{2. Èíslicový strom (radix tree)}

Zvolíme základ soustavy $b$, prvky universa zapisujeme jako $k$-tice èíslic. Èili:
$$x\in U \mapsto [b]^{k}, k=\lceil\log_b U\rceil.$$
Tím nám vznikne strom s~hloubkou $k$, na $k$-té úrovni se rozhodujeme podle $k$-té èíslice.

Operace \<Find> bude trvat $O(\log_b U)$, operace \<Insert> a \<Delete> pak
$O(b \log_b U)$. Strom zabere prostor velikosti $O(nb\log_b U)$.

Èím bude základ $b$ men¹í, tím lep¹í pamì»ová a hor¹í èasová slo¾itost,
a obrácenì. Èíslicový strom tedy vy¾aduje peèlivé nastavení parametrù.

\h{3. Písmenkový strom }

Pou¾ívá se pro øezìzce, za základ soustavy $b$ zvolíme abecedu.

\medskip

$\vert x\vert $...délka øetìzce

Find, Insert, Delete: $O(\vert x\vert )$

Pamì»: $O(\sum_{i} \vert x\vert )$

\bigskip

\h{4. Hashování }


$h$ ... hashovací funkce $[U] \rightarrow [m]$ 

$m$ ... poèet pøihrádek, v ka¾dé pøihrádce spojový seznam.

\medskip

Perfektní hashovací funkce pøiøadí do ka¾dé z $m$ pøihrádek jediný prvek z $[U]$.

\s{Pøíklad:} Jaká je pravdìpodobnost, ¾e 2 z k lidí mají narozeniny ve stejný den? Staèí 23 lidí, aby nastala kolize s pravdìpodobností vìt¹í ne¾ jedna polovina. Aby nenastala, potøebovali bychom vìt¹í poèet pøihrádek: $p = cm^2$




\h{Hashování se separovými øetezci}

\medskip
Insert, Delete i Find pracují v èase $O(\vert x\vert )$, pamì»ová slo¾itost je $O(m+n)$
\medskip

vlo¾ili jsme $x_1 \ldots x_n \in [U]$

nyní pracujeme s $x \in [U]$

pøedpokládejme, ¾e $h(x_i)$ a $h(x)$ jsou náhodné

$p:=h(x)$

$N_p:=\sharp$ : $h(x_1)=h(x)$

$N_{i,p} := 0$ pokud $h(x_i)\neq p$

$N_{i,p} := 1$ pokud $h(x_i)= p$

$N_p = \sum_{i=1}^n N_{i,p}$

$E N_{i,p} = Pr[h(x_i)=p] = {1 \over m} $

$E N_p = n {1\over m} = {n \over m} $

\medskip

Za pøedpokladu, ¾e hash pøidìluje náhodnou pøihrádku, je v ka¾dé pøihrádce ${n \over m}$ prvkù.

\bigskip


\h{Druhá pùlka}


\noindent {\sc Vìta:} {\it Pokud jsme do hashovací tabulky vlo¾ili
hodnoty $x_1,\dots,x_m$ tak, ¾e $h_{x_i}$ jsou v¹echny stejnì
pravdìpodobné, pak následující Insert, Delete, Find pracují v èase
${\cal O}\,({n \over m}+1)$. (Za pøedpokladu, ¾e výpoèet $h$ trvá
${\cal O}\,(1)$.)}

\medskip

{\it Insert}: Spoèítá si $h(x)$ a vlo¾í jej do spojového seznamu v patøièné pøihrádce.

{\it Delete}: Spoèítá si $h(x)$ a najde jej v spojovém seznamu v patøièné pøihrádce a
odstraní jej.

{\it Find}: Spoèítá si $h(x)$ a najde jej v spojovém seznamu v patøièné pøihrádce.

\medskip

\noindent Tato metoda má dva háèky:

1. vysoká koliznost

2. musíme dopøedu vìdìt, kolik prvkù budeme vkládat

\bigskip

{\large \bf Nafukovací hashovací tabulka}

na poèátku: $n=0;m=4$

v ka¾dém okam¾iku budeme udr¾ovat pomìr ${n\over m}\in \langle
{1\over 2},1)$

tedy: (pokud nastane)
$$n=4 \Rightarrow m:=8 $$
$$n=8 \Rightarrow m:=16$$
Pøi ka¾dém zvìt¹ování tabulky musíme zvìt¹it obor hodnot hashovací funkce a v¹echny prvky ji¾
v tabulce ulo¾ené znovu "zhashovat".

Nafukování trvá ${\cal O}\, (n)$, ale mezi dvìma nafouknutími je
minimálnì $ {n\over 2} $ Insertù.

Pokud tedy ka¾dý Insert pøispìje konstantou, tak to máme zadarmo!

\bigskip

PROBLÉM: Jak udìlat funkci Delete? Jednoduché zmen¹ování tabulky pøi pomìru
${n\over m}={1\over 2}$ není dostaèující, nebo» by se mohlo stát, ¾e bychom nafukovali a
zfukovali hned po sobì.

\bigskip

{\bf Verze s Insert a Delete}

Udr¾ujeme ${n\over m}\in \langle {1\over 4},1)$

pøi zfukování tabulku pùlíme, pøi nafukování zdvojnásobujeme

\medskip

Po pøehashování je pomìr ${n\over m}={1\over 2} \Rightarrow$mezi dvìma pøehashováními
nastane minimálnì ${m\over 2}$ Insertù èi ${m\over 4}$ Deletù, tedy alespoò ${m\over 4}$
operací.

Zároveò zabereme v¾dy lineárnì prostoru vzhledem k $n$.

\bigskip

\noindent {\sc Vìta:} {\it Nafukovací hashování (se separovanými øetìzci) za pøedpokladu
rovnomìrné pravdìpodobnosti pracuje v prùmìrném èase ${\cal O}\,(1)$ na operaci a v prostoru
${\cal O}\,(n)$ (kde $n$ je poèet pøítomných prvkù).}

\medskip

Kde pøijít k rovnomìrné hashovací funkci?

\medskip

\noindent Dìdeèkovo vyprávìní:

a) $h(x)= x$ $mod (m)$ -rychlá, snadná kolize, sudé x v¾dy v sudých pøihrádkách. Na náhodných
èíslech funguje v pohodì.

\bigskip

\noindent POZOROVÁNÍ: $\alpha \in(0,1)$ iracionální;

$x \in{\sc N}$ pak $\alpha x $ $ mod (1)$ se chová "náhodnì".

\medskip

 b) $h(x)=\lfloor m(\alpha x $ $mod(1))\rfloor$
 $$ {A\over W} \sim \alpha \Rightarrow h(x)= \lfloor m(Ax \ mod(W)) \rfloor $$

 \medskip

 Jako velmi výhodné se jeví pou¾ívat $\alpha = {{\sqrt{5} -1}\over{2}} $ - pøevrácená hodnota zlatého øezu.

\medskip

c) funkce k hashování øetìzcù
$$ h(\emptyset)=0 $$
$$ h(x_1, \dots , x_n)=c(h(x_1, \dots ,x_{n-1})+x_n)$$
$$ \Rightarrow h(x_1, \dots , x_n)=x_n + cx_{n-1} + c^2 x_{n-2} +
\dots $$ (polynom)

\medskip

d)Pokud $x$ je $k$-tice (celých) èísel. Pak mù¾eme jako hashovací funkci pou¾ít skalární
souèín s náhodnì vybraným prvkem z vektorového prostoru $Z_p^k$ (nad koneèným tìlesem):
$$ h(x)= \overrightarrow{a} * \overrightarrow{x}   mod (p) $$

\medskip

Pravdìpodobnost pøes v¹echny volby $\overrightarrow{a}$, ¾e  $x,y$ se zahashují stejnì je
pak:
$$ p[h(x)=h(y)] = p[\overrightarrow{a}*\overrightarrow{x} =
\overrightarrow{a}*\overrightarrow{y}]= p[\overrightarrow{a}*
(\overrightarrow{x}-\overrightarrow{y})=0)] $$

Pokud platí $p[\overrightarrow{a}* (\overrightarrow{x}-\overrightarrow{y}=0)]$, pak
$\overrightarrow{a}$ je prvkem ortogonálního doplòku k $(x-y)$, ten má $ dim (W^\bot) =
(k-1)$

$$ p= {{W^\bot}\over{Z_p^k}}= {{p^{k-1}}\over{p^k}} = {1\over p}={1\over m}$$

kde $m$ je poèet pøihrádek. Co¾ je dostaèující.

\bye

