TIN066 Univerzální a perfektní hashování
Obsah
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 $ 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í
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
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í $ 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á
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á
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í
Dynamizace pravděpodobnostních algoritmů.
Přístup přes hypergrafy.
