\input ../lecnotes.tex

\prednaska{11}{Vyhledávací stromy a hashování}{zapsal P. Taufer}

{\bf FIXME: Zatím chybí èerveno-èerné stromy a trie.}

\h{Hashovaní}

Mìjme universum~$U$ (jeho velikost oznaèíme~$u$), mno¾inu~$P$ pøihrádek ($p=\vert P\vert$)
a nìjakou funkci $h: U\rightarrow P$, které budeme øíkat {\I hashovací funkce.}

Datová struktura bude fungovat takto: kdy¾ prvek vkládáme, spoèteme hashovací funkci a vlo¾íme
prvek do~pøíslu¹né pøihrádky (pøihrádky budeme reprezentovat jako pole seznamù). Pokud chceme
prvek vyhledat nebo smazat, opìt vyhodnotíme hashovací funkci a dozvíme se, ve~které jediné
pøihrádce ho dává smysl hledat.

Budeme-li pøedpokládat, ¾e výpoèet funkce~$h$ trvá $\O(1)$, bude vkládání pracovat v~konstantním
èase a ostatní operace v~èase lineárním s~poètem prvkù v~dané pøihrádce. Pokud
se hashovací funkce bude chovat \uv{rozumnì náhodnì}, mù¾eme oèekávat, ¾e
po~vlo¾ení $n$~prvkù jich bude v~ka¾dé pøihrádce pøibli¾nì $n/p$, tak¾e pøi volbì $p\approx n$
mù¾eme získat konstantní èasovou slo¾itost operací. (Volit $p \gg n$ nemá smysl, proto¾e pak
bychom inicializací pole trávili pøíli¹ mnoho èasu.)

Tento pøístup má ale samozøejmì své zádrhele: potøebujeme s~prvky universa umìt poèítat
(u¾ si nevystaèíme s~porovnáváním), ale hlavnì potøebujeme sehnat hashovací funkci, která
se chová dostateènì rovnomìrnì. Èasto se pou¾ívají funkce, které se pro obvyklé vstupy
chovají \uv{pseudonáhodnì}, tøeba:

\itemize\ibull
\:$x \mapsto ax \bmod p$, pokud je universum èíselné (pro nìjakou konstantu~$a$; nejlep¹í
  je, kdy¾ $a$ i~$p$ jsou prvoèísla);
\:$x_1,\ldots,x_n \mapsto \left(\sum_i C^ix_i\right) \bmod p$, pokud hashujeme øetìzce ($C$ a~$p$
  opìt nejlépe prvoèíselná, navíc je-li $\ell$ obvyklá délka øetìzce, mìlo by být $C^\ell \gg p$).
\endlist

Nicménì, a» u¾ zvolíme jakoukoliv deterministickou funkci, v¾dy budou existovat nepøíjemné
vstupy, pro které skonèí v¹echny prvky v~té¾e pøihrádce a operace budou mít lineární slo¾itost
namísto konstantní. Pomù¾eme si snadno: vybereme hashovací funkci náhodnì. Ne ze v¹ech funkcí
(ty bychom neumìli reprezentovat), nýbr¾ z~vhodnì zvolené tøídy funkcí, které umíme snadno
popisovat pomocí parametrù.

\s{Definice:} Systém funkcí~$S$ z~$U$ do~$P$ nazveme $c$-universální (pro nìjaké $c\ge 1$),
pokud pro v¹echny dvojice $x,y$ navzájem rùzných prvkù z~$U$ platí
$$
{\rm Pr}_{h\in S}[h(x) = h(y)] \le c/p.
$$
\>(Kdybychom volili náhodnì z~úplnì v¹ech funkcí, vy¹la by tato pravdìpodobnost právì $1/p$
-- $c$-universální systém je tedy nejvý¹e $c$-krát hor¹í.)

\s{Lemma:} Buï $h$ funkce náhodnì vybraná z~nìjakého $c$-universálního systému. Nech» $x_1,\ldots,x_n$
jsou navzájem rùzné prvky universa vlo¾ené do struktury a $x$~je nìjaký prvek universa. Potom pro
oèekavaný poèet prvkù v~té¾e pøihrádce jako~$x$ platí:
$$
{\bb E}[ \#x: h(x) = h(x_i) ] \le cn/p.
$$

\proof
Pro dané $x$ definujeme indikátorové náhodné promìnné:
$$
Z_i = \cases{
1 & \hbox{kdy¾ $h(x)=h(x_i)$} \cr
0 & \hbox{jinak} \cr
}
$$
Jinými slovy, $Z_i$ øíká, kolikrát padl prvek~$x_i$ do pøihrádky $h(x)$, co¾ je buï
0 nebo~1. Proto $Z = \sum_i Z_i$ a díky linearitì støední hodnoty je hledaná hodnota ${\bb E}[Z]$
rovna $\sum_i {\bb E}[Z_i]$. Pøitom ${\bb E}[Z_i] = {\rm Pr}[Z_i=1] \le c/p$ podle definice
$c$-universálního systému. Tak¾e ${\bb E}[Z] \le cn/p$.
\qed

{\bf FIXME: Doplnit pøehashovávání.}

Zbývá doøe¹it, kde nìjaký $c$-universální systém sehnat. Známých konstrukcí je vícero,
zde si pøedvedeme jednu lineárnì algebraickou.

\def\Zp{{\bb Z}_p}
\def\Zpd{\Zp^d}

\s{Lemma:} Pøedpokládejme, ¾e $p$ je prvoèíslo, pøihrádky jsou identifikované
prvky koneèného tìlesa $\Zp$ a universum~$U$ je vektorový prostor dimense~$d$
nad tìlesem~$\Zp$, tedy $Zpd$. Uva¾ujme systém funkcí $S = \{ h_t \mid t \in \Zpd \}$,
kde $h_t(x) := t\cdot x$ (skalární souèin s~vektorem~$s$). Pak tento systém je
1-universální.

\proof
Nech» $x,y \in \Zpd$, $x\ne y$. Potom jistì existuje~$i$, pro nìj¾ $x_i\ne y_i$;
bez újmy na obecnosti pøedpokládajme, ¾e $i=d$. Nyní volíme~$t$ náhodnì po slo¾kách
a poèítáme pravdìpodobnost kolize (rovnost modulo~$p$ znaèíme~$\equiv$):
$$\eqalign{
&{\rm Pr}_{t\in\Zpd} [ h_t(x) \equiv h_t(y) ] =
{\rm Pr} [ x\cdot t \equiv y\cdot t ] =
{\rm Pr} [ (x-y)t \equiv 0 ] = \cr
&= {\rm Pr} \left[ \sum_{i=1}^d (x_i-y_i)t_i \equiv 0 \right] =
{\rm Pr} \left[ (x_d-y_d)t_d \equiv -\sum_{i=1}^{d-1} (x_i-y_i)t_i \right]. \cr
}
$$
Pokud u¾ jsme $t_1,\ldots,t_{d-1}$ zvolili a nyní náhodnì volíme~$t_d$, nastane
kolize pro právì jednu volbu (poslední výraz je linearní rovnice tvaru $ax=b$
pro nenulové~$a$ a ta má v~libovolném tìlese právì jedno øe¹ení). Pravdìpodobnost
kolize je tedy nejvý¹e $1/p$, jak po¾aduje 1-universalita.
\qed


\s{Vìta (Bertandùv postulát):}
Pro libovolné $n\ge 1$ existuje prvoèíslo $p$, které splòuje nerovnost $n< p\le 2n$.

\bye
