10-hash/10-hash.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{11}{Vyhledávací stromy a hashování}{zapsal P. Taufer}
   4
   5 {\bf FIXME: Zatím chybí èerveno-èerné stromy a trie.}
   6
   7 \h{Hashovaní}
   8
   9 Mìjme universum~$U$ (jeho velikost oznaèíme~$u$), mno¾inu~$P$ pøihrádek ($p=\vert P\vert$)
  10 a nìjakou funkci $h: U\rightarrow P$, které budeme øíkat {\I hashovací funkce.}
  11
  12 Datová struktura bude fungovat takto: kdy¾ prvek vkládáme, spoèteme hashovací funkci a vlo¾íme
  13 prvek do~pøíslu¹né pøihrádky (pøihrádky budeme reprezentovat jako pole seznamù). Pokud chceme
  14 prvek vyhledat nebo smazat, opìt vyhodnotíme hashovací funkci a dozvíme se, ve~které jediné
  15 pøihrádce ho dává smysl hledat.
  16
  17 Budeme-li pøedpokládat, ¾e výpoèet funkce~$h$ trvá $\O(1)$, bude vkládání pracovat v~konstantním
  18 èase a ostatní operace v~èase lineárním s~poètem prvkù v~dané pøihrádce. Pokud
  19 se hashovací funkce bude chovat \uv{rozumnì náhodnì}, mù¾eme oèekávat, ¾e
  20 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$
  21 mù¾eme získat konstantní èasovou slo¾itost operací. (Volit $p \gg n$ nemá smysl, proto¾e pak
  22 bychom inicializací pole trávili pøíli¹ mnoho èasu.)
  23
  24 Tento pøístup má ale samozøejmì své zádrhele: potøebujeme s~prvky universa umìt poèítat
  25 (u¾ si nevystaèíme s~porovnáváním), ale hlavnì potøebujeme sehnat hashovací funkci, která
  26 se chová dostateènì rovnomìrnì. Èasto se pou¾ívají funkce, které se pro obvyklé vstupy
  27 chovají \uv{pseudonáhodnì}, tøeba:
  28
  29 \itemize\ibull
  30 \:$x \mapsto ax \bmod p$, pokud je universum èíselné (pro nìjakou konstantu~$a$; nejlep¹í
  31   je, kdy¾ $a$ i~$p$ jsou prvoèísla);
  32 \:$x_1,\ldots,x_n \mapsto \left(\sum_i C^ix_i\right) \bmod p$, pokud hashujeme øetìzce ($C$ a~$p$
  33   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$).
  34 \endlist
  35
  36 Nicménì, a» u¾ zvolíme jakoukoliv deterministickou funkci, v¾dy budou existovat nepøíjemné
  37 vstupy, pro které skonèí v¹echny prvky v~té¾e pøihrádce a operace budou mít lineární slo¾itost
  38 namísto konstantní. Pomù¾eme si snadno: vybereme hashovací funkci náhodnì. Ne ze v¹ech funkcí
  39 (ty bychom neumìli reprezentovat), nýbr¾ z~vhodnì zvolené tøídy funkcí, které umíme snadno
  40 popisovat pomocí parametrù.
  41
  42 \s{Definice:} Systém funkcí~$S$ z~$U$ do~$P$ nazveme $c$-universální (pro nìjaké $c\ge 1$),
  43 pokud pro v¹echny dvojice $x,y$ navzájem rùzných prvkù z~$U$ platí
  44 $$
  45 {\rm Pr}_{h\in S}[h(x) = h(y)] \le c/p.
  46 $$
  47 \>(Kdybychom volili náhodnì z~úplnì v¹ech funkcí, vy¹la by tato pravdìpodobnost právì $1/p$
  48 -- $c$-universální systém je tedy nejvý¹e $c$-krát hor¹í.)
  49
  50 \s{Lemma:} Buï $h$ funkce náhodnì vybraná z~nìjakého $c$-universálního systému. Nech» $x_1,\ldots,x_n$
  51 jsou navzájem rùzné prvky universa vlo¾ené do struktury a $x$~je nìjaký prvek universa. Potom pro
  52 oèekavaný poèet prvkù v~té¾e pøihrádce jako~$x$ platí:
  53 $$
  54 {\bb E}[ \#x: h(x) = h(x_i) ] \le cn/p.
  55 $$
  56
  57 \proof
  58 Pro dané $x$ definujeme indikátorové náhodné promìnné:
  59 $$
  60 Z_i = \cases{
  61 1 & \hbox{kdy¾ $h(x)=h(x_i)$} \cr
  62 0 & \hbox{jinak} \cr
  63 }
  64 $$
  65 Jinými slovy, $Z_i$ øíká, kolikrát padl prvek~$x_i$ do pøihrádky $h(x)$, co¾ je buï
  66 0 nebo~1. Proto $Z = \sum_i Z_i$ a díky linearitì støední hodnoty je hledaná hodnota ${\bb E}[Z]$
  67 rovna $\sum_i {\bb E}[Z_i]$. Pøitom ${\bb E}[Z_i] = {\rm Pr}[Z_i=1] \le c/p$ podle definice
  68 $c$-universálního systému. Tak¾e ${\bb E}[Z] \le cn/p$.
  69 \qed
  70
  71 {\bf FIXME: Doplnit pøehashovávání.}
  72
  73 Zbývá doøe¹it, kde nìjaký $c$-universální systém sehnat. Známých konstrukcí je vícero,
  74 zde si pøedvedeme jednu lineárnì algebraickou.
  75
  76 \def\Zp{{\bb Z}_p}
  77 \def\Zpd{\Zp^d}
  78
  79 \s{Lemma:} Pøedpokládejme, ¾e $p$ je prvoèíslo, pøihrádky jsou identifikované
  80 prvky koneèného tìlesa $\Zp$ a universum~$U$ je vektorový prostor dimense~$d$
  81 nad tìlesem~$\Zp$, tedy $Zpd$. Uva¾ujme systém funkcí $S = \{ h_t \mid t \in \Zpd \}$,
  82 kde $h_t(x) := t\cdot x$ (skalární souèin s~vektorem~$s$). Pak tento systém je
  83 1-universální.
  84
  85 \proof
  86 Nech» $x,y \in \Zpd$, $x\ne y$. Potom jistì existuje~$i$, pro nìj¾ $x_i\ne y_i$;
  87 bez újmy na obecnosti pøedpokládajme, ¾e $i=d$. Nyní volíme~$t$ náhodnì po slo¾kách
  88 a poèítáme pravdìpodobnost kolize (rovnost modulo~$p$ znaèíme~$\equiv$):
  89 $$\eqalign{
  90 &{\rm Pr}_{t\in\Zpd} [ h_t(x) \equiv h_t(y) ] =
  91 {\rm Pr} [ x\cdot t \equiv y\cdot t ] =
  92 {\rm Pr} [ (x-y)t \equiv 0 ] = \cr
  93 &= {\rm Pr} \left[ \sum_{i=1}^d (x_i-y_i)t_i \equiv 0 \right] =
  94 {\rm Pr} \left[ (x_d-y_d)t_d \equiv -\sum_{i=1}^{d-1} (x_i-y_i)t_i \right]. \cr
  95 }
  96 $$
  97 Pokud u¾ jsme $t_1,\ldots,t_{d-1}$ zvolili a nyní náhodnì volíme~$t_d$, nastane
  98 kolize pro právì jednu volbu (poslední výraz je linearní rovnice tvaru $ax=b$
  99 pro nenulové~$a$ a ta má v~libovolném tìlese právì jedno øe¹ení). Pravdìpodobnost
 100 kolize je tedy nejvý¹e $1/p$, jak po¾aduje 1-universalita.
 101 \qed
 102
 103
 104 \s{Vìta (Bertandùv postulát):}
 105 Pro libovolné $n\ge 1$ existuje prvoèíslo $p$, které splòuje nerovnost $n< p\le 2n$.
 106
 107 \bye