TIN066 Univerzální a perfektní hashování
Obsah
Univerzální hashování[editovat | editovat zdroj]
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 $ h \in H $ (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: $ H = \{h_i|i \in I\}\colon U \to \{0,\ldots,m-1\} $
- Systém funkcí H je c-univerzální pro U, pokud $ \forall x,y \in U, x \ne y: |\{h \in H|h(x) = h(y)\}| \le {c |H| \over m} $
- ekvivalentně pomocí pravděpodobnosti pro náhodně zvolené h,x,y: $ P(h(x)=h(y)) \leq \frac{c}{m} $
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 $ a,b \in U $ mějme hašovací funkce dané předpisem:
- $ h_{a,b}(x) = ((ax + b) \mod N) \mod m $
Těchto funkcí je $ N^2 $. Pro pevně daná různá $ x, y \in U $, kolik funkci zobrazí x, y na stejný prvek? Když se zobrazí na stejný prvek, znamená to, že existuje $ i \in \{0..m-1\} $ (hodnota h) a $ r, s \in \{0.. \lceil \frac{N}{m}\rceil-1 \} $ (násobky m) takové, že:
- $ (a x + b) \mod N = r \cdot m + i $
- $ (a y + b) \mod N = s \cdot m + i $
To představuje dvě lineární rovnice v tělese $ \mathbb{Z}_N $ 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 $ m \lceil \frac{N}{m}\rceil ^2 $. Tento systém je c-univerzální, pokud:
- $ m \lceil \frac{N}{m}\rceil ^2 \leq {c |H| \over m} = c \cdot {N^2 \over m} $
Což platí pro hodnotu c :
- $ 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} } $
Očekávaný čas operací MEMBER, INSERT, DELETE je $ O(1+c\alpha) $.
Vybrat z H nějakou funkci nemusí být jednoduché, velikost $ |H| $ 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 $ |I|\ge {m \over c}(\lceil\log_m N\rceil - 1) $, 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: $ c > 1 - m/N $
Perfektní hashování[editovat | editovat zdroj]
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 $ U = \{ 0,\ldots,N-1 \} $ a soubor funkcí $ H\colon U \to \{0,\ldots,m-1\} $. H bude $ (N,m,n) $-perfektní, když $ \forall S \subseteq U: |S| = n $ existuje perfektní $ h \in H $.
Lze odhadnout, že: $ |H| \ge {{N \choose n} \over {m \choose n}(N/m)^n} $ $ |H| \ge {\log N \over \log m} $
Důkaz existence se provádí maticemi, logaritmy, páčidly a integrály.
Důkaz, že $ |H| \ge {\log N \over \log m} $ je poměrně jednoduchý (analýza ve skriptech je náročnější). Nechť pro spor platí, že $ |H| \le {\log N \over \log m} $, potom $ |H| \log m \le \log N $ a když se zbavíme logaritmů, dostanem $ m^{|H|} \le N $. Z přihrádkového principu plyne, že musí existovat alespoň dva prvky z $ S $, které všechny funkce z $ H $ nahašují do jednoho políčka a to je spor s tím, že $ H $ je perfektní systém.
Konstrukce[editovat | editovat zdroj]
Kterak sobě perfektní funkci poříditi? Existuje mnoho různých způsobů, ukazují se tři:
Velikánská tabulka, malá funkce, rychle nalezená[editovat | editovat zdroj]
Nechť N je prvočíslo, zavedeme si
- sadu funkcí $ h_k(x) = (kx \mod N) \mod m\quad k=1,\ldots,N-1 $
- počet kolizí $ b_i^k = |\{ x | h_k(x)=i\}| $ (trochu hloupá symbolika)
- "míru" kolizí $ B_m^k = \sum_{i=0}^{m-1} (b_i^k)^2 $
Takže pokud funkce $ h_k $ není perfektní, nějaké $ b_i^k \ge 2 $ a tedy $ B_m^k \ge n + 2 $.
Co potřebuji? Najít (m,k) takové, aby $ h_k $ 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 $ m=n(n-1)+1 $ existuje deterministický algoritmus, který v $ O(nN) $ nalezne perfektní k. (Prostě zkouší všech N možností, ověřit jednu trvá O(n).)
- Pro $ m=2n(n-1) $ existuje pravděpodobnostní algoritmus, který v $ O(n) $ nalezne perfektní k s pravděpodobností alespoň 1/4. (Prostě střelíme náhodné $ k $ a v průměru po čtyřech pokusech se trefíme.)
Malá tabulka, velká funkce, celkem rychle nalezená[editovat | editovat zdroj]
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 $ m=n $ existuje deterministický algoritmus, který v $ O(nN) $ nalezne k takové, že $ B_m^k < 3n $
- Pro $ m=n $ existuje pravděpodobnostní algoritmus, který v očekávaném čase $ O(n) $ nalezne k takové, že $ B_m^k < 4n $
BÚNO konstruujme deterministický algoritmus. Najdeme k, aby $ B_m^k < 3n $. Mějme:
- Množinu kolidujících prvků $ S_i = \{s \in S|h_k(s) = i\} $
- Velikost segmentu tabulky $ c_i = |S_i|(|S_i|-1)+1 $
Teď stačí pro každou neprázdnou $ S_i $ najít perfektní funkci $ h_{k_i} $ a naskládat segmenty pro všechny i za sebe a vyrobíme odpovídající perfektní funkci.
Ok, cílová tabulka je $ m<3n $, časová složitost $ O(nN) $. Teď ale zase máme problém, že si musíme pamatovat hashovací funkce pro všechny segmenty, to je $ O(n \log N) $ (druhý člen je prostor potřebný pro samotné číslo jedné funkce).
Malá tabulka, malá funkce, za dlouho nalezená[editovat | editovat zdroj]
Nechť $ \phi_p(x) = x \mod p $ pro prvočíslo p. Platí, že pro každou n-prvkovou S existuje prvočíslo p nejvýše $ O(n^2\ln N) $ takové, že funkce $ \phi_p $ je perfektní. (To je celkem těžké, ale dokazuje se.)
Deterministický algoritmus prostě zkusí všechna možná p. Ověřit, že nějaká $ \phi_p $ je perfektní, trvá $ O(n\log n) $ (duplicity odhalím setříděním všech nabytelných hodnot). Najít prvočíslo trvá málo (Rabin-Miller $ O(\log^3 p) $). Takže celkem to bude trvat $ O(n^3\log n\log N) $. Pravděpodobnostní algoritmus (střílí p náhodná) to zvládne v očekávaném čase $ O(n\log n(\log n + \log\log N)) $.
Dynamické perfektní hashování[editovat | editovat zdroj]
Dynamizace pravděpodobnostních algoritmů.
Přístup přes hypergrafy.
