13-hash/13-hash.latex

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