{{TOC float}}
===Dynamické perfektní hashování===
Perfektní hashování nepodporuje efektivní INSERT a DELETE, to se snaží tyto metody řešit (dynamizace pravděpodobnostních algoritmů). Máme množiny funkcí <math> H_t:U\to\{0,\dots,t-1\}\,\!</math> pro <math> t\in\{1,\dots,N-1\}\,\!</math> tvaru <math> h_k(x)=(kx\mod N)\mod t\,\!</math> pro <math> k=1,\dots,N-1\,\!</math>. Volíme-li náhodně <math> k\,\!</math>, pak <math> h_k\in H_s\,\!</math> s pravd. <math> \geq 1/2\,\!</math> splňuje
:<math>\sum_{i=0}^{s-1}(b_i^k)^2<\frac{8n^2}{s}+2n\,\!</math>
kde <math> s=\frac{4}{3}\sqrt{6}(1+c)|S|\,\!</math> (pro fixované <math> c>1\,\!</math>). Označme <math> S_i=\{t\in S;h_k(t)=i\}\,\!</math> a pak zvolíme-li <math> j(i)\,\!</math> náhodně, je <math> h_{j(i)}\in H_{2(b_i^k)^2}\,\!</math> perfektní s pravd. <math> 1/2\,\!</math> -- předp. že takové <math> j(i)\,\!</math> máme <math> \forall i\in\{1,\dots,N-1\}\,\!</math>. Reprezentujme <math> S_i\,\!</math> funkcemi <math> h_{j(i)}\,\!</math>, pro každou zvláštní tabulkou <math> T_i\,\!</math> (pro <math> i\in\{0,\dots,s-1\}\,\!</math>).
Algoritmus MEMBER jen počítá hash-fce, INSERT zjistí, zda <math> x\in S\,\!</math>, není-li, najde příslušnou <math> T_i\,\!</math> (pomocí <math> i=(kx\mod N)\mod s\,\!</math>) a vloží. Pokud je funkce stále perfektní, je vše OK, jinak alg. spočítá novou perfektní hash-funkci pro novou <math> S_i\,\!</math> a vytvoří <math> T_i\,\!</math>. Když <math> k\,\!</math> nesplňuje pravděpodobnostní rovnici, přehashuje se vše -- spočte se nové <math> s\,\!</math> a nalezne správné <math> k\,\!</math>, rozdělí se do množin <math> S_i\,\!</math> a pro každé <math> i\,\!</math> se najde <math> j(i)\,\!</math> a vytvoří tabulka <math> T_i\,\!</math>. DELETE zjišťuje po odstranění, zda <math> k\,\!</math> splňuje pravděp. rovnici, pokud ne, provede přehashování.
Složitost -- lineárně paměti (bez uložení funkcí), MEMBER <math> O(1)\,\!</math> v nejhorším případě a INSERT, DELETE <math> O(1)\,\!</math> amortizovaně (bez důkazu).
====Druhá možnost: hypergrafy====
Hashuje do tabulky velikosti <math> n\,\!</math>. <math> r-\,\!</math>hypergraf -- hrany jsou <math> r-\,\!</math>prvkové podmnožiny mn. vrcholů. Cyklus -- hypergraf, kde každý vrchol leží alespoň ve 2 různých hranách. Mějme tedy ''acyklický'' <math> r\,\!</math>-hypergraf s <math> n\,\!</math> hranami. Nalezeneme funkci <math> g:V\to\{0,\dots,m-1\}\,\!</math> takovou, že <math> h:E\to\{0,\dots,m-1\}:h(e)=\sum_{i=1}^r g(v_i)\mod m\,\!</math> je prostá na <math> \{0,\dots,m-1\}\,\!</math>. To lze provést tak, že zvolím bijekci <math> h:E\to\{0,\dots,m-1\}\,\!</math> a pak je-li <math> g(v_i)\,\!</math> definováno pro <math> i=2,\dots,r\,\!</math>, definuji <math> g(v_1)=h(e)-\sum_{i=2}^r g(v_i)\mod m\,\!</math>. Protože v každém acyklickém <math> r-\,\!</math>hypergrafu existuje vrchol ležící jen v 1 hraně, lze toto použít ke kontrukci <math> g\,\!</math> indukcí. Pak naleznu funkce <math> f_1,\dots,f_r:U\to V\,\!</math> takové, že <math> E=\{(f_1(x),\dots,f_r(x));x\in S\}\,\!</math> je acyklický hypergraf. Celková hashovací funkce je definovaná
:<math>f(x)=\sum_{i=1}^r gf_i(x)\,\!</math>
Nejvýhodnější je, když <math> f_i\,\!</math> jsou náhodná zobrazení náhodně zvolená, nebo náhodná z nějakého <math> c\,\!</math>-univerzálního systému. Vyžaduje <math> O(rn+|V|)\,\!</math> času a <math> O(n\log n+r\log |V|)\,\!</math> paměti (bez důkazu).
{{Stub}}
{{Statnice I3}}
