{{TIN066 Skripta}}
{{TODO|Univerzální hashování. Důkazy a tak}}
= Univerzální hashování =
Naše hashovací funkce se pro některé vstupní množiny bude chovat dobře a pro jiné hůře. Abychom si vylepšili naše šance, zaveďme si místo toho obecnější třídu (rozumně různorodých) funkcí H; než začneme hashovat, vybereme z nich náhodnou funkci <math>h \in H</math> (ta se stane atributem konkrétní instance hashovací tabulky). Můžeme analyzovat chování přes celý prostor hashovacích funkcí H a nepotřebuji předpoklad rovnoměrně rozložených dat.
* Abychom měli snadnější práci, funkce si očíslujeme: <math>H = \{h_i|i \in I\}\colon U \to \{0,\ldots,m-1\}</math>
* Systém funkcí H je '''c-univerzální''' pro U, pokud <math>\forall x,y \in U, x \ne y: |\{h \in H|h(x) = h(y)\}| \le {c |H| \over m}</math>
** ekvivalentně pomocí pravděpodobnosti pro náhodně zvolené h,x,y: <math>P(h(x)=h(y)) \leq \frac{c}{m}</math>
Pro univerzální systém (= 1-univerzální) je pravděpodobnost kolize (= 1/m) stejná, jako kdybychom rozhodili x,y do přihrádek zcela náhodně.
Existuje takový systém? Pro <math>a,b \in U</math> mějme hašovací funkce dané předpisem:
* <math>h_{a,b}(x) = ((ax + b) \mod N) \mod m</math>
Těchto funkcí je <math>N^2</math>. Pro pevně daná různá <math>x, y \in U</math>, kolik funkci zobrazí x, y na stejný prvek? Když se zobrazí na stejný prvek, znamená to, že existuje <math>i \in \{0..m-1\}</math> (hodnota ''h'') a <math>r, s \in \{0.. \lceil \frac{N}{m}\rceil-1 \}</math> (násobky ''m'') takové, že:
* <math>(a x + b) \mod N = r \cdot m + i</math>
* <math>(a y + b) \mod N = s \cdot m + i</math>
To představuje dvě lineární rovnice v tělese <math>\mathbb{Z}_N</math> s neznámými a, b. Matice je regulární a soustava má právě jedno řešení. Rovnice se mohu lišit pravou stranou, každá pravá strana určuje jedno řešení (a, b). Počet pravých stran (= počet různých hodnot ''i, r, s'' = počet funkcí, zobrazujících x,y na stejný prvek) je <math>m \lceil \frac{N}{m}\rceil ^2</math>. Tento systém je c-univerzální, pokud:
* <math> m \lceil \frac{N}{m}\rceil ^2 \leq {c |H| \over m} = c \cdot {N^2 \over m}</math>
Což platí pro hodnotu ''c'' :
* <math> c = \frac{ m \lceil \frac{N}{m}\rceil ^2 } { \frac{N^2}{m} } = \frac{ \lceil \frac{N}{m}\rceil ^2 } { \frac{N^2}{m^2} } </math>
{{TODO|Důkazy. Různé další vlastnosti.}}
Očekávaný čas operací MEMBER, INSERT, DELETE je <math>O(1+c\alpha)</math>.
Vybrat z H nějakou funkci nemusí být jednoduché, velikost <math>|H|</math> totiž dost rychle roste a tak to může začít být obtížné. Podívejme se, jaké nejmenší c-univerzální systémy dokážeme najít!
Můžeme snadno dokázat, že <math>|I|\ge {m \over c}(\lceil\log_m N\rceil - 1)</math>, takže velikost systému roste alespoň s logaritmem velikosti univerza.
Dá se také dokázat existence 5-univerzálního systému, funkce vypadnouz takové zvláštní prvočíselné konstrukce.
Nakonec c se dá zdola odhadnout: <math>c > 1 - m/N</math>
= Perfektní hashování =
Máme předem danou množinu S a chceme vyrobit perfektní hashovací funkci h takovou, aby nikdy negenerovala pro prvky množiny kolize. Typicky potřebujeme hodně rychlý MEMBER a vůbec nepotřebujeme INSERT/DELETE. Samozřejmě chceme, aby h byla rychlá a malá (ne třeba další tabulka ;-). Při generování h si můžeme klidně dát trochu na čas.
Mějme univerzum <math>U = \{ 0,\ldots,N-1 \}</math> a soubor funkcí <math>H\colon U \to \{0,\ldots,m-1\}</math>. H bude <math>(N,m,n)</math>-perfektní, když <math>\forall S \subseteq U: |S| = n</math> existuje perfektní <math>h \in H</math>.
Lze odhadnout, že:
<math>|H| \ge {{N \choose n} \over {m \choose n}(N/m)^n}</math>
<math>|H| \ge {\log N \over \log m}</math>
Důkaz existence se provádí maticemi, logaritmy, páčidly a integrály.
Důkaz, že <math>|H| \ge {\log N \over \log m}</math> je poměrně jednoduchý (analýza ve skriptech je náročnější). Nechť pro spor platí, že <math>|H| \le {\log N \over \log m}</math>, potom <math>|H| \log m \le \log N</math> a když se zbavíme logaritmů, dostanem <math>m^{|H|} \le N</math>. Z přihrádkového principu plyne, že musí existovat alespoň dva prvky z <math>S</math>, které všechny funkce z <math>H</math> nahašují do jednoho políčka a to je spor s tím, že <math>H</math> je perfektní systém.
== Konstrukce ==
{{TODO|Důkazy; neměly by ale zamlžit princip, možná by bylo lepší mít podrobnou konstrukci se všemi odvozeními na zvláštní stránce}}
Kterak sobě perfektní funkci poříditi? Existuje mnoho různých způsobů, ukazují se tři:
=== Velikánská tabulka, malá funkce, rychle nalezená ===
Nechť N je prvočíslo, zavedeme si
* sadu funkcí <math>h_k(x) = (kx \mod N) \mod m\quad k=1,\ldots,N-1</math>
* počet kolizí <math>b_i^k = |\{ x | h_k(x)=i\}|</math> (trochu hloupá symbolika)
* "míru" kolizí <math>B_m^k = \sum_{i=0}^{m-1} (b_i^k)^2</math>
Takže pokud funkce <math>h_k</math> není perfektní, nějaké <math>b_i^k \ge 2</math> a tedy <math>B_m^k \ge n + 2</math>.
Co potřebuji? Najít (m,k) takové, aby <math>h_k</math> vedoucí do tabulky velikosti m byla perfektní.
Potřebujeme odhadnout m, o kterém toto umíme dokázat, to se dělá přes nějaké omezení shora míry kolizí.
Dojdeme k tomu, že platí:
* Pro <math>m=n(n-1)+1</math> existuje deterministický algoritmus, který v <math>O(nN)</math> nalezne perfektní k. (Prostě zkouší všech N možností, ověřit jednu trvá O(n).)
* Pro <math>m=2n(n-1)</math> existuje pravděpodobnostní algoritmus, který v <math>O(n)</math> nalezne perfektní k s pravděpodobností alespoň 1/4. (Prostě střelíme náhodné <math>k</math> a v průměru po čtyřech pokusech se trefíme.)
=== Malá tabulka, velká funkce, celkem rychle nalezená ===
Výše popsaný postup je fajn, ale potřebuje ''fakt velkou'' (kvadraticky velkou) tabulku. Půjdeme na to tedy trochu jinak; před chvílí jsme ve skutečnosti dostali ještě dva výsledky:
* Pro <math>m=n</math> existuje deterministický algoritmus, který v <math>O(nN)</math> nalezne k takové, že <math>B_m^k < 3n</math>
* Pro <math>m=n</math> existuje pravděpodobnostní algoritmus, který v očekávaném čase <math>O(n)</math> nalezne k takové, že <math>B_m^k < 4n</math>
BÚNO konstruujme deterministický algoritmus. Najdeme k, aby <math>B_m^k < 3n</math>. Mějme:
* Množinu kolidujících prvků <math>S_i = \{s \in S|h_k(s) = i\}</math>
* Velikost segmentu tabulky <math>c_i = |S_i|(|S_i|-1)+1</math>
Teď stačí pro každou neprázdnou <math>S_i</math> najít perfektní funkci <math>h_{k_i}</math> a naskládat segmenty pro všechny i za sebe a vyrobíme odpovídající perfektní funkci.
Ok, cílová tabulka je <math>m<3n</math>, časová složitost <math>O(nN)</math>. Teď ale zase máme problém, že si musíme pamatovat hashovací funkce pro všechny segmenty, to je <math>O(n \log N)</math> (druhý člen je prostor potřebný pro samotné číslo jedné funkce).
=== Malá tabulka, malá funkce, za dlouho nalezená ===
Nechť <math>\phi_p(x) = x \mod p</math> pro prvočíslo p. Platí, že pro každou n-prvkovou S existuje prvočíslo p nejvýše <math>O(n^2\ln N)</math> takové, že funkce <math>\phi_p</math> je perfektní. (To je celkem těžké, ale dokazuje se.)
Deterministický algoritmus prostě zkusí všechna možná p. Ověřit, že nějaká <math>\phi_p</math> je perfektní, trvá <math>O(n\log n)</math> (duplicity odhalím setříděním všech nabytelných hodnot). Najít prvočíslo trvá málo (Rabin-Miller <math>O(\log^3 p)</math>). Takže celkem to bude trvat <math>O(n^3\log n\log N)</math>. Pravděpodobnostní algoritmus (střílí p náhodná) to zvládne v očekávaném čase <math>O(n\log n(\log n + \log\log N))</math>.
{{TODO|Chybí algoritmus}}
= Dynamické perfektní hashování =
Dynamizace pravděpodobnostních algoritmů.
Přístup přes hypergrafy.
