12-hash/12-hash.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{10}{Hashování}{}
   4
   5 V pøedchozích kapitolách jsme se zabývali tøídìním prvkù a zjistili jsme, ¾e v obecném pøípadì (kdy¾ smíme prvky pouze porovnávat a prohazovat) nelze tøídit rychleji ne¾ v èase $\Theta(n\log n)$. Zároveò jsme do¹li k tomu, ¾e pokud víme o prvcích nìco více (napø. jejich rozsah), tak jsme v nìkterých pøípadech schopni tøídit i s lineární èasovou slo¾itostí.
   6
   7 V praxi nicménì vìt¹inou netøídíme samotná èísla, ale spí¹e nìjaké polo¾ky, napø. urèené uspoøádanou dvojicí (klíè, hodnota), kde klíèe jsou unikátní a existuje na nich lineární uspoøádání. Ukázali jsme si, jak takovouto mno¾inu udr¾ovat (aby se v ní dalo rychle vyhledávat, zaøazovat i mazat) ve vyhledávacích stromech. Dokázali jsme si, ¾e pokud budeme udr¾ovat strom dostateènì vyvá¾ený, tak budou jednotlivé operace (\<Find>, \<Insert> a \<Delete>) trvat $\Theta(\log n)$.
   8
   9 Ne¹lo by to ale rychleji? Odpovìï je jak kdy. Podívejme se na dal¹í mo¾nosti. Nejdøíve si ale pøipomeòme základní pojmy, které budeme pou¾ívat.
  10
  11 Klíèe budou prvky universa, co¾ je mno¾ina $\{ 0, \dots, U-1 \}$, kterou budeme oznaèovat $[U]$. Tuto mno¾inu budeme chtít udr¾ovat v nìjaké ¹ikovné datové struktuøe, abychom v ní mohli rychle vyhladávat, zaøazovat i mazat. Dále $n$ bude znaèit (maximální) poèet prvkù, které si budeme v jednu chvíli pamatovat.
  12
  13
  14 \h{1. Pole {\it indexované od $0$ do $U-1$}}
  15
  16 Pokud bude velikost universa dostateènì malá, tak si mù¾eme polo¾ky pamatovat v poli o velikosti universa. Operace \<Find>, \<Insert> i \<Delete> pracují v~èase $\O(1)$, ale platíme za~to pamì»ovou slo¾itostí $\O(U)$. Kdy¾ uvá¾íme, ¾e si budeme pamatovat mnohem ménì prvkù, ne¾ je velikost universa, tak je to velké plýtvání.
  17
  18 \h{2. Èíslicový strom}
  19
  20 Zvolíme vhodný základ soustavy $b$, klíè zapí¹eme v soustavì o základu $b$ a zápis ulo¾íme do stromu. Tímto nám vznikne \uv{$b$-ární strom}, tedy strom, jeho¾ ka¾dý vrchol má a¾ $b$ synù.
  21
  22 Vrcholy na první hladinì pak znaèí první èíslici, na druhé druhou, atd. Na poslední hladinì bude tedy $n$ listù. Hloubka tohoto stromu je $\lceil\log_b U\rceil$.
  23
  24 Operace \<Find> bude trvat $O(\log_b U)$ (najití jednoho klíèe odpovídá projití jedné cesty ve stromì od koøene do listu). Stejný èas budou trvat i operace \<Insert> a \<Delete>. (Pøi vkládání zakládáme vrcholy, které odpovídají na¹emu klíèi a které je¹tì nejsou zalo¾ené. Pøi mazání sma¾eme list a následnì vrcholy, ze kterých nic nevede. Pro tuto operaci je výhodné si ve vrcholech udr¾ovat jejich stupnì.) Strom zabere prostor velikosti $O(nb\log_b U)$.
  25
  26
  27 Èím bude základ $b$ men¹í, tím bude lep¹í pamì»ová a hor¹í èasová slo¾itost
  28 a obrácenì. Èíslicový strom tedy vy¾aduje peèlivé nastavení parametrù.
  29
  30 \s{Pøíklad:} Pøedstavme si, ¾e klíèe budou IP-adresy, tedy 32-bitová èísla. Jak zvolit $b$, aby byla èasová i pamì»ová slo¾itost pøijatelná? Zkusme rozdìlit IP-adresu na 4 kusy, $b$ bude tedy 256. Strom bude mít hloubku 4. Èas bude v poødáku, ale po¾adavky na prostor jsou dost vysoké. Výhodnìj¹í bude rozdìlit IP-adresu na 8 èástí, $b$ bude tedy 16, hloubka stromu 8 a nároky na èas i pamì» jsou pøijatelné.
  31
  32
  33 \h{4. Hashování }
  34
  35 Mìjme $m$ pøihrádek a v ka¾dé z nich spojový seznam. Dále $h$ bude hashovací funkce, která libovolnému prvku z universa pøiøadí právì jednu pøihrádku.
  36
  37 Kdyby $h$ fungovala \uv{rovnomìrnì } (ka¾dému prvku by pøiøadila jinou pøihrádku, tedy ka¾dý spojový seznam by mìl jen jeden prvek), tak bychom umìli vyhledávat, pøidávat i mazat prvky v konstantním èase. To je ov¹em samozøejmì pøíli¹ krásné na to, aby to byla pravda.
  38
  39 Problém je, ¾e pokud bude $m$ výraznì men¹í ne¾ $U$ (co¾ chceme, jinak se jedná o normální (obrovské)  pole a funkce je identita -- tento pøípad jsme ji¾ vyøe¹ili), tak urèitì budou existovat prvky, kterým funkce pøiøadí stejnou hodnotu. Takovému pøípadu se øíká {\it kolize}. Prvky se pak zaøadí do spojového seznamu. Kdyby byla naopak funkce hodnì ne¹ikovná a namapovala by nám v¹echny prvky do jedné pøihrádky, tak budeme v¾dy muset projít (v nejhor¹ím pøípadì celý) dlouhý spojový seznam.
  40
  41 Jak se dá tedy kolizím bránit? Nejvýhodnìj¹í by bylo mít dobrou hashovací funkci, která by mapovala prvky pokud mo¾no rovnomìrnì. Ale nìkdy staèí i prùmìrnì dobrá funkce a dostateènì náhodné klíèe.
  42
  43
  44 \s{Vsuvka:} 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$.
  45
  46 \h{Praktické hashovací funkce}
  47
  48 \s{První pøíklad}
  49
  50 Tato hashovací funkce $h: [U] \rightarrow [m]$ je definovaná pøedpisem: $h(x) = x \mod m$. Pro dostateènì náhodné hodnoty bude fungovat, ale v mnoha pøípadech mù¾e být nevhodná. Napøíklad je zøejmé, ¾e pro sudé $m$ zachovává paritu. V pøípadì, ¾e sudých, resp. lichých klíèù bude mnohem více, vznikne mnoho zbyteèných kolizí. Pro takovouto hashovací funkci je nejlep¹í zvolit za $m$ nìjaké prvoèíslo.
  51
  52 \s{Druhý pøíklad}
  53
  54 Zvolme si iracionální $\alpha$ z intervalu $(0,1)$. Funkce bude definovaná následovnì: $$h(x) = \lfloor m (x \cdot \alpha \mod 1) \rfloor.$$ Tato funkce by mìla na $x$ záviset velmi málo, ale nebudeme si to dokazovat.
  55
  56 \s{Implementace} Reálná èísla se samozøejmì implementují dosti nároènì (resp. to vùbec nejde), tak¾e v praxi se tento postup aproximuje celoèíselnì. Místo reálné $\alpha$ si zvolme $A = \lfloor \alpha \cdot 2^w \rfloor$, kde $2^w$ je ¹íøka slova ($w$ je napø. poèet bitù integeru). Potom místo výrazu $(x \cdot \alpha \mod 1)$, který je z intervalu $(0,1)$, budeme poèítat s výrazem $(x \cdot A \mod 2^w)$. Potom na¹e funkce vyjde následovnì:
  57
  58 $$h(x) = \lfloor { m(x \cdot A \mod 2^w) \over 2^w } \rfloor$$
  59
  60
  61 Zbývá jen otázka, jak volit $\alpha$? Osvìèená hodnota je ${1 \over \tau }$, co¾ je pøibli¾nì 0,618. ($\tau$ je hodnota zlatého øezu.) Takto zvolené $\alpha$ dobøe rozbíjí aritmetické posloupnosti, ale i toto je pouze pøedstava a nebudeme si to dokazovat.
  62
  63 \h{Hashování øetìzcù}
  64
  65 Vzhledem k tomu, ¾e hashování nijak speciálnì nepotøebuje, aby byly prvky èísla, tak se mohou hashovat i øetìzce. Uka¾me si jeden pøíklad funkce pro hashování øetìzcù.
  66 Prázdnému øetìzci pøiøaïme nulu: $h(\epsilon) = 0$. Øetìzci znakù $x_1, \dots, x_n$ pøiøaïme hodnotu:
  67 $$h(x_1, \dots, x_n) = (h(x_1, \dots, x_{n-1}) \cdot + x_n) \mod m.$$
  68 $A$ je zde nìjaká konstanta. Aby se vyu¾ily v¹echny pøihrádky, tak je vhodné zvlit $A$ tak, aby $A^{{\bb E}[\<délka øetìzce>]} >> m$. Tato funkce vyu¾ívá podobných vlastností jako lineární konkurenèní generátor náhodných èísel, který pomocí vhodných konstant $A$ a $B$ a ¹íøky slova $2^w$ vyrábí nové náhodné èíslo $x'$ z minulého èísla $x$ jako $$x' = (x \cdot A + B) \mod 2^w.$$
  69
  70
  71 \s{Vìta} Pokud jsou $h(x_1), \dots, h(x_n)$ rovnomìrnì náhodné, pak $$\forall i: {\bb E}[\<poèet prvkù v i-té pøihrádce>] = {n \over m}.$$
  72
  73 \proof
  74 Poèet prvkù v $i$-té pøihrádce si oznaème $N_i$. Definujme si indikátor $P_{ij}$, který je roven 1, pokud $x_j$ padlo do $i$-té pøihrádky, jinak je roven 0.
  75 Vidíme, ¾e poèet prvkù v $i$-té pøihrádce je souèet $P_{ij}$ pøes v¹echny $j$.
  76 $$N_i = \sum_{j} P_{i,j}.$$
  77 Teï ji¾ staèí upravit následující výrazy. Vyu¾ijeme mimo jiné vìtu o linearitì støední hodnoty.
  78 $${\bb E}[P_{ij}] = {1 \over m} \cdot 1 + (1 - {1 \over m}) \cdot 0 = {1 \over m}.$$
  79 $${\bb E}[N_i] = {\bb E}[\sum_{j} P_{i,j}] = \sum_{j} {\bb E}[P_{i,j}] = {n \over m}.$$
  80 \qed
  81
  82 \s{Dùsledek:} Pokud bude $n$ pøibli¾nì stejnì velké jako $m$, tak v ka¾dé pøihrádce bude prùmìrnì jeden prvek.
  83
  84 \bye