13-hash/13-hash.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{13}{Hashování}{(zapsal Martin Francù a Bohdan Maslowski)}
   4
   5
   6 \h{Tøídìní}
   7
   8 V kapitole 5 jsme si ukázali, ¾e tøídìní pomocí porovnávání se dá zvládnout nejlépe v èase $O(n)$. Víme-li v¹ak nìco o hodnotách, mù¾eme najít lep¹í tøídící algoritumus, který pracuje napø. v lineárním èase.
   9
  10 \>Na mno¾inì máme tyto operace:
  11
  12 \itemize\ibull
  13 \:Insert(x)
  14 \:Delete(x)
  15 \:Find(x)
  16 \endlist
  17
  18 \>Víme-li, ¾e je mno¾ina uspoøádaná, mù¾eme pou¾ít vyhledávací strom, tedy $\Theta(\log n)$ na operaci.
  19
  20 \medskip
  21
  22 \>Znaèíme
  23
  24 \itemize\ibull
  25 \:$n$ ... Poèet prvkù
  26 \:$U$ ... Velikost universa (mno¾ina ze které prvky vybíráme)
  27 \:$[U] = {0, 1, 2,\ldots,U-1}$
  28 \endlist
  29
  30
  31 \bigskip
  32
  33 \h{1. Pole indexované $0$ a¾ $U-1$}
  34
  35 Insert, Delete i Find pracují v èase $O(1)$, pamì»ová slo¾itost je $O(U)$.
  36
  37
  38 \h{2. Èíslicový strom (radix tree) }
  39
  40 Zvolíme základ soustavy $b$, prvky universa zapisujeme jako $k$-tice èíslic. Èili:
  41
  42 $$x\in U \mapsto [b]^{k}, k=[\log_b U]$$
  43
  44 Tedy vznikne strom (s hloubkou $k$), na $k$-té úrovni podle $k$-té èíslice
  45
  46 \medskip
  47
  48
  49 Find: $O(\log_b U)$
  50
  51 Insert, Delete: $O(b \log_b U)$
  52
  53 Pamì»ová nároènost: $O(nb\log_b U)$
  54
  55 \medskip
  56
  57 Èí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ù.
  58
  59 \bigskip
  60
  61 \h{3. Písmenkový strom }
  62
  63 Pou¾ívá se pro øezìzce, za základ soustavy $b$ zvolíme abecedu.
  64
  65 \medskip
  66
  67 $\vert x\vert $...délka øetìzce
  68
  69 Find, Insert, Delete: $O(\vert x\vert )$
  70
  71 Pamì»: $O(\sum_{i} \vert x\vert )$
  72
  73 \bigskip
  74
  75 \h{4. Hashování }
  76
  77
  78 $h$ ... hashovací funkce $[U] \rightarrow [m]$
  79
  80 $m$ ... poèet pøihrádek, v ka¾dé pøihrádce spojový seznam.
  81
  82 \medskip
  83
  84 Perfektní hashovací funkce pøiøadí do ka¾dé z $m$ pøihrádek jediný prvek z $[U]$.
  85
  86 \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$
  87
  88
  89
  90
  91 \h{Hashování se separovými øetezci}
  92
  93 \medskip
  94 Insert, Delete i Find pracují v èase $O(\vert x\vert )$, pamì»ová slo¾itost je $O(m+n)$
  95 \medskip
  96
  97 vlo¾ili jsme $x_1 \ldots x_n \in [U]$
  98
  99 nyní pracujeme s $x \in [U]$
 100
 101 pøedpokládejme, ¾e $h(x_i)$ a $h(x)$ jsou náhodné
 102
 103 $p:=h(x)$
 104
 105 $N_p:=\sharp$ : $h(x_1)=h(x)$
 106
 107 $N_{i,p} := 0$ pokud $h(x_i)\neq p$
 108
 109 $N_{i,p} := 1$ pokud $h(x_i)= p$
 110
 111 $N_p = \sum_{i=1}^n N_{i,p}$
 112
 113 $E N_{i,p} = Pr[h(x_i)=p] = {1 \over m} $
 114
 115 $E N_p = n {1\over m} = {n \over m} $
 116
 117 \medskip
 118
 119 Za pøedpokladu, ¾e hash pøidìluje náhodnou pøihrádku, je v ka¾dé pøihrádce ${n \over m}$ prvkù.
 120
 121 \bigskip
 122
 123
 124 \h{Druhá pùlka}
 125
 126
 127 \noindent {\sc Vìta:} {\it Pokud jsme do hashovací tabulky vlo¾ili
 128 hodnoty $x_1,\dots,x_m$ tak, ¾e $h_{x_i}$ jsou v¹echny stejnì
 129 pravdìpodobné, pak následující Insert, Delete, Find pracují v èase
 130 ${\cal O}\,({n \over m}+1)$. (Za pøedpokladu, ¾e výpoèet $h$ trvá
 131 ${\cal O}\,(1)$.)}
 132
 133 \medskip
 134
 135 {\it Insert}: Spoèítá si $h(x)$ a vlo¾í jej do spojového seznamu v patøièné pøihrádce.
 136
 137 {\it Delete}: Spoèítá si $h(x)$ a najde jej v spojovém seznamu v patøièné pøihrádce a
 138 odstraní jej.
 139
 140 {\it Find}: Spoèítá si $h(x)$ a najde jej v spojovém seznamu v patøièné pøihrádce.
 141
 142 \medskip
 143
 144 \noindent Tato metoda má dva háèky:
 145
 146 1. vysoká koliznost
 147
 148 2. musíme dopøedu vìdìt, kolik prvkù budeme vkládat
 149
 150 \bigskip
 151
 152 {\large \bf Nafukovací hashovací tabulka}
 153
 154 na poèátku: $n=0;m=4$
 155
 156 v ka¾dém okam¾iku budeme udr¾ovat pomìr ${n\over m}\in \langle
 157 {1\over 2},1)$
 158
 159 tedy: (pokud nastane)
 160 $$n=4 \Rightarrow m:=8 $$
 161 $$n=8 \Rightarrow m:=16$$
 162 Pøi ka¾dém zvìt¹ování tabulky musíme zvìt¹it obor hodnot hashovací funkce a v¹echny prvky ji¾
 163 v tabulce ulo¾ené znovu "zhashovat".
 164
 165 Nafukování trvá ${\cal O}\, (n)$, ale mezi dvìma nafouknutími je
 166 minimálnì $ {n\over 2} $ Insertù.
 167
 168 Pokud tedy ka¾dý Insert pøispìje konstantou, tak to máme zadarmo!
 169
 170 \bigskip
 171
 172 PROBLÉM: Jak udìlat funkci Delete? Jednoduché zmen¹ování tabulky pøi pomìru
 173 ${n\over m}={1\over 2}$ není dostaèující, nebo» by se mohlo stát, ¾e bychom nafukovali a
 174 zfukovali hned po sobì.
 175
 176 \bigskip
 177
 178 {\bf Verze s Insert a Delete}
 179
 180 Udr¾ujeme ${n\over m}\in \langle {1\over 4},1)$
 181
 182 pøi zfukování tabulku pùlíme, pøi nafukování zdvojnásobujeme
 183
 184 \medskip
 185
 186 Po pøehashování je pomìr ${n\over m}={1\over 2} \Rightarrow$mezi dvìma pøehashováními
 187 nastane minimálnì ${m\over 2}$ Insertù èi ${m\over 4}$ Deletù, tedy alespoò ${m\over 4}$
 188 operací.
 189
 190 Zároveò zabereme v¾dy lineárnì prostoru vzhledem k $n$.
 191
 192 \bigskip
 193
 194 \noindent {\sc Vìta:} {\it Nafukovací hashování (se separovanými øetìzci) za pøedpokladu
 195 rovnomìrné pravdìpodobnosti pracuje v prùmìrném èase ${\cal O}\,(1)$ na operaci a v prostoru
 196 ${\cal O}\,(n)$ (kde $n$ je poèet pøítomných prvkù).}
 197
 198 \medskip
 199
 200 Kde pøijít k rovnomìrné hashovací funkci?
 201
 202 \medskip
 203
 204 \noindent Dìdeèkovo vyprávìní:
 205
 206 a) $h(x)= x$ $mod (m)$ -rychlá, snadná kolize, sudé x v¾dy v sudých pøihrádkách. Na náhodných
 207 èíslech funguje v pohodì.
 208
 209 \bigskip
 210
 211 \noindent POZOROVÁNÍ: $\alpha \in(0,1)$ iracionální;
 212
 213 $x \in{\sc N}$ pak $\alpha x $ $ mod (1)$ se chová "náhodnì".
 214
 215 \medskip
 216
 217  b) $h(x)=\lfloor m(\alpha x $ $mod(1))\rfloor$
 218  $$ {A\over W} \sim \alpha \Rightarrow h(x)= \lfloor m(Ax \ mod(W)) \rfloor $$
 219
 220  \medskip
 221
 222  Jako velmi výhodné se jeví pou¾ívat $\alpha = {{\sqrt{5} -1}\over{2}} $ - pøevrácená hodnota zlatého øezu.
 223
 224 \medskip
 225
 226 c) funkce k hashování øetìzcù
 227 $$ h(\emptyset)=0 $$
 228 $$ h(x_1, \dots , x_n)=c(h(x_1, \dots ,x_{n-1})+x_n)$$
 229 $$ \Rightarrow h(x_1, \dots , x_n)=x_n + cx_{n-1} + c^2 x_{n-2} +
 230 \dots $$ (polynom)
 231
 232 \medskip
 233
 234 d)Pokud $x$ je $k$-tice (celých) èísel. Pak mù¾eme jako hashovací funkci pou¾ít skalární
 235 souèín s náhodnì vybraným prvkem z vektorového prostoru $Z_p^k$ (nad koneèným tìlesem):
 236 $$ h(x)= \overrightarrow{a} * \overrightarrow{x}   mod (p) $$
 237
 238 \medskip
 239
 240 Pravdìpodobnost pøes v¹echny volby $\overrightarrow{a}$, ¾e  $x,y$ se zahashují stejnì je
 241 pak:
 242 $$ p[h(x)=h(y)] = p[\overrightarrow{a}*\overrightarrow{x} =
 243 \overrightarrow{a}*\overrightarrow{y}]= p[\overrightarrow{a}*
 244 (\overrightarrow{x}-\overrightarrow{y})=0)] $$
 245
 246 Pokud platí $p[\overrightarrow{a}* (\overrightarrow{x}-\overrightarrow{y}=0)]$, pak
 247 $\overrightarrow{a}$ je prvkem ortogonálního doplòku k $(x-y)$, ten má $ dim (W^\bot) =
 248 (k-1)$
 249
 250 $$ p= {{W^\bot}\over{Z_p^k}}= {{p^{k-1}}\over{p^k}} = {1\over p}={1\over m}$$
 251
 252 kde $m$ je poèet pøihrádek. Co¾ je dostaèující.
 253
 254 \bye
 255