{{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í''', pokud <math>\forall x,y \in U, x \ne y: |\{i \in I|h_i(x) = h_i(y)\}| \le {c |I| \over m}</math>
* Tedy čím menší ''c'', tím jsou funkce z H "různorodější"
Existuje takový systém? Tak si jeden postavme:
* <math>h_{a,b}(x) = ((ax + b) \mod N) \mod m</math>
Frobeniova věta omezuje počet řešení číslem <math>m\lceil N/m\rceil^2</math>. Tedy:
* <math>c = {\lceil N/m \rceil^2 \over (N/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.
== 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 = |\{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.
