Základní problém: Reprezentace množin a operace s nimi. V řadě úloh a algoritmů je tento

Datové struktury – haˇsov´ an´ı Pˇredn´ aˇska 1 ´ Uvod Základn´ı problém: Reprezentace mnoˇzin a operace s nimi. V ˇradˇe u ´loh a algoritm˚ u je tento podproblém rozhoduj´ıc´ı pro sloˇzitost ˇreˇsen´ı, protoˇze tyto operace se mnohokrát opakuj´ı. Proto je tˇreba navrhnout pro tyto u ´lohy co nejefektivnˇejˇs´ı algoritmy (kaˇzd´ y uˇsetˇren´ y ˇcas mnohonásobn´ ym opakován´ım zaˇcne hrát d˚ uleˇzitou roli). Proto je tˇreba detailn´ı anal´ yza sloˇzitosti v závislosti na vnˇejˇs´ıch okolnostech. Nelze ˇr´ıct, ˇze nˇekter´ y algoritmus je nejlepˇs´ı, protoˇze za urˇcit´ ych okolnost´ı m˚ uˇze b´ yt ‘ménˇe efektivn´ı’ algoritmus v´ yhodnˇejˇs´ı. Základn´ı problém je slovn´ıkov´ y problém: Dáno univerzum U , máme reprezentovat S ⊆ U a navrhnout algoritmy pro následuj´ıc´ı operace MEMBER(x) – zjist´ı, zda x ∈ S, a nalezne jeho uloˇzen´ı INSERT(x) – kdyˇz x ∈ / S, pak vloˇz´ı x do struktury reprezentuj´ıc´ı S DELETE(x) – kdyˇz x ∈ S, pak odstran´ı x ze struktury reprezentuj´ıc´ı S. ˇ v nejhorˇs´ım pˇr´ıpaEfektivita algoritmu: ˇcasová sloˇzitost, prostorová sloˇzitost vyˇsetˇrená bud dˇe nebo v pr˚ umˇerném pˇr´ıpadˇe nebo amortizovanˇe. Literatura: K. Mehlhorn: Data Structures and Algorithms 1: Sorting and Searching, Springer 1984 http://www.mpi-sb.mpg.de/∼ mehlhorn/DatAlgbooks.html J. S. Vitter, W.-Ch. Chen: Design and Analysis of Coalesced Hashing, Oxford Univ. Press, 1987

Haˇsov´ an´ı Pomoc´ı pole m˚ uˇzeme rychle implementovat operace MEMBER, INSERT a DELETE. Nev´ yhoda: kdyˇz je velké univerzum, pak je prostorová sloˇzitost v nejlepˇs´ım pˇr´ıpadˇe ohromná, ve ˇspatném pˇr´ıpadˇe nelze pole zadat do poˇc´ıtaˇce. Haˇsován´ı chce zachovat rychlost operac´ı, ale odstranit pamˇeˇtovou nároˇcnost. Prvn´ı publikovan´ y ˇclánek o haˇsován´ı je od Petersona 1957, ale existuje technická zpráva od IBM o haˇsován´ı z roku 1953. Základn´ı idea: Dáno univerzum U a mnoˇzina S ⊆ U tak, ˇze |S| << |U |. Máme funkci h:U − → {0, 1, . . . , m − 1} a mnoˇzinu S reprezentujeme tabulkou (polem) s m ˇrádky tak, ˇze s ∈ S je uloˇzen na ˇrádku h(s). Nev´ yhoda: mohou existovat r˚ uzná s, t ∈ S taková, ˇze h(s) = h(t) - tento jev se naz´ yv´ a kolize. Hlavn´ı problém: ˇreˇsen´ı koliz´ı. Základn´ı ˇreˇsen´ı: pouˇzijeme pole o velikosti [0..m − 1] a i-tá poloˇzka pole bude spojov´ y seznam obsahuj´ıc´ı vˇsechny prvky s ∈ S takové, ˇze h(s) = i. Toto ˇreˇsen´ı se naz´ yvá haˇsov´ an´ı se separovan´ ymi ˇretˇezci. Pˇr´ıklad: U = {1, 2, . . . , 1000}, S = {1, 7, 11, 53, 73, 141, 161} a funkce je h(x) = x mod 10. Pak P (0) = P (2) = P (4) = P (5) = P (6) = P (8) = P (9) jsou prázdné seznamy, P (7) =< 7 >, P (3) =< 53, 73 >, P (1) =< 1, 141, 11, 161 >. Seznamy nemus´ı b´ yt uspoˇrádané. 1

2

Algoritmy operac´ı MEMBER(x) 1) Spoˇc´ıtáme i := h(x); 2) if i-t´ y seznam je neprázdn´ y then t :=prvn´ı prvek i-tého seznamu while t 6= x a t 6=posledn´ı prvek i-tého seznamu do t :=následuj´ıc´ı prvek i-tého seznamu enddo endif 3) if t = x then x ∈ S else x ∈ / S endif INSERT(x) 1) Spoˇc´ıtáme i := h(x); 2) if i-t´ y seznam je neprázdn´ y then t :=prvn´ı prvek i-tého seznamu while t 6= x a t 6=posledn´ı prvek i-tého seznamu do t :=následuj´ıc´ı prvek i-tého seznamu enddo endif 3) if t 6= x then vloˇz´ıme x do i-tého seznamu endif DELETE(x) 1) Spoˇc´ıtáme i := h(x); 2) if i-t´ y seznam je neprázdn´ y then t :=prvn´ı prvek i-tého seznamu while t 6= x a t 6=posledn´ı prvek i-tého seznamu do t :=následuj´ıc´ı prvek i-tého seznamu enddo endif 3) if t = x then odstran´ıme x z i-tého seznamu endif V následuj´ıc´ı anal´ yze pˇredpokládáme, ˇze hodnota funkce h(x) je spoˇcitatelná v ˇcase O(1). V nejhorˇs´ım pˇr´ıpadˇe operace vyˇzaduj´ı ˇcas O(|S|) (vˇsechny prvky jsou v jednom seznamu). Poˇzadovaná pamˇeˇtová nároˇcnost O(m + |S|) (pˇredpokládáme, ˇze s ∈ S vyˇzaduje pamˇeˇt O(1)). Pamˇeˇt vˇsak nen´ı efektivnˇe vyuˇzitá Spoˇc´ıtáme oˇcekávanou délku ˇretˇezc˚ u za pˇredpoklad˚ u 1) h je rychle spoˇcitatelná (a pevná bˇehem v´ ypoˇctu) 2) h rozdˇeluje univerzum U rovnomˇernˇe (tj. −1 ≤ |h−1 (i)| − |h−1 (j)| ≤ 1 pro i, j ∈ {0, 1, . . . , m − 1}) 3) S je náhodnˇe vybraná z univerza U (tj. kaˇzd´ y prvek z U je v S se stejnou pravdˇepodobnost´ı) 4) kaˇzd´ y prvek z U má stejnou pravdˇepodobnost b´ yt argumentem operace. Pouˇzité znaˇcen´ı: |S| = n, m =poˇcet seznam˚ u, |U | = N , n faktor naplnˇen´ı (load factor) ℓ(i) =délka i-tého ˇretˇezce, α = m D˚ usledky pˇredpoklad˚ u: 1 Prob(h(x) = i) = m pro vˇ x ∈ U a vˇsechna i = 0, 1, . . . , m − 1 sechna n 1 n−l 1 l ) pro vˇsechna i = 0, 1, . . . , m − 1. Prob(ℓ(i) = l) = pn,l = l ( m ) (1 − m Vysvˇetlen´ı: i-t´ y ˇretˇezec má d´ a, ˇze elku l, právˇe kdyˇz existuje podmnoˇzina A ⊆ S takov´ |A| = l (tˇechto moˇznost´ı je nl ), pro kaˇzdé x ∈ A plat´ı h(x) = i (pravdˇepodobnost tohoto 1 n−l 1 l ) ) a pro kaˇzdé x ∈ S\A plat´ı h(x) 6= i (pravdˇepodobnost tohoto jevu je (1− m ) . jevu je ( m

3

Oˇcekávan´ a délka ˇretˇezc˚ u E(l) =

n X

lpn,l

l=0

n n X n 1 l 1 n−l X n! 1 1 ( ) (1 − ) = l = l ( )l (1 − )n−l = l m m l!(n − l)! m m l=0

l=0

n (n − 1)! 1 1 n X ( )l−1 (1 − )n−l = m (l − 1)!(n − l)! m m l=1 n n X n − 1 1 l−1 1 ( ) (1 − )(n−1)−(l−1) = l−1 m m m l=1 n−1 1 n 1 1 n n X n−1 1 l ( ) (1 − )n−1−l = ( + 1 − )n−1 = . l m m m m m m m l=0

V´ ypoˇcet druhého momentu 2

E(l ) =E(l(l − 1)) + E(l)E(l(l − 1)) =

n X l=0

n X

n 1 l 1 ( ) (1 − )n−l = l(l − 1) l m m

1 n − 2 1 l−2 n(n − 1) ( ) (1 − )(n−2)−(l−2) = 2 l−2 m m m l=2 n−2 1 n−2−l n(n − 1) n(n − 1) X n − 2 1 l ( ) (1 − ) = l m2 m m m2 l=0

E(l2 ) =

n(n − 1) n n n−1 + = (1 + ) 2 m m m m

V´ ypoˇcet rozptylu var(l) = E(l − E(l))2 = E(l2 ) − (E(l))2 = Shrneme v´ ysledky: Oˇcekávaná délka ˇretˇezc˚ u je

n m

n−1 n n 1 n (1 + ) − ( )2 = (1 − ). m m m m m

a rozptyl délky ˇretˇezc˚ u je

n m (1

−

1 m ).

Oˇcekávan´ y nejhorˇs´ı pˇr´ıpad Spoˇc´ıtáme EN P oˇcekávanou délku maximáln´ıho ˇretˇezce. Oznaˇcme ℓ(i) délku i-tého ˇretˇezce. Pak Prob(max ℓ(i) = j) = Prob(max ℓ(i) ≥ j) − Prob(max ℓ(i) ≥ j + 1). i

i

i

4

Pak m˚ uˇzeme poˇc´ıtat: X X j(Prob(max ℓ(i) ≥ j) − Prob(max ℓ(i) ≥ j + 1)) = j Prob(max ℓ(i) = j) = EN P = i

j

X

j Prob(max ℓ(i) ≥ j) − i

j

X

X

X

i

X

i

(j − 1) Prob(max ℓ(i) ≥ j) = i

j

(j − j + 1) Prob(max ℓ(i) ≥ j) = i

j

i

j Prob(max ℓ(i) ≥ j + 1) =

j

j Prob(max ℓ(i) ≥ j) −

j

i

j

X

Prob(max ℓ(i) ≥ j)

j

i

Vysvˇetlen´ı: Pˇri ˇctvrté rovnosti se v druhé sumˇe zvˇetˇsil index, pˇres kter´ y sˇc´ıtáme, o 1, v p´ até rovnosti se k sobˇe daly koeficienty pˇri stejn´ ych pravdˇepodobnostech ve dvou sumách. Odtud Prob(max ℓ(i) ≥ j) = Prob(ℓ(1) ≥ j ∨ ℓ(2) ≥ j ∨ · · · ∨ ℓ(m − 1) ≥ j) ≤ i X n 1 j ( ) = Prob(ℓ(i) ≥ j) ≤ m j m i Qj−1 1 n k=0 (n − k) 1 j−1 ( ) ≤ n( )j−1 . j! m m j! Vysvˇetlen´ı: Prvn´ı nerovnost plyne z toho, ˇze pravdˇepodobnost disjunkce jev˚ u je menˇs´ı neˇz souˇcet pravdˇepodobnost´ı jev˚ u, druhá nerovnost plyne z toho, ˇze i-t´ y ˇretˇezec má délku j, jakmile existuje podmnoˇzina A ⊆ S taková, ˇze |A| = j (tˇechto moˇznost´ı je nj ) a pro kaˇzdé 1 j x ∈ A plat´ı h(x) = i (pravdˇepodobnost tohoto jevu je ( m ) ). n j−1 1 D˚ usledek. Prob(maxi ℓ(i) ≥ j) ≤ min{1, n( m ) }. j!

Pˇredpoklad: α =

n m

n j−1 1 ≤ 1. Pak pro j0 = min{j | n( m ) ı j! ≤ 1} plat´

j j n j−1 1 ) ≤ 1} ≤ min{j | n ≤ j!} ≤ min{j | n ≤ ( ) 2 } = m j! 2 j 2 log n 2 log n j ≤ j} ≤ min{j | }= min{j | log n ≤ log( )} = min{j | j log n 2 2 log( 2 ) log( log( j ) )

j0 = min{j | n(

2

min{j |

2 log n 2 log n ≤ j}, ≤ j} ≤ min{j | j log log n log log n − log log( 2 )

odtud dostáváme, ˇze j0 = O( logloglogn n ). j

Vysvˇetlen´ı: Druhá nerovnost plyne z faktu, ˇze j! ≥ ( 2j ) 2 a tˇret´ı nerovnost jsme dostali dosazen´ım nerovnosti pro j do j ve jmenovateli v pˇredchoz´ım v´ yrazu charakterizuj´ıc´ım j. V ostatn´ıch u ´pravách jsme pouˇzili jen algebraické u ´pravy.

5

Toto pouˇzijeme pˇri odhadu EN P . EN P =

X

Prob(max ℓ(i) ≥ j) ≤

X

1+

X

i

j

j0

j

j=j0 +1

j=1

j0 +

∞ X

X

(

j=j0 +1

min{1, n(

∞ ∞ X n j−1 1 n n X j0 ! n( ) ≤ j0 + = j0 + ≤ m j! j! j ! j! 0 j=j +1 j=j +1 0

0

1 )j−j0 ≤ j0 + j0 + 1

1 j0 +1 − j01+1 +

Vysvˇetlen´ı: Pˇri druhé nerovnosti jsme pouˇzili, ˇze ˇze jn0 ! ≤ 1, pˇri ˇctvrté nerovnosti jsme pouˇzili 1 j0 ! = Qj j! k=j

0+1

Shrneme z´ıskan´ y v´ ysledek

n j−1 1 ) }= m j!

k

≤(

n m

1

= j0 +

1 = O(j0 ) j0

≤ 1, pˇri tˇret´ı nerovnosti jsme pouˇzili,

1 )j−j0 . j0 + 1

n Vˇ eta. Za pˇredpokladu α = m ≤ 1 je pˇri haˇsov´ an´ı se separuj´ıc´ımi ˇretˇezci horn´ı odhad log n oˇcek´ avané délky maxim´ aln´ıho ˇretˇezce O( log log n ). Kdyˇz 0.5 ≤ α ≤ 1, je to z´ aroveˇ n i doln´ı odhad.

Oˇcekávan´ y poˇcet test˚ u Test je porovnán´ı argumentu operace s prvkem na daném m´ıstˇe ˇretˇezce nebo zjiˇstˇen´ı, ˇze vyˇsetˇrovan´ y ˇretˇezec je prázdn´ y. Budeme rozliˇsovat dva pˇr´ıpady u ´spˇeˇsné vyhledáván´ı, kdyˇz argument operace je mezi prvky reprezentované mnoˇziny, ne´ uspˇeˇsné vyhledáván´ı, kdyˇz argument operace nen´ı mezi prvky reprezentované mnoˇziny.

Ne´ uspˇeˇsné vyhled´ aván´ı Oˇcekávan´ y poˇcet test˚ u: E(T ) = Prob(ℓ(i) = 0) +

X l

l Prob(ℓ(i) = l) = pn,0 +

X l

lpn,l = (1 −

1 n n ) + ≈ e−α + α. m m

Vysvˇetlen´ı: Zjiˇstˇen´ı, zda ˇretˇezec je prázdn´ y, vyˇzaduje jeden test, tj. Prob(ℓ(i) = 0 nen´ı s koeficientem 0, ale 1. Protoˇze pravdˇepodobnosti jsou stejné pro P vˇsechny ˇretˇezce, nemus´ıme specifikovat ˇretˇezec, kter´ y vyˇsetˇrujeme, staˇc´ı psát obecnˇe i. c´ıtali pˇri l lpn,l jsme spoˇ v´ ypoˇctu oˇcekávané délky ˇretˇezce.

6

´ eˇsné vyhled´ Uspˇ aván´ı Zvolme jeden ˇretˇezec prvk˚ u o délce l. Poˇcet test˚ u pˇri vyhledán´ı vˇsech prvk˚ u v tomto ˇretˇezci je l+1 . 1+2+···+l = 2 P Oˇcekávan´ y poˇcet test˚ u pˇri vyhledán´ı vˇsech prvk˚ u v nˇejakém ˇretˇezci je l l+1 Prob(ℓ(i) = 2 P l+1 l) = l 2 pn,l . P Oˇcekán´ y poˇcet test˚ u pˇri vyhledán´ı vˇsech prvk˚ u v tabulce je m l l+1 pn,l . 2 Oˇcekávan´ y poˇcet test˚ u pro vyhledán´ı jednoho prvku je

n n n X mX l+1 m X 2 pn,l = l pn,l + lpn,l = n n 2n l=0

m 2n

l=0 n X l=1

l=0

l(l − 1)pn,l + 2

n X l=1

lpn,l =

m n(n − 1) 2m n−1 ( + )= +1 ≈ 2 2n m n 2m α 1+ . 2 Jin´ y postup: Poˇcet test˚ u pˇri u ´spˇeˇsném vyhledáván´ı prvku x ∈ S je 1+poˇcet porovn´ an´ı kl´ıˇc˚ u pˇri ne´ uspˇeˇsném vyhledáván´ı x v operaci INSERT(x). Poˇcet porovnán´ı kl´ıˇc˚ u je délka ˇretˇezce, a proto oˇcekávan´ y poˇcet porovnán´ı kl´ıˇc˚ u je oˇcekávaná délka ˇretˇezce. Tedy oˇcek´ avan´ y poˇcet test˚ u pˇri u ´spˇeˇsném vyhledáván´ı x je 1+oˇcekávaná délka ˇretˇezce v okamˇziku vkl´ ad´ an´ı x, neboli n−1 i n−1 1X (1 + ) = 1 + . n i=0 m 2m Vˇ eta. Pˇri haˇsov´ an´ı se separovan´ ymi ˇretˇezci je oˇcek´ avan´ y poˇcet test˚ u pˇri ne´ uspeˇsném vyα −α hled´ avan´ı pˇribliˇznˇe e + α a pˇri u ´spˇeˇsném vyhled´ av´ an´ı pˇribliˇznˇe 1 + 2 . Následuj´ıc´ı tabulka dává pˇrehled oˇcekávaného poˇctu test˚ u pro r˚ uzné hodnoty α α ne´ usp. u ´spˇeˇs. α ne´ usp. u ´spˇeˇs.

vyh. vyh. vyh. vyh.

0 0.1 0.2 0.3 0.4 0.5 0.6 1 1.005 1.019 1.041 1.07 1.107 1.149 1 1.05 1.1 1.15 1.2 1.25 1.3 0.7 0.8 0.9 1 2 3 1.196 1.249 1.307 1.368 2.135 3.05 1.35 1.4 1.45 1.5 2 2.5

7

Vˇsimnˇete si, ˇze oˇcekávan´ y poˇcet test˚ u pˇri ne´ uspˇeˇsném vyhledáván´ı je menˇs´ı neˇz oˇcek´ avan´ y poˇcet test˚ u pˇri u ´spˇeˇsném vyhledáván´ı, kdyˇz α ≤ 1. Na prvn´ı pohled vypadá tento v´ ysledek nesmyslnˇe, ale d˚ uvod je, ˇze poˇcet test˚ u pˇri u ´spˇeˇsném vyhledáván´ı pr˚ umˇerujeme proti n, kdeˇzto pˇri ne´ uspˇeˇsném vyhledáván´ı proti m. Ilustrujeme to na následuj´ıc´ım pˇr´ıkladu: ˇ Nechˇt n = m azdn´ ych ˇretˇezc˚ u má délku 1 a polovina má délku 2. 2 a necht polovina nepr´ Oˇcekávan´ y poˇcet test˚ u pˇri ne´ uspˇeˇsném vyhledávan´ı – 1 test pro prázdné ˇretˇezce a ˇretˇezce délky 1; tˇechto pˇr´ıpad˚ u je 5m 6 . – 2 testy pro ˇretˇezce délky 2; tˇechto pˇr´ıpad˚ u je m 6 m 7 1 (1 5m + 2 ) = . Oˇcekávan´ y poˇcet test˚ u je m 6 6 6 Oˇcekávan´ y poˇcet test˚ u pˇri u ´spˇeˇsném vyhledáván´ı – 1 test pro prvky na prvn´ım m´ıstˇe ˇretˇezce; tˇechto pˇr´ıpad˚ u je 2n 3 – 2 testy pro prvky, které jsou na druhém m´ıstˇe ˇretˇezce; tˇechto pˇr´ıpad˚ u je n3 . + 2 n3 ) = 34 . Oˇcekávan´ y poˇcet test˚ u je n1 (1 2n 3 Velikost α je doporuˇcována menˇs´ı neˇz 1, ale nemá b´ yt hodnˇe mal´ a, protoˇze by pamˇeˇt nebyla efektivnˇe vyuˇzita. medskip Vylepˇsen´ı metody: haˇsován´ı s uspoˇrádan´ ymi ˇretˇezci. Rozd´ıl proti p˚ uvodn´ı metodˇe – ˇretˇezce jsou uspoˇrádané ve vzr˚ ustaj´ıc´ım poˇrad´ı. Protoˇze ˇretˇezce obsahuj´ı stejné prvky, je poˇcet oˇcekávan´ ych test˚ u pˇri u ´spˇeˇsném vyhledáván´ı stejn´ y jako u neuspoˇrádan´ ych ˇretˇezc˚ u. Pˇri ne´ uspˇeˇsném vyhledáván´ı konˇc´ıme, kdyˇz argument operace je menˇs´ı neˇz vyˇsetˇrovan´ y prvek v ˇretˇezci, tedy konˇc´ıme dˇr´ıv. Následuj´ıc´ı vˇeta (bez d˚ ukazu) uvád´ı oˇcekavan´ y poˇcet test˚ uv ne´ uspˇeˇsném pˇr´ıpadˇe. Vˇ eta. Oˇcek´ avan´ y poˇcet test˚ u pˇri ne´ uspˇeˇsném vyhled´ av´ an´ı pro haˇsov´ an´ı s uspoˇra ´dan´ ymi α 1 −α −α ˇretˇezci je pˇribliˇznˇe e + 1 + 2 − α (1 − e ). Oˇcek´ avan´ y poˇcet test˚ u pˇri u ´spˇeˇsném vyhled´ av´ an´ı pro haˇsov´ an´ı s uspoˇra ´dan´ ymi ˇretˇezci je pˇribliˇznˇe 1 + α2 .

8

Na závˇer uvedeme algoritmy pro operace s uspoˇrádan´ ymi ˇretˇezci.

Algoritmy MEMBER(x) 1) Spoˇc´ıtáme i := h(x); 2) if i-t´ y seznam je neprázdn´ y then t :=prvn´ı prvek i-tého seznamu while t < x a t 6=posledn´ı prvek i-tého seznamu do t :=následuj´ıc´ı prvek i-tého seznamu enddo endif 3) if t = x then x ∈ S else x ∈ / S endif INSERT(x) 1) Spoˇc´ıtáme i := h(x); 2) if i-t´ y seznam je neprázdn´ y then t:=prvn´ı prvek i-tého seznamu while t < x a t 6=posledn´ı prvek i-tého seznamu do t :=následuj´ıc´ı prvek i-tého seznamu enddo endif 3) if t 6= x then vloˇz´ıme x do i-tého seznamu za prvek t endif DELETE(x) 1) Spoˇc´ıtáme i := h(x); 2) if i-t´ y seznam je neprázdn´ y then t:=prvn´ı prvek i-tého seznamu while t < x a t 6=posledn´ı prvek i-tého seznamu do t :=následuj´ıc´ı prvek i-tého seznamu enddo endif 3) if t = x then odstran´ıme x z i-tého seznamu endif

9

Pˇredn´ aˇska 2 Nev´ yhody haˇsovan´ı se separovan´ ymi ˇretˇezci – nevyuˇzit´ı alokované pamˇeti (nehospodárné) pouˇz´ıván´ı ukazatel˚ u ˇ Reˇsen´ı: vyuˇz´ıt pro ˇretˇezce p˚ uvodn´ı tabulku. Poloˇzky tabulky: key, odkaz na uloˇzená data, poloˇzky pro práci s tabulkou Pˇredpokládáme, ˇze data jsou velká, v tom pˇr´ıpadˇe se ukládaj´ı mimo tabulku. V tabulce je jen odkaz na uloˇzená data. Pˇri popisu práce s tabulkou tuto ˇcást budeme vynechávat (tj. data budou pouze kl´ıˇc). Podle ˇreˇsen´ı kolize dˇel´ıme dál haˇsován´ı: haˇsován´ı s pˇrem´ısˇtován´ım, haˇsován´ı s dvˇema ukazateli, sr˚ ustaj´ıc´ı haˇsován´ı, dvojité haˇsován´ı a haˇsován´ı s lineárn´ım pˇridáván´ım.

Haˇsov´ an´ı s pˇrem´ısˇtov´ an´ım Poloˇzky pro práci s tabulkou: next, previous poloˇzka next – ˇc´ıslo ˇrádku tabulky obsahuj´ıc´ı následuj´ıc´ı u ´daj poloˇzka previous – ˇc´ıslo ˇrádku tabulky obsahuj´ıc´ı pˇredchoz´ı u ´daj Pˇr´ıklad: U = {1, 2, . . . , 1000}, h(x) = x mod 10, uloˇzená mnoˇzina S = {1, 7, 11, 53, 73, 141, 161}, ˇretˇezce: P (1) = (1, 141, 11, 161), P (3) = (73, 53), P (7) = (7). Haˇsovac´ı tabulka: ˇrádek P(0) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9)

key

next

1

9

73

6

161 53 7 11 141

previous

8 3 5 8

9 1

Tabulka vznikla následuj´ıc´ı posloupnost´ı operac´ı: INSERT(1), INSERT(141), INSERT(11), INSERT(73), INSERT(53), INSERT(7), INSERT(161).

10

1) 2) 3) 4)

MEMBER(x): Spoˇc´ıtáme i := h(x), if i.previous 6=prázdné nebo i.key =prázdné then goto 4) endif while i.next 6=prázdné a i.key 6= x do i := i.next enddo if i.key = x then x ∈ S else x ∈ / S endif

DELETE(x): 1) Spoˇc´ıtáme i := h(x), 2) if i.previous 6=prázdné nebo i.key =prázdné then stop endif 3) while i.next 6=prázdné a i.key 6= x do i := i.next enddo 4) if i.key = x then (i.previous).next := i.next, (i.next).previous := i.previous, i.key := i.next := i.previous :=prázdné endif Insert(x): 1) Spoˇc´ıtáme i := h(x), 2) if i.previous 6=prázdné nebo i.key =prázdné then goto 5) endif 3) while i.next 6=prázdné a i.key 6= x do i := i.next enddo 4) if neexistuje prázdn´ y ˇrádek tabulky then pˇreplnˇen´ı else nechˇt j je voln´ y ˇrádek tabulky i.next := j, j.key := x, j.previous := i, stop endif 5) if i.key =prázdné then i.key := x else if neexistuje prázdn´ y ˇrádek tabulky then pˇreplnˇen´ı ˇ else necht j je voln´ y ˇrádek tabulky j.key := i.key, j.previous := i.previous, j.next := i.next, (j.previous).next := j, (j.next).previous := j, i.key := x, i.next := i.previous :=pr´ azdné endif endif V pˇr´ıkladu provedeme Insert(28), nov´ y ˇrádek je 4. ˇrádek – v´ ysledná haˇsovac´ı tabulka ˇrádek P(0) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9)

key

next

1

9

73 11 161 53 7 28 141

6 5

4

previous

9 4 3

1

Oˇcekávan´ y poˇcet porovnán´ı je stejn´ y jako pro haˇsován´ı se separuj´ıc´ımi ˇretˇezci: n−1 u ´spˇeˇsné vyhledáván´ı: 2m + 1 ≈ 1 + α2 n 1 n ) +m ≈ e−α + α ne´ uspˇeˇsné vyhledáván´ı: (1 − m n kde m – velikost tabulky, n – velikost S tj. poˇcet uloˇzen´ ych prvk˚ u, α = m – faktor zaplnˇen´ı

11

Haˇsov´ an´ı s dvˇema ukazateli Nev´ yhoda haˇsován´ı s pˇrem´ısˇtován´ım krok 5) v operaci INSERT. Vyˇzaduje v´ıce ˇcasu – operace s pˇrem´ıstˇen´ım poloˇzky. Dalˇs´ı implementace haˇsován´ı se separuj´ıc´ımi ˇretˇezci. Poloˇzky pro práci s tabulkou – next, begin Poloˇzka next – ˇc´ıslo ˇrádku tabulky obsahuj´ıc´ı následuj´ıc´ı u ´daj begin – ˇc´ıslo ˇrádku tabulky obsahuj´ıc´ı prvn´ı prvek ˇretˇezce tohoto m´ısta Stejná data jako v minulém pˇr´ıpadˇe Haˇsovac´ı tabulka: ˇrádek P(0) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9)

key

next

begin

1

9

1

73

7

3

161 7 53 11 141

6 5 8

Tabulka vznikla následuj´ıc´ı posloupnost´ı operac´ı: INSERT(1), INSERT(141), INSERT(11), INSERT(73), INSERT(53), INSERT(7), INSERT(161). MEMBER(x): 1) Spoˇc´ıtáme i := h(x), 2) if i.begin =prázdné then goto 4) else i := i.begin endif 3) while i.next 6=prázdné a i.key 6= x do i := i.next enddo 4) if i.key = x then x ∈ S else x ∈ / S endif DELETE(x): 1) Spoˇc´ıtáme i := h(x), 2) if i.begin =prázdné then stop else j := i, i := i.begin endif 3) while i.next 6=prázdné a i.key 6= x do j := i, i := i.next enddo 4) if i.key = x then if i = j.begin then j.begin := i.key :=prázdné else j.next := i.next, i.key := i.next :=prázdné endif endif

12

Insert(x): 1) Spoˇc´ıtáme i := h(x), 2) if i.begin =prázdné then goto 5) endif 3) while i.next 6=prázdné a i.key 6= x do i := i.next enddo 4) if neexistuje prázdn´ y ˇrádek tabulky then pˇreplnˇen´ı else nechˇt j je voln´ y ˇrádek tabulky i.next := j, j.key := x, stop endif 5) if i.key =prázdné then i.key := x, i.begin := i else if neexistuje prázdn´ y ˇrádek tabulky then pˇreplnˇen´ı ˇ else necht j je voln´ y ˇrádek tabulky j.key = x, i.begin := j endif endif V pˇr´ıkladu provedeme Insert(28), nov´ y ˇrádek je 4. ˇrádek – v´ ysledná haˇsovac´ı tabulka ˇrádek P(0) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9)

key

next

1

9

1

73 28 161 7 53 11 141

7

3

5 8

begin

6 4

Algoritmus pˇri práci s poloˇzkami je rychlejˇs´ı neˇz pˇri haˇsován´ı s pˇrem´ısˇtován´ım, ale zaˇc´ atek ˇretˇezce v jiném m´ıstˇe tabulky pˇridává jeden test. V´ ysledek bez odvozován´ı: Oˇcekávan´ y poˇcet porovnán´ı: α2 α u ´spˇeˇsn´ y pˇr´ıpad: 1 + (n−1)(n−2) + n−1 6m2 2m ≈ 1 + 6 + 2 2 ne´ uspˇeˇsn´ y pˇr´ıpad: ≈ 1 + α2 + α + e−α (2 + α) − 2

Sr˚ ustaj´ıc´ı haˇsov´ an´ı Sr˚ ustaj´ıc´ı haˇsován´ı se dˇel´ı podle práce s pamˇet´ı na standardn´ı a na sr˚ ustaj´ıc´ı haˇsov´ an´ı s pomocnou pamˇet´ı (budeme naz´ yvat jen sr˚ ustaj´ıc´ı haˇsován´ı) a podle zp˚ usobu pˇrid´ av´ an´ı dalˇs´ıho prvku. Pop´ıˇseme metody: Standardn´ı sr˚ ustaj´ıc´ı haˇsován´ı: LISCH, EISCH Sr˚ ustaj´ıc´ı haˇsován´ı: LICH, VICH, EICH Vˇsechny metody pro práci s tabulkou pouˇz´ıvaj´ı jen poloˇzku next – ˇc´ıslo ˇrádku tabulky obsahuj´ıc´ı následuj´ıc´ı poloˇzku.

13

Základn´ı idea: ˇretˇezec zaˇc´ıná na svém m´ıstˇe (jako v haˇsován´ı s pˇrem´ısˇtovan´ım), pokud uˇz tam byl uloˇzen nˇejak´ yu ´daj, pak ˇretˇezec tohoto u ´daje sroste s ˇretˇezcem zaˇc´ınaj´ıc´ım na tomto ˇrádku.

Metody EISCH a LISCH EISCH – early-insertion standard coalesced hashing LISCH – late-insertion standard coalesced hashing Organizace tabulky je stejná jako v pˇredchoz´ıch pˇr´ıpadech. Základn´ı idee: LISCH pˇridává nov´ y prvek na konec ˇretˇezce, EISCH pˇridává nov´ y prvek x do ˇretˇezce za ˇrádlem h(x). Pˇr´ıklad: U = {1, 2, . . . , 1000}, h(x) = x mod 10 mnoˇzina S = {1, 7, 11, 53, 73, 141, 171} je uloˇzena v haˇsovac´ı tabulce ˇrádek P(0) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9)

key

next

1

9

73

6

7 53 161 11 141

5 7 8

Tabulka pro metodu LISCH vznikla následuj´ıc´ı posloupnost´ı operac´ı: INSERT(1), INSERT(141), INSERT(11), INSERT(73), INSERT(53), INSERT(161), INSERT(7). Pro metodu EISCH tabulka vznikla následuj´ıc´ı posloupnost´ı operac´ı: INSERT(1), INSERT(161), INSERT(11), INSERT(73), INSERT(53), INSERT(7), INSERT(141). Provedeme INSERT(28), pˇridáváme do ˇcvrtého rádku v´ ysledná tabulka vlevo je pro metodu LISCH vpravo pro metodu EISCH. ˇrádek P(0) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9)

key

next

1

9

73 28 7 53 161 11 141

6 4 5 7 8

ˇrádek P(0) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9)

key

next

1

9

73 28 7 53 161 11 141

6 7

5 4 8

14

Algoritmus operace MEMBER je pro obˇe metody stejn´ y. MEMBER(x): 1) Spoˇc´ıtáme i := h(x), 2) while i.next 6=prázdné a i.key 6= x do i := i.next enddo 3) if i.key = x then x ∈ S else x ∈ / S endif Metoda LISCH – INSERT(x): 1) Spoˇc´ıtáme i := h(x), 2) while i.next 6=prázdné a i.key 6= x do i := i.next enddo 3) if i.key 6= x then if neexistuje prázdn´ y ˇrádek tabulky then pˇreplnˇen´ı else nechˇt j je prázdn´ y ˇrádek j.key := x, i.next := j endif Metoda EISCH – Insert(x): 1) Spoˇc´ıtáme k := i := h(x), 2) while i.next 6=prázdné a i.key 6= x do i := i.next enddo 3) if neexistuje prázdn´ y ˇrádek tabulky then pˇreplnˇen´ı ˇ else necht j je voln´ y ˇrádek tabulky j.next := k.next, k.next := j, j.key := x endif Efektivn´ı operace DELETE nen´ı známá, ale i primitivn´ı algoritmy pro operaci DELETE maj´ı rozumnou oˇcekávanou ˇcasovou sloˇzitost. Anal´ yza sloˇzitosti tˇechto algoritm˚ u. Popis situace: Uloˇzena mnoˇzina S = {s1 , s2 , . . . , sn } do tabulky velikosti m, je dán prvek sn+1 a máme zjistit, zda sn+1 ∈ S. Oznaˇcme ai = h(si ) pro i = 1, 2, . . . , n + 1, kde h je pouˇzitá haˇsovac´ı funkce. Pˇredpoklad: vˇsechny posloupnosti a1 , a2 , . . . , an+1 jsou stejnˇ e pravdˇ epodobn´ e.

Ne´ uspˇeˇsné vyhled´ aván´ı Oznaˇcen´ı: C(a1 , a2 , . . . , an ; an+1 ) oznaˇcuje poˇcet test˚ u pˇri ne´ uspˇeˇsném hledán´ı adresy an+1 v S. Plat´ı: oˇcekávan´ y poˇcet test˚ u pˇri neuspˇeˇsném vyhledáv´ an´ı v mnoˇzinˇe S je P

C(a1 , a2 , . . . , an ; an+1 ) , mn+1

kde se sˇc´ıtá pˇres vˇsechny posloupnosti a1 , a2 , . . . , an – a tˇech je mn+1 . ˇ ezec délky l v mnoˇzinˇe S je maximáln´ı posloupnost adres (b1 , b2 , . . . , bl ) takov´ Retˇ a, ˇze bi .next = bi+1 pro i = 1, 2, . . . , l−1. Kdyˇz adresa an+1 je i-t´ y prvek v ˇretˇezci, pak poˇcet test˚ u P l ˇ je l − i + 1. Retˇezec délky l pˇrispˇel k souˇctu C(a1 , a2 , . . . , an ; an+1 ) 1 + 2 + · · · + l = l + 2 testy.

15

cn (l) – poˇcet vˇsech ˇretˇezc˚ u délky l ve vˇsech reprezentac´ıch n-prvkov´ ych mnoˇzin (ztotoˇzn ˇujeme dvˇe mnoˇziny, které mˇely stejnou posloupnost adres pˇri ukládan´ı prvk˚ u), pak X

C(a1 , a2 , . . . , an ; an+1 ) =cn (0) +

n X l=1

= cn (0) +

l )cn (l) (l + 2

n X

lcn (l) +

l=1

n X l l=1

2

cn (l).

kde cn (0) je poˇcet prázdn´ ych ˇrádk˚ u ve vˇsech reprezentac´ıch. Reprezentace S má m − n prázdn´ ych ˇrádk˚ u, vˇsech posloupnost´ı n-adres je mn , proto cn (0) = (m − n)mn . Pn

lcn (l) je celková délka vˇsech ˇretˇezc˚ u ve vˇsech tabulkách reprezentuj´ıc´ıch vˇsechny nprvkové mnoˇziny a proto n X lcn (l) = nmn . l=1

l=1

Pn l Spoˇc´ıtáme Sn = ı vztah pro cn (l). Pˇridáváme prvek s l=1 2 cn (l). Nejprve rekurentn´ adresou an+1 . Pak ˇretˇezec délky l v reprezentaci S z˚ ustal stejn´ y, kdyˇz adresa an+1 neleˇzela v tomto ˇretˇezci, v opaˇcném pˇr´ıpadˇe se délka ˇretˇezce zvˇetˇsila na l + 1. Proto pˇridán´ı jednoho prvku vytvoˇrilo z ˇretˇezce délky l celkem m−l ˇretˇezc˚ u délky a l ˇretˇezc˚ u délky l+1. Vysˇc´ıt´ an´ım pˇres vˇsechny n-prvkové posloupnosti adres), dostáváme cn+1 (l) = (m − l)cn (l) + (l − 1)cn (l − 1). Odtud n n X X l l l (l − 1)cn−1 (l − 1) = (m − l)cn−1 (l) + cn (l) = Sn = 2 2 2 l=1 l=1 n−1 n X l + 1 X n l (m − n)cn−1 (n)+ lcn−1 (l) = (m − l)cn−1 (l) + 2 2 2 l=0 l=1 n−1 X l 1 l+1 0cn−1 (0) = l)cn−1 (l) + (m − l) + ( 2 2 2 l=1 n−1 n−1 X X l (m + 2)cn−1 (l) + lcn−1 (l) 2 l=1

l=1 n−1

= (m + 2)Sn−1 + (n − 1)m

,

16

kde jsme pouˇzili, ˇze cn−1 (n) = 0, a identitu 1 l+1 l = (l2 m − lm − l3 + l2 + l3 + l2 ) = +l (m − l) 2 2 2 1 2 1 (l m − lm + 2l2 ) = (l2 m − lm + 2(l2 − l)) + l = 2 2 l + l. (m + 2) 2 Rekurence pro Sn dává Sn =(m + 2)Sn−1 + (n − 1)mn−1 = (m + 2)2 Sn−2 + (m + 2)(n − 2)mn−2 + (n − 1)mn−1 = (m + 2)3 Sn−3 + (m + 2)2 (n − 3)mn−3 + (m + 2)(n − 2)mn−2 + (n − 1)mn−1 = (m + 2)

n−1

S0 +

n−1 X

(m + 2)i (n − 1 − i)mn−1−i =

i=0

(m + 2)n−1 = (m + 2)

n−1 X

(n − 1 − i)

i=0 n−1 X n−1

i

i=1

m n−1−i m+2

m i , m+2

kde jsme ˇze S0 = 0. Spoˇc´ıtáme souˇcet Tcn = Pnvyuˇzili, n i+1 cTc = i=1 ic plyne (c − 1)Tcn =cTcn − Tcn = ncn+1 + ncn+1 −

n+1 X

(i − 1)ci −

−ci − c =

ci = ncn+1 −

i=1

i=1

ici pro n = 1, 2, . . . a c 6= 1. Z

ici = ncn+1 +

i=1

i=2 n X

i=2 n X

n X

Pn

n X i=2

((i − 1)ci − ici ) − c =

cn+1 − c ncn+2 − (n + 1)cn+1 + c = . c−1 c−1

Tedy plat´ı Tcn = m m+2

ncn+2 − (n + 1)cn+1 + c . (c − 1)2

6= 1, dostáváme, ˇze n+1 n m m m (n − 1) m+2 − n m+2 + m+2 n−1 Sn =(m + 2) = 2 m m+2 − 1 1 m m n m n+1 −n + = (m + 2)n+1 (n − 1) 4 m+2 m+2 m+2 1 1 (n − 1)mn+1 − n(m + 2)mn + m(m + 2)n = m(m + 2)n − mn+1 − 2nmn . 4 4

Protoˇze

17

Oˇcekávan´ y poˇcet test˚ u pˇri ne´ uspˇeˇsném vyhledáván´ı je (m − n)mn + nmn +

1 4

m(m + 2)n − mn+1 − 2nmn = mn+1 mn+1 + 41 m(m + 2)n − mn+1 − 2nmn = mn+1 2 1 1 2n ∼ 1 + (e2α − 1 − 2α), 1 + (1 + )n − 1 − 4 m m 4 Tento odhad je stejn´ y pro obˇe metody – LISCH i EISCH, protoˇze maj´ı stejné posloupnosti adres (liˇs´ı se jen poˇrad´ım prvk˚ u v jednotliv´ ych ˇretˇezc´ıch).

´ eˇsn´ Uspˇ y pˇr´ıpad Oˇcekávan´ y poˇcet test˚ u pˇri u ´spˇeˇsném vyhledáván´ı v modelu LISCH spoˇc´ıtáme stejnou metodou jako pro haˇsován´ı se separuj´ıc´ımi ˇretˇezci. Pro vyhledán´ı prvku sn+1 ∈ S je poˇcet test˚ u roven 1+poˇcet porovnán´ı kl´ıˇc˚ u pˇri operaci INSERT(sn+1 ). Kdyˇz sn+1 je vloˇzen na m´ısto h(sn+1 ), nebyl porovnáván ˇzádn´ y kl´ıˇc a test bude 1, kdyˇz h(sn+1 ) byl na na i-tém m´ıstˇe v ˇ ˇretˇezci délky l, pak bylo pˇri operaci INSERT(sn+1 ) pouˇzito l − i + 1 porovnán´ı kl´ıˇc˚ u a ted se pouˇzije l − i + 2 test˚ u. Oˇcekávan´ y poˇcet porovnán´ı kl´ıˇc˚ u pˇri ne´ uspˇeˇsném vyhledáv´ an´ı je n 1 1 l 1 X )cn (l)) = n+1 (nmn + m(m + 2)n − mn+1 − 2nmn ) = ( (l + n+1 2 m m 4 l=1

1 2 2n (1 + )n − 1 + . 4 m m

Tedy oˇcekávan´ y poˇcet test˚ u pˇri u ´spˇeˇsném vyhled´ aván´ı v n-prvkové mnoˇzinˇe je podle pˇredchoz´ı anal´ yzy roven 1+ n-tina souˇctu oˇcekávaného poˇctu porovnán´ı kl´ıˇc˚ u pˇri ne´ uspˇeˇsném vyhledáván´ı v i-prvkové mnoˇzinˇe, kde i prob´ıhá ˇc´ısla 0, 1, . . . , n − 1. Podle pˇredchoz´ıch v´ ysledk˚ u je hledan´ y souˇcet n−1 n 2 n X 1 ) −1 n 2 i 2i 1 (1 + m 2 (1 + ) − 1 + = − + = 2 4 m m 4 1+ m 4 2m −1 i=0 m 2 2n n2 − n (1 + )n − 1 − + . 8 m m 4m

Tedy oˇcekávan´ y poˇcet test˚ uvu ´spˇeˇsném pˇr´ıpadˇe pro n-prvkovou mnoˇzinu je 1+

m 2 2n n − 1 1 2α α (1 + )n − 1 − + ∼1+ (e − 1 − 2α) + . 8n m m 4m 8α 4

Pro metodu EISCH je oˇcekáván´ y poˇcet test˚ uvu ´spˇeˇsném pˇr´ıpadˇe 1 1 m (1 + )n − 1 ∼ (eα − 1). n m α

1 ). Mus´ı se pouˇz´ıt sloˇzitˇejˇs´ı metoda. Chyba aproximace pro tyto odhady je O( m

18

Pˇredn´ aˇska 3 Metody LICH, EICH, VICH LICH – late-insertion coalesced hashing EICH – early-insertion coalesced hashing VICH – varied-insertion coalesced hashing Základn´ı idea: Metody pouˇz´ıvaj´ı pomocnou pamˇeˇt. Tabulka je rozdˇelená na adresovac´ı ˇc´ ast ˇ a na pomocnou pamˇet, která nen´ı dostupná pomoc´ı haˇsovac´ı funkce, ale pomáhá pˇri ˇreˇsen´ı koliz´ı. Metody se liˇs´ı operac´ı INSERT. Vˇsechny metody pˇri kolizi nejprve pouˇzij´ı ˇr´ adek tabulky z pomocné ˇcásti a teprve, kdyˇz je pomocná ˇcást zaplnˇena, pouˇz´ıvaj´ı adresovac´ı ˇc´ ast. Metoda LICH: pˇri INSERTu vkládá prvek vˇzdy na konec ˇretˇezce. Metoda EICH: pˇri INSERTu vkládá prvek x do ˇretˇezce vˇzdy na m´ısto hned za ˇr´ adkem h(x). Metoda VICH: Pˇri INSERTu, kdyˇz nov´ y ˇrádek je z pomocné ˇcásti, tak je vloˇzen s nov´ ym prvkem na konec ˇretˇezce, kdyˇz je pomocná ˇcást pamˇeti vyˇcerpána, tak se ˇrádek s nov´ ym prvkem vkládá do ˇretˇezce za posledn´ı ˇrádek z pomocné ˇcásti tabulky. Idea: pomocn´ a ˇcást má zabránit rychlému sr˚ ustán´ı ˇretˇezc˚ u. Tyto metody nepodporuj´ı pˇrirozené efektivn´ı algoritmy pro operaci DELETE. Pˇr´ıklad: U = {1, 2, . . . , 1000}, h(x) = x mod 10, S = {1, 7, 11, 53, 73, 141, 161}. Tabulka má 12 ˇrádk˚ u a má tvar ˇrádek P(0) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9) P(10) P(11)

key

next

1

10

73

11

7 161 11

5 7

141 53

8

Haˇsovac´ı tabulka vznikla posloupnostmi operac´ı: Pro metodu LICH: INSERT(1), INSERT(73), INSERT(141), INSERT(53), INSERT(11), INSERT(161), INSERT(7).

19

Pro metodu EICH: INSERT(1), INSERT(73), INSERT(161), INSERT(53), INSERT(11), INSERT(141), INSERT(7) ale nedodrˇzovalo se, ˇze se nejdˇr´ıv dávaj´ı ˇrádky z pomocné ˇcásti. Pˇri dodrˇzován´ı tohoto pravidla tabulka nem˚ uˇze vzniknout. Pro metodu VICH: INSERT(1), INSERT(73), INSERT(141), INSERT(53), INSERT(161), INSERT(11), INSERT(7). Aplikujeme operace INSERT(28) 2a INSERT(31), nové ˇrádky budou ˇrádky ˇc´ıslo 4 a 9. Tabulka vytvoˇrená pomoc´ı metody LICH je na levé stranˇe, metodou VICH je v prostˇredku a metodou EICH je na pravé stranˇe. ˇrádek P(0) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9) P(10) P(11)

key

next

1

10

73 28 7

11 9 4

161 11 31 141 53

5 7 8

ˇrádek P(0) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9) P(10) P(11)

key

next

1

10

73 28 7

11 7

161 11 31 141 53

5 4 8 9

ˇrádek P(0) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9) P(10) P(11)

key

next

1

9

73 28 7

11 7

161 11 31 141 53

5 4 10 8

Algoritmus operace MEMBER je pro tyto metody stejn´ y jako pro LISCH a EISCH MEMBER(x): 1) Spoˇc´ıtáme i := h(x), 2) while i.next 6=prázdné a i.key 6= x do i := i.next enddo 3) if i.key = x then x ∈ S else x ∈ / S endif Algoritmus operace INSERT je pro metodu LICH stejn´ y jako pro metodu LISCH a pro metodu EICH je stejn´ y jako pro metodu EISCH s jedin´ ym doplˇ nkem, pokud existuje pr´ azdn´ y ˇrádek v pomocné ˇcásti, tak j-t´ y ˇrádek je z pomocné ˇcásti. Tento pˇredpoklad je i pro algoritmus INSERT pro metodu VICH.

20

Metoda LICH – INSERT(x): 1) Spoˇc´ıtáme i := h(x), 2) while i.next 6=prázdné a i.key 6= x do i := i.next enddo 3) if i.key 6= x then if neexistuje prázdn´ y ˇrádek tabulky then pˇreplnˇen´ı else nechˇt j je prázdn´ y ˇrádek, j.key := x, i.next := j endif Metoda EICH – Insert(x): 1) Spoˇc´ıtáme k := i := h(x), 2) while i.next 6=prázdné a i.key 6= x do i := i.next enddo 3) if neexistuje prázdn´ y ˇrádek tabulky then pˇreplnˇen´ı ˇ else necht j je voln´ y ˇrádek tabulky j.next := k.next, k.next := j, j.key := x endif Metoda VICH – INSERT(x) 1) Spoˇc´ıtáme k := i := h(x); 2) while i.next 6=prázdné a i.key 6= x do if i ≥ m (je v pomocné ˇcásti) a i.next < m (nen´ı v pomocné ˇcásti) then k := i endif i := i.next enddo 3) if i.key 6= x then if neexistuje prázdn´ y ˇrádek then pˇreplnˇen´ı else if j ≥ m (tj. j je v pomocné ˇcásti) then i.next := j else j.next:=k.next, k.next:=j endif j.key := x endif endif Sloˇzitost algoritm˚ u pro sr˚ ustaj´ıc´ı haˇsován´ı. Znaˇcen´ı: n – velikost uloˇzené mnoˇziny, m – velikost adresovac´ı ˇcásti tabulky, m′ – velikost tabulky, α = mn′ – faktor zaplnˇen´ı, m ı faktor, β=m ′ – adresovac´ λ – jediné nezáporné ˇreˇsen´ı rovnice e−λ + λ =

1 β.

21

Oˇcekávan´ y poˇcet test˚ u pro metodu LICH α ne´ uspˇeˇsn´ y pˇr´ıpad: e− β + α z α ≤ λβ, β , kdyˇ α

+ 14 (e2( β −λ) − 1)(3 − β2 + 2λ) − 21 ( α − λ), kdyˇz α ≥ λβ β α u ´spˇeˇsn´ y pˇr´ıpad: 1 + 2β , kdyˇz α ≤ λβ, 1 β

1+

α β (e2( β −λ) 8α

− 1 − 2( α − λ))(3 − β

2 β

+ 2λ) + 41 ( α + λ) + λ4 (1 − β

λβ ), α

kdyˇz α ≥ λβ.

Oˇcekávan´ y poˇcet test˚ u pro metodu EICH −α z α ≤ λβ, ne´ uspˇeˇsn´ y pˇr´ıpad: e β + α β , kdyˇ α

α

1 e2( β −λ) ( 43 + λ2 − 2β ) + e β −λ ( β1 − 1) + ( 14 − α u ´spˇeˇsn´ y pˇr´ıpad: 1 + 2β , kdyˇz α ≤ λβ,

1+

α 2β

α

α 2β

β +α ((e β −λ − 1)(1 + λ) − ( α − λ))(1 + β

+ λ 2

1 2β ),

+

kdyˇz α ≥ λβ

α )), 2β

kdyˇz α ≥ λβ.

Oˇcekávan´ y poˇcet test˚ u pro metodu VICH −α ne´ uspˇeˇsn´ y pˇr´ıpad: e β + α , kdyˇz α ≤ λβ, β α

+ 14 (e2( β −λ) − 1)(3 − β2 + 2λ) − 21 ( α z α ≥ λβ β − λ), kdyˇ α , kdyˇz α ≤ λβ, u ´spˇeˇsn´ y pˇr´ıpad: 1 + 2β 1 β

α

α

β 1−β α α λ α β −λ + 1), kdyˇ 1 + 2β +α ((e β −λ − 1)(1 + λ) − ( α z α ≥ λβ. β − λ))(1 + 2 + 2β )) + α ( β − λ − e ′

Chyba aproximace pro tyto odhady je O(log √mm′ ).

Haˇsov´ an´ı s lineárn´ım pˇrid´ aván´ım Tabulka má jedinou poloˇzku – key Základn´ı idea: Pˇri operaci INSERT(x) vloˇz´ıme x na ˇrádek h(x), kdyˇz je prázdn´ y, v opaˇcném pˇr´ıpadˇe nalezneme nejmenˇs´ı i takové, ˇze ˇrádek h(x) + i mod m je prázdn´ y, a tam vloˇz´ıme x. Komentáˇr: Metoda vyˇzaduje minimáln´ı velikost pamˇeti. V tabulce se vytváˇrej´ı shluky pouˇzit´ ych ˇrádk˚ u, a proto pˇri velkém zaplnˇen´ı metoda vyˇzaduje velké mnoˇzstv´ı ˇcasu. Metoda nepodporuje efektivn´ı implementaci operace DELETE. Pro zjiˇstˇen´ı pˇreplnˇen´ı je vhodné m´ıt uloˇzen poˇcet vyplnˇen´ ych ˇrádk˚ u a testovat, zda nevyˇsetˇrujeme podruhé prvn´ı vyˇsetˇrovan´ y ˇrádek.

22

MEMBER(x): 1) Spoˇc´ıtáme i := h(x); 2) if poˇcet zaplnˇen´ ych ˇrádk˚ u je menˇs´ı neˇz m then while i.key 6=prázdn´ y a i.key 6= x do i := i + 1 mod m enddo else j := i, while i 6= j a i.key 6= x do i := i + 1 mod m enddo endif 3) if i.key = x then x ∈ S else x ∈ / S endif INSERT(x): 1) Spoˇc´ıtáme i := h(x); 2) if poˇcet zaplnˇen´ ych ˇrádk˚ u je menˇs´ı neˇz m then while i.key 6=prázdn´ y a i.key 6= x do i := i + 1 mod m enddo else j := i, while i 6= j a i.key 6= x do i := i + 1 mod m enddo if i = j then pˇreplnˇen´ı, stop endif endif 3) if i.key =prázdn´ y then i.key := x, poˇcet zaplnˇen´ ych ˇrádk˚ u zvˇetˇsit o 1 endif Pˇr´ıklad: Máme universum U = {1, 2, . . . , 1000}, haˇsovac´ı funkci h(x) = x mod 10 a mnoˇzinu S = {1, 7, 11, 53, 73, 141, 161}. Tato mnoˇzina je uloˇzena v levé tabulce. Provedeme operaci INSERT(35). V´ ysledek je uloˇzen v pravé tabulce. ˇrádek key P(0) P(1) 1 P(2) 11 P(3) 73 P(4) 141 P(5) 161 P(6) 53 P(7) 7 P(8) P(9)

ˇrádek key P(0) P(1) 1 P(2) 11 P(3) 73 P(4) 141 P(5) 161 P(6) 53 P(7) 7 P(8) 35 P(9)

Tabulka vznikla posloupnost´ı operac´ı: INSERT(1), INSERT(11), INSERT(73), INSERT(141), INSERT(161), INSERT(53), INSERT(7). Na závˇer uvedeme sloˇzitost této metody. Oˇcekávan´ y poˇcet test˚ u: 2 1 1 Ne´ uspˇeˇsn´ y pˇr´ıpad: ≈ 2 (1 + 1−α ), 1 ´ eˇsn´ Uspˇ y pˇr´ıpad: ≈ 12 (1 + 1−α ).

23

Dvojité haˇsov´ an´ı Základn´ı nev´ yhoda pˇredchoz´ı metody je zp˚ usob v´ ybˇeru dalˇs´ıho ˇrádku. Je velmi determinován a d˚ usledkem je vznik shluku ˇrádk˚ u, kter´ y vede k v´ yraznému zpomalen´ı metody. Idea jak odstranit tuto nev´ yhodu: Pouˇzijeme dvˇe haˇsovac´ı funkce h1 a h2 a pˇri operaci INSERT(x) nalezneme nejmenˇs´ı i = 0, 1, . . . takové, ˇze (h1 (x)+ih2 (x)) mod m je pr´ azdn´ y ˇrádek, a tam uloˇz´ıme prvek x. Tabulka má jedinou poloˇzku – key. Poˇzadavky na korektnost: Pro kaˇzdé x mus´ı b´ yt h2 (x) a m nesoudˇelné (jinak prvek x nem˚ uˇze b´ yt uloˇzen na libovolném ˇrádku tabulky). m−1 Pˇredpoklad pro v´ ypoˇcet oˇcekavaného poˇctu test˚ u: posloupnost {h1 (x) + ih2 (x)}i=0 je náhodná permutace mnoˇziny ˇrádk˚ u tabulky. Nev´ yhoda: Uvedená metoda nepodporuje operaci DELETE. Pˇreplnˇen´ı se ˇreˇs´ı stejn´ ym zp˚ usobem jako v metodˇe haˇsován´ı s lineárn´ım pˇridáván´ım. Poznámka: Metoda haˇsován´ı s lineárn´ım pˇridáván´ım je speciáln´ı pˇr´ıpad dvojitého haˇsov´ an´ı, kde h2 (x) = 1 pro kaˇzdé x ∈ U . MEMBER(x): 1) Spoˇc´ıtáme i := h1 (x) a h2 (x); 2) if poˇcet zaplnˇen´ ych ˇrádk˚ u je menˇs´ı neˇz m then while i.key 6=prázdn´ y a i.key 6= x do i := i + h2 (x) mod m enddo else j := i, while i 6= j a i.key 6= x do i := i + h2 (x) mod m enddo endif 3) if i.key = x then x ∈ S else x ∈ / S endif INSERT(x): 1) Spoˇc´ıtáme i := h1 (x) a h2 (x); 2) if poˇcet zaplnˇen´ ych ˇrádk˚ u je menˇs´ı neˇz m then while i.key 6=prázdn´ y a i.key 6= x do i := i + h2 (x) mod m enddo else j := i, while i 6= j a i.key 6= x do i := i + h2 (x) mod m enddo if i = j then pˇreplnˇen´ı, stop endif endif 3) if i.key =prázdn´ y then i.key := x, poˇcet zaplnˇen´ ych ˇrádk˚ u zvˇetˇsit o 1 endif Pˇr´ıklad: Mˇejme universum U = {1, 2, . . . , 1000}. Haˇsovac´ı funkce jsou h1 (x) = x mod 10 a h2 (x) = 1 + 2(x mod 4), kdyˇz x mod 4 ∈ {0, 1}, h2 (x) = 3 + 2(x mod 4), kdyˇz x mod 4 ∈ {2, 3}. Mnoˇzina je S = {1, 7, 11, 53, 73, 141, 161}. Tato mnoˇzina je uloˇzena v levé tabulce. Aplikujme INSERT(35). Pak h2 (35) = 9, tedy posloupnost pro x = 35 je (5, 4, 3, 2, 1, 0, 9, 8, 7, 6). V´ ysledek je uloˇzen v pravé tabulce, která vznikla posloupnost´ı operac´ı:

24

INSERRT(1), INSERT(73), INSERT(53), INSERT(141), INSERT(161), INSERT(11), INSERT(7). ˇrádek key P(0) 11 P(1) 1 P(2) P(3) 73 P(4) 141 P(5) 7 P(6) 53 P(7) 161 P(8) P(9)

ˇrádek key P(0) 11 P(1) 1 P(2) 35 P(3) 73 P(4) 141 P(5) 7 P(6) 53 P(7) 161 P(8) P(9)

Anal´ yza vyhledáván´ı v dvojitém haˇsován´ı. Ne´ uspˇeˇsn´ y pˇr´ıpad: Znaˇcen´ı: qi (n, m) – kdyˇz tabulka má m ˇrádk˚ u a je v n´ı obsazeno n ˇrádk˚ u, tak je to pravdˇepodobnost, ˇze za pro kaˇzdé j = 0, 1, . . . , i − 1 je ˇrádek h1 (x) + jh2 (x) obsazen. n(n−1) n Pak q0 (n, m) = 1, q1 (n, m) = m , q2 (n, m) = m(m−1) a obecnˇe Qi−1

j=0 (n

qi (n, m) = Qi−1

− j)

j=0 (m − j)

.

C(n, m) – oˇcekávan´ y poˇcet test˚ u v ne´ uspˇeˇsném vyhledáv´ an´ı, kdyˇz tabulka má m ˇrádk˚ uan jich je obsazeno. Podle definice plat´ı: C(n, m) =

n X

(j + 1)(qj (n, m) − qj+1 (n, m)) =

qj (n, m).

j=0

j=0

Dále plat´ı C(0, m) = 1 pro kaˇzdé m a qj (n, m) = a m > 1. Odtud

n X

n m qj−1 (n

− 1, m − 1) pro vˇsechna j, n > 0

n X

n−1 n X n C(n, m) = qj (n, m) = 1 + ( qj (n − 1, m − 1) = 1 + C(n − 1, m − 1). m j=0 m j=0 m+1 m+1 . Kdyˇz n = 0, pak C(0, m) = m−0+1 = 1 a tvrzen´ı Indukc´ı ukáˇzeme, ˇze C(n, m) = m−n+1 plat´ı. Pˇredpokládáme, ˇze plat´ı pro n − 1 ≥ 0 a pro kaˇzdé m ≥ n − 1 a dokáˇzeme tvrzen´ı pro n. Plat´ı

n n((m − 1) + 1) C(n − 1, m − 1) = 1 + = m m((m − 1) − (n − 1) + 1) m+1 n = . 1+ m−n+1 m−n+1

C(n, m) =1 +

25

Oˇcekávan´ y poˇcet dotaz˚ u pˇri ne´ uspˇeˇsném vyhledáván´ı v tabulce s m ˇrádky, z nichˇz n je m+1 . obsazeno, je m−n+1 ´ eˇsn´ Uspˇ y pˇr´ıpad. Pouˇzijeme metodu ze separuj´ıc´ıch ˇretˇezc˚ u. Poˇcet dotaz˚ u pˇri vyhledáván´ı x pro x ∈ S je stejn´ y jako byl poˇcet dotaz˚ u pˇri vkládán´ı x do tabulky. Tedy oˇcekávan´ y poˇcet dotaz˚ u pˇri u ´spˇeˇsném vyhledáván´ı v tabulce s m ˇrádky, z nichˇz n je obsazeno, je n−1 n−1 m+1 m−n+1 X 1 1X 1 X m+1 m+1 X 1 C(i, m) = ≈ = − n i=0 n i=0 m − n + 1 n j j j=1 j=1

m+1 1 1 1 ln( ) ≈ ln( ). α m−n+1 α 1−α

Následuj´ıc´ı tabulka ukazuje tyto hodnoty v závislosti na velikosti α. hodnota α 1 α

1 1−α

1 ln( 1−α )

0.5 2 1.38

0.7 3.3 1.70

0.9 10 2.55

0.95 20 3.15

0.99 100 4.65

0.999 1000 6.9

Porovn´ an´ı efektivity Poˇrad´ı metod haˇsován´ı podle oˇcekávaného poˇctu test˚ u: Ne´ uspˇeˇsné vyhledáván´ı: Haˇsován´ı s uspoˇrádan´ ymi ˇretˇezci, Haˇsovan´ı s ˇretˇezci=Haˇsován´ı s pˇrem´ısˇtován´ım, Haˇsován´ı s dvˇema ukazateli, VICH=LICH, EICH, LISCH=EISCH, Dvojité haˇsov án´ı, Haˇsován´ı s lineárn´ım pˇridáván´ım. ´ eˇsné vyhledáván´ı: Uspˇ Haˇsován´ı s uspoˇrádan´ ymi ˇretˇezci=Haˇsován´ı s ˇretˇezci=Haˇsován´ı s pˇrem´ısˇtován´ım, Haˇsován´ı s dvˇema ukazateli, VICH, LICH, EICH, EISCH, LISCH, Dvojité haˇsován´ı, Haˇsován´ı s lineárn´ım pˇridáván´ım. Poznámka: Metoda VICH pˇri ne´ uspˇeˇsném vyhledáván´ı pro α < 0.72 a pˇri u ´spˇeˇsném vyhledáván´ı pro α < 0.92 vyˇzaduje menˇs´ı oˇcekávan´ y poˇcet test˚ u neˇz metoda s dvˇema ukazateli. Pˇri ne´ uspˇeˇsném vyhledáván´ı má VICH a LICH stejnou sloˇzitost a je o 8% lepˇs´ı neˇz EICH a o 15% neˇz LISCH a EISCH, které maj´ı stejnou sloˇzitost. Pˇri u ´spˇeˇsném vyhledáv´ an´ı je VICH nepatrnˇe lepˇs´ı neˇz LICH a EICH o 3% lepˇs´ı neˇz EISCH a o 7% lepˇs´ı neˇz LISCH.

26

Oˇcekávan´ y poˇcet test˚ u pˇri u ´plnˇe zaplnˇené tabulce: Metoda s pˇrem´ısˇtován´ım: ne´ uspˇeˇsné vyhledáván´ı 1.5, u ´spˇeˇsné vyhledáván´ı 1.4. Metoda s dvˇema ukazateli: u ´spˇeˇsné i ne´ uspˇeˇsné vyhledáván´ı 1.6. VICH: ne´ uspˇeˇsné vyhledáván´ı 1.79, u ´spˇeˇsné vyhledáván´ı 1.67, LICH: ne´ uspˇeˇsné vyhledáván´ı 1.79, u ´spˇeˇsné vyhledáván´ı 1.69, EICH: ne´ uspˇeˇsné vyhledáván´ı 1.93, u ´spˇeˇsné vyhledáván´ı 1.69, EISCH: ne´ uspˇeˇsné vyhledáván´ı 2.1, u ´spˇeˇsné vyhledáván´ı 1.72, LISCH: ne´ uspˇeˇsné vyhledáván´ı 2.1, u ´spˇeˇsné vyhledáván´ı 1.8. Metodu s lineárn´ım pˇridáván´ım je dobré pouˇz´ıt jen pro α < 0.7, metodu s dvojit´ ym haˇsován´ım pro α < 0.9, pak ˇcas pro ne´ uspˇeˇsné vyhledáván´ı rychle nar˚ ustá. m ri sr˚ ustaj´ıc´ım haˇsován´ı. Vliv β = m ′ pˇ Pˇri u ´spˇeˇsném vyhledáván´ı je optimáln´ı hodnota β = 0.85, pˇri ne´ uspˇeˇsném vyhledáv´ an´ı je optimáln´ı hodnota β = 0.78. V praxi se doporuˇcuje pouˇz´ıt hodnotu β = 0.86 (uvedené v´ ysledky byly pro tuto hodnotu β).

Komentáˇr: Metody se separuj´ıc´ımi ˇretˇezci a sr˚ ustaj´ıc´ı haˇsován´ı pouˇz´ıvaj´ı v´ıce pamˇeti (pˇri sr˚ ustaj´ıc´ım haˇsován´ı souˇcet adresovac´ı a pomocné ˇcásti). Metoda s pˇrem´ısˇtován´ım a metoda dvojitého haˇsován´ı vyˇzaduji v´ıce ˇcasu – na pˇrem´ıstˇen´ı prvku a na v´ ypoˇcet druhé haˇsovac´ı funkce.

Dalˇs´ı otázky

Jak nalézt voln´ y ˇrádek. Za nejlepˇs´ı metodu se povaˇzuje m´ıt seznam (zásobn´ık) voln´ ych ˇrádk˚ u a z jeho kraje br´ at voln´ y ˇrádek a po u ´spˇeˇsné operaci DELETE tam zase ˇrádek vloˇzit (pozor pˇri operaci DELETE ve strukturách které nepodporuj´ı DELETE). Jak ˇreˇsit pˇreplnˇen´ı. Standardn´ı model: Dána základn´ı velikost tabulky m a pracuje se s tabulkami s 2i m ˇr´ adky 1 pro vhodné i = 0, 1, . . . . Vhodné i znamená, ˇze faktor zaplnˇen´ı α je v intervalu < 4 , 1 > (s vyj´ımkou i = 0, kde se uvaˇzuje pouze horn´ı mez). Pˇri pˇrekroˇcen´ı meze se zvˇetˇs´ı nebo zmenˇs´ı i a vˇsechna data se pˇrehaˇsuj´ı do nové tabulky. V´ yhoda: Po pˇrehaˇsován´ı do nové tabulky, poˇcet operac´ı, které vedou k novému pˇrehaˇsov´ aván´ı, je alespoˇ n polovina velikosti uloˇzené mnoˇziny. Praktické pouˇzit´ı: Nedrˇzet se striktnˇe mez´ı, pouˇz´ıvat malé tabulky pˇri pˇreplnˇen´ı a posunout velké pˇrehaˇsován´ı na dobu klidu (aby systém nenechal uˇzivatele v normáln´ı dobˇe ˇcekat). Jak ˇreˇsit DELETE v metodách, které ho nepodporuj´ı. Pouˇz´ıt ideu tzv. ‘faleˇsného DELETE’. Odstranit prvek, ale ˇrádek neuvolnit (i v kl´ıˇci nechat nˇejakou hodnotu, která bude znamenat, ˇze ˇrádek je prázdn´ y, poloˇzky podporuj´ıc´ı pr´ aci s ˇ adek nebude v seznamu voln´ tabulkami nemˇenit). R´ ych ˇrádk˚ u, ale operace INSERT, kdyˇz testuje tento ˇrádek, tak tam m˚ uˇze vloˇzit nov´ y prvek. Kdyˇz je alespoˇ n polovina pouˇzit´ ych ˇrádk˚ u takto blokována, je vhodné celou strukturu pˇrehaˇsovat. Pravdˇepodobnostn´ı anal´ yzu tohoto modelu neznám.

Otevˇren´ y problém

Jak vyuˇz´ıt ideje z haˇsován´ı s uspoˇrádan´ ymi ˇretˇezci pro ostatn´ı metody ˇreˇsen´ı koliz´ı (jmenovitˇe pro sr˚ ustaj´ıc´ı haˇsován´ı.

27

Pˇredn´ aˇska 4 Pˇredpoklady pro uvedenou anal´ yzu haˇsován´ı: 1) Haˇsovac´ı funkce se rychle spoˇc´ıtá (v ˇcase O(1)) 2) Haˇsovac´ı funkce rovnomˇernˇe rozdˇeluje univerzum (to znamená, ˇze pro dvˇe r˚ uzné hodnoty −1 −1 i a j haˇsovac´ı funkce plat´ı −1 ≤ |h (i)| − |h (j)| ≤ 1); 3) Vstupn´ı data jsou rovnomˇernˇe rozdˇelená. Pˇredpoklad 1) je jasn´ y. Pˇredpoklad 2) – je v´ yhodné, kdyˇz rozdˇelen´ı univerza haˇsovac´ı funkc´ı kop´ıruje známé rozdˇelen´ı vstupn´ıch dat. Pouˇzilo se pˇri návrhu pˇrekladaˇce pro FORTRAN (Lum 1971). Porovn´ an´ı v´ ysledku: hodnota α experiment teorie

0.5 1.19 1.25

0.6 1.25 1.30

0.7 1.28 1.35

0.8 1.34 1.40

0.9 1.38 1.45

Pouˇzila se metoda separuj´ıc´ıch ˇretˇezc˚ u. Závˇer: Podm´ınky 1) a 2) m˚ uˇzeme splnit, kdyˇz známe rozloˇzen´ı vstupn´ıch dat, m˚ uˇzeme dosáhnout jeˇstˇe lepˇs´ıch v´ ysledk˚ u. Nev´ yhoda: Rozloˇzen´ı vstupn´ıch dat nem˚ uˇzeme ovlivnit a obvykle ho ani neznáme. Je reálné, ˇze rozdˇelen´ı vstupn´ıch dat bude nevhodné pro pouˇzitou haˇsovac´ı funkci. D˚ usledek – na poˇcátku 70. let se zaˇcalo ustupovat od haˇsován´ı.

Univerzáln´ı haˇsov´ an´ı Tuto metodu navrhli Carter a Wegman (1977), aby obeˇsli poˇzadavek 3). To vedlo k novému rozsáhlému pouˇz´ıván´ı haˇsován´ı. Základn´ı idea: M´ısto jedné funkce máme mnoˇzinu H funkc´ı z univerza do tabulky velikosti m takov´ ych, ˇze pro kaˇzdou mnoˇzinu S ⊆ U , |S| ≤ m se vˇetˇsina funkc´ı chová dobˇre v˚ uˇci S (tj. S splˇ nuje poˇzdavek 3)). Haˇsovac´ı funkci zvol´ıme náhodnˇe z H (s rovnomˇern´ ym rozdˇelen´ım) a haˇsujeme pomoc´ı takto zvolené funkce. Formálnˇe: Nechˇt U je univerzum. Mnoˇzina funkc´ı H z univerza U do mnoˇziny {0, 1, . . . , m− 1} se naz´ yvá c-univerzáln´ı, (c je kladné reálné ˇc´ıslo), kdyˇz ∀x, y ∈ U, x 6= y plat´ı |{f ∈ H | f (x) = f (y)}| ≤

c|H| . m

Problémy: existence c-univerzáln´ıch systém˚ u, vlastnosti c-univerzáln´ıch systém˚ u (zda splˇ nuj´ı poˇzadované ideje).

Existence univerzáln´ıch systém˚ u Univerzum U = {0, 1, . . . , N − 1} pro prvoˇc´ıslo N , H = {ha,b | a, b ∈ U }, kde ha,b (x) = ((ax + b) mod N ) mod m V´ yhoda: funkce z mnoˇziny H um´ıme rychle vyˇc´ıslit. Zvolme x, y ∈ U taková, ˇze x 6= y. Chceme nalézt a, b z U tak, ˇze ha,b (x) = ha,b (y).

28 N ⌉ − 1} tak, ˇze plat´ı Mus´ı existovat i ∈ {0, 1, . . . , m − 1} a r, s ∈ {0, 1, . . . , ⌈ m

(ax + b ≡ i + rm) mod N (ay + b ≡ i + sm) mod N Kdyˇz x, y, i, r a s jsou konstanty a a a b jsou promˇenné, je to systém lineárn´ıch rovnic v tˇelese Z/ mod N , kde Z jsou celá ˇc´ısla. Matice soustavy je

x 1 y 1

a je regulárn´ı, protoˇze x 6= y. Tedy existuje jediné ˇreˇsen´ı této soustavy pro fixovaná x, y, i, r a s. Pro dané x a y, i nab´ yvá m hodnot, r a s nab´ yvaj´ı ⌈ N m ⌉ hodnot. 2 Závˇer: pro kaˇzd´ a x, y ∈ U taková, ˇze x 6= y, existuje m ⌈ N ⌉ dvojic a, b takov´ ych, ˇze m a, b ∈ U a ha,b (x) = ha,b (y). Velikost H. Mˇejme a, b, a′ , b′ ∈ U . Protoˇze ha,b (0) = b a ha′ ,b′ (0) = b′ , dostáváme, ˇze b 6= b′ implikuje ha,b 6= ha′ ,b′ . Kdyˇz b = b′ , pak ha,b (1) = a + b a ha′ ,b (1) = a′ + b. Tedy a 6= a′ implikuje ha,b 6= ha′ ,b . Odtud (a, b) 6= (a′ , b′ ) implikuje, ˇze ha,b 6= ha′ ,b′ . Proto |H| = N 2 . Vˇ eta. Mnoˇzina H je c-univerz´ aln´ı pro 2 ⌈N m⌉ c= . N 2 m

Skuteˇcnˇe, pro kaˇzdé x, y ∈ U , x 6= y, je poˇcet a, b ∈ U takov´ ych, ˇze ha,b (x) = ha,b (y), roven 2 2 N 2 ⌈N ⌈ ⌉ ⌉ N 2 N |H| m ⌈ ⌉ = m 2 = m 2 . N N m m m m

m

Závˇer: Dokázali jsme existenci c-univerzáln´ıch systém˚ u pro c bl´ızké 1. Staˇc´ı si uvˇedomit, ˇze bez ztráty obecnosti, kaˇzdé univerzum m˚ uˇzeme povaˇzovat za univerzum tvaru {0, 1, . . . , N − 1} pro nˇejaké N a ˇze mezi ˇc´ısly N a 2N vˇzdy existuje nˇejaké prvoˇc´ıslo.

Vlastnosti univerzáln´ıho haˇsov´ an´ı Pˇredpoklad: H je c-univerzáln´ı systém funkc´ı Oznaˇcen´ı: Pro funkci h ∈ H a prvky x, y ∈ U oznaˇcme δh (x, y) = 1

kdyˇz x 6= y a h(x) = h(y)

δh (x, y) = 0 kdyˇz x = y nebo h(x) 6= h(y).

29

Pro mnoˇzinu S ⊆ U , x ∈ U a h ∈ H definujme X δh (x, S) = δh (x, y). y∈S

Pro fixovanou mnoˇzinu S ⊆ U a pro fixované x ∈ U seˇcteme δh (x, S) pˇres vˇsechny h ∈ H: X XX XX X δh (x, y) = δh (x, y) = |{h ∈ H | h(x) = h(y)}| ≤ δh (x, S) = h∈H

h∈H y∈S

X

y∈S,y6=x

y∈S,y6=x

y∈S h∈H

|H| c = m

(

(|S| − 1)c |H| m

if x ∈ S,

|S|c |H| m

if x ∈ / S.

Oˇcekávaná délka ˇretˇezce pro fixovanou mnoˇzinu S ⊆ U a fixované x ∈ U pˇres h ∈ H s rovnomˇern´ ym rozdˇelen´ım je |S| − 1 kdyˇz x ∈ S, m |S| c kdyˇz x ∈ / S. m Vˇ eta. Oˇcek´ avan´ y ˇcas operac´ı MEMBER, INSERT a DELETE pˇri c-univerz´ aln´ım |S| haˇsov´ an´ı je O(1 + cα), kde α je faktor naplnˇen´ı (tj. α = m ). Oˇcek´ avan´ y ˇcas posloupnosti n operac´ı MEMBER, INSERT a DELETE aplikovan´ ych c na pr´ azdnou tabulku pˇri c-univerz´ aln´ım haˇsov´ an´ı je O(1 + 2 α). c

V´ yznam v´ ysledku: Vzorec se jen o multiplikativn´ı konstantu c liˇs´ı od vzorce pro haˇsov´ an´ı se separovan´ ymi ˇretˇezci. Pˇritom c m˚ uˇze b´ yt jen o málo menˇs´ı neˇz 1 a ve vˇsech zn´ am´ ych pˇr´ıkladech je c ≥ 1. Takˇze, co jsme dosáhli? Rozd´ıl je v pˇredpokladech. Zde je pˇredpoklad 3) nahrazen pˇredpokladem, ˇze funkce h ∈ H je vybrána s rovnomˇern´ ym rozdˇelen´ım, a nen´ı ˇzádn´ y pˇredpoklad na vstupn´ı data. V´ ybˇ er funkce h m˚ uˇ zeme ovlivnit, ale v´ ybˇ er vstupn´ıch dat nikoliv. M˚ uˇzeme zajistit rovnomˇerné rozdˇelen´ı v´ ybˇeru h z H nebo se k tomuto rozdˇelen´ı hodnˇe pˇribl´ıˇzit.

Markovova nerovnost Pˇredpoklady: Vybraná mnoˇzina S ⊆ U , prvek x ∈ U . Oˇcekávaná délka ˇretˇezce S, kter´ y by mˇel obsahovat x, je µ, a t ≥ 1. Ukáˇzeme, ˇze pravdˇepodobnost, ˇze pro h ∈ H je délka ˇretˇezce alespoˇ n tµ, je menˇs´ı neˇz (pˇredpokladáme, ˇze h je z H vybrána s rovnomˇern´ ym rozdˇelen´ım).

1 t

Oznaˇcme H ′ = {h ∈ H | δh (x, S) ≥ tµ}. Pak plat´ı P P P |H ′ | ′ tµ h∈H δh (x, S) h∈H ′ δh (x, S) µ= > ≥ h∈H = tµ |H| |H| |H| |H| Odtud

|H| . t Závˇer: Pravdˇepodobnost, ˇze δh (x, S) ≥ tµ, je menˇs´ı neˇz |H ′ | <

1 t

a odtud plyne poˇzadované tvrzen´ı.

Poznámka: Toto tvrzen´ı plat´ı obecnˇe a naz´ yvá se Markovova nerovnost. Uveden´ y d˚ ukaz ilustruje jednoduchou ideu pro koneˇcn´ y pˇr´ıpad.

30

Problémy Hlavn´ı problém: Zajiˇstˇen´ı rovnomˇerného rozdˇelen´ı v´ ybˇeru h z H. Proveden´ı v´ ybˇeru: Zakódovat funkce z mnoˇziny H do ˇc´ısel 0, 1, . . . , |H| − 1. Zvolit náhodnˇe ˇc´ıslo i z tohoto intervalu s rovnomˇern´ ym rozdˇelen´ım, a pak pouˇz´ıt funkci s kódem i. Abychom vybrali i, nalezneme nejmenˇs´ı j takové, ˇze 2j − 1 ≥ |H| − 1. Pak ˇc´ısla v intervalu {0, 1, . . . , 2j − 1} jednoznaˇcnˇe koresponduj´ı s posloupnostmi 0 a 1 délky j. Budeme vyb´ırat náhodnˇe posloupnost 0 a 1 délky j. K v´ ybˇeru posloupnosti pouˇzijeme náhodn´ y gener´ ator rovnomˇerného rozdˇelen´ı. Závada: Skuteˇcn´ y náhodn´ y generátor pro rovnomˇerné rozdˇelen´ı je prakticky nedosaˇziteln´ y (nˇekteré fyzikáln´ı procesy). K dispozici je pouze pseudogenerátor. ˇ ım je j vˇetˇs´ı, t´ım je posloupnost pravidelnˇejˇs´ı (tj. ménˇe náhodná). Jeho nev´ yhoda: C´ Zámˇer: Nalézt co nejmenˇs´ı c-univerzáln´ı systémy. Nalézt doln´ı odhady na jejich velikost.

Doln´ı odhady na velikost Pˇredpoklady: Nechˇt U je universum velikosti N a nechˇt H je c-univerzáln´ı systém funkc´ı haˇsuj´ıc´ıch do tabulky velikosti m. Pˇredpokládejme, ˇze H = {h0 , h1 , . . . , }. Indukc´ı definujme mnoˇziny U0 , U1 , . . . tak, ˇze U0 = U . Nechˇt U1 je nejvˇetˇs´ı podmnoˇzina U0 vzhledem k poˇctu prvk˚ u taková, ˇze h0 (U1 ) je jednoprvková mnoˇzina. Nechˇt U2 je nejvˇetˇs´ı podmnoˇzina U1 vzhledem k poˇctu prvk˚ u taková, ˇze h1 (U2 ) je jednoprvková mnoˇzina. Nechˇt U3 je nejvˇetˇs´ı podmnoˇzina U2 vzhledem k poˇctu prvk˚ u taková, ˇze h2 (U3 ) je jednoprvková mnoˇzina. Obecnˇe, nechˇt Ui je nejvˇetˇs´ı podmnoˇzina Ui−1 vzhledem k poˇctu prvk˚ u taková, ˇze hi−1 (Ui ) je jednoprvková mnoˇzina. |U

|

i−1 Protoˇze haˇsujeme do tabulky velikosti m, plat´ı|Ui | ≥ ⌈ m ⌉. Protoˇze |U0 | = N , dost´ av´ ame N indukc´ı, ˇze |Ui | ≥ ⌈ mi ⌉ pro kaˇzdé i. Zvolme i = ⌈logm N ⌉ − 1. Pak i je nejvˇetˇs´ı pˇrirozené N a aspoˇ n dva prvky, zvolme x, y ∈ Ui takové, ˇze x 6= y. ˇc´ıslo takové, ˇze m i > 1. Tedy Ui m´ Pak hj (x) = hj (y) pro j = 0, 1, . . . , i − 1. Tedy

i ≤ |{h ∈ H | h(x) = h(y)}| ≤

c|H| . m

Vˇ eta. Kdyˇz H je c-univerz´ aln´ı systém pro univerzum U o velikosti N haˇsuj´ıc´ı do tabulky s m ˇra ´dky, pak m |H| ≥ (⌈logm N ⌉ − 1). c Posloupnosti 0 a 1 pˇri n´ ahodné volbˇe h z H mus´ı m´ıt délku ⌈(log m − log c + log log N − log log m)⌉.

Mal´ y univerzáln´ı systém Zkonstruujeme c-univerzáln´ı systém takov´ y, ˇze logaritmus z jeho velikosti pro velká univerza je aˇz na aditivn´ı konstantu menˇs´ı neˇz 4(log m + log log N ), kde N je velikost univerza a m je poˇcet ˇrádk˚ u v tabulce.

31

Nechˇt p1 , p2 , . . . je rostouc´ı posloupnost vˇsech prvoˇc´ısel. Pˇredpoklady: Dáno univerzum U = {0, 1, . . . , N − 1}, kde N je pˇrirozené ˇc´ıslo N a ˇc´ıslo m. Nechˇt t je nejmenˇs´ı ˇc´ıslo takové, ˇze t ln pt ≥ m ln N . Definujme H1 = {gc,d (hℓ ) | t < ℓ ≤ 2t, c, d ∈ {0, 1, . . . , p2t − 1}}, kde hℓ (x) = x mod pℓ a gc,d (x) = ((cx + d) mod p2t ) mod m. Ukáˇzeme, ˇze H1 je 5-univerzáln´ı systém. Velikost H1 . Protoˇze gc,d (hℓ ) 6= gc′ d′ (hℓ′ ) jakmile (c, d, ℓ) 6= (c′ , d′ , ℓ′ ), dostáváme, ˇze |H1 | = tp22t (protoˇze c a d prob´ıhaj´ı p2t ˇc´ısel a ℓ prob´ıhá t ˇc´ısel). Z vˇety o rozloˇzen´ı prvoˇc´ısel plyne existence konstanty a takové, ˇze pi ≤ ai ln i pro kaˇzdé i, tedy p2t ≤ 2at ln 2t. Tedy |H1 | ≤ 4a2 t3 ln2 2t. Z toho dostáváme log(|H1 |) ≤ 2 + 2 log a + 3 log t + 2 log log t. Pro dostateˇcnˇe velké t (takové, ˇze log t ≥ 2 log log t) existuje aditivn´ı konstanta b, ˇze log(|H1 |) ≤ b + 4 log t. Z definice t plyne, ˇze t ≤ m ln N , kdyˇz ln pt ≥ 1 (tj. pt ≥ 3). Závˇer: log(|H1 |) ≤ b + 4(log m + log log N ).

Univerzalita malého systému Zvolme r˚ uzná x a y z univerza U . Oznaˇc´ıme G1 = {(c, d, ℓ) | gc,d (hℓ (x)) = gc,d (hℓ (y)), hℓ (x) 6= hℓ (y)}, G2 = {(c, d, ℓ) | gc,d (hℓ (x)) = gc,d (hℓ (y)), hℓ (x) = hℓ (y)} a odhadneme velikost G1 a G2 . Odhad velikosti G1 . Kdyˇz (c, d, ℓ) ∈ G1 , pak existuj´ı i ∈ {0, 1, . . . , m − 1} a r, s ∈ {0, 1, . . . , ⌈ pm2t ⌉ − 1} taková, ˇze (c(x mod pℓ ) + d ≡ i + rm) mod p2t (c(y mod pℓ ) + d ≡ i + sm) mod p2t . Kdyˇz c a d povaˇzujeme za nezn´ amé, pak je to lineárn´ı soustava rovnic s regulárn´ı matic´ı (protoˇze x mod pℓ 6= y mod pℓ ), a tedy pro kaˇzdé ℓ, i, r a s existuje nejv´ yˇse jedna dvojice (c, d). Proto tp2 m 2 |H1 | m 2 p2t ) = ) . (1 + |G1 | ≤ tm(⌈ ⌉)2 ≤ 2t (1 + m m p2t m p2t Q Odhad velikosti G2 . Oznaˇcme L = {ℓ | t < ℓ ≤ 2t, x mod pℓ = y mod pℓ } a P = ℓ∈L pℓ . Protoˇze P dˇel´ı |x − y|, dostáváme, ˇze P ≤ N . Protoˇze pt < pℓ pro kaˇzdé ℓ ∈ L, dostáv´ ame, |L| ln N t ˇze P > pt . Tedy |L| ≤ ln pt ≤ m z definice t. Protoˇze (c, d, ℓ) ∈ G2 právˇe kdyˇz ℓ ∈ L a c, d ∈ {0, 1, . . . , p2t − 1}, shrneme, ˇze |G2 | ≤ |L|p22t ≤

tp22t |H1 | = . m m

32

Kdyˇz m ≥ p2t , pak t ln pt < pt ln p2t < m ln m < m ln N

(protoˇze m ≤ N ),

a to je spor s definic´ı t. Tedy m < p2t a odtud {h ∈ H1 | h(x) = h(y)}| = |G1 | + |G2 | ≤

|H1 | m 2 |H1 | |H1 | |H1 | (1 + ) + ≤ (1 + 22 ) = 5 . m p2t m m m

Shrnut´ı: H1 je 5-univerzáln´ı. Odhad na velikost c. Kdyˇz H je c-univerzáln´ı systém univerza U o velikosti N haˇsuj´ıc´ı do m . tabulky s m ˇrádky, pak c ≥ 1 − N

Problémy univerzáln´ıho haˇsov´ an´ı Pouˇz´ıt jiné metody na ˇreˇsen´ı koliz´ı neˇz separuj´ıc´ı ˇretˇezce. Jak to ovlivn´ı pouˇzitelnost univerzáln´ıho haˇsován´ı? Plat´ı podobné vztahy jako pro pevnˇe danou haˇsovac´ı funkci? Jak´ y vliv na efektivnost má nepˇr´ıtomnost operace DELETE? Existuje c-univerzáln´ı haˇsovac´ı systém pro c < 1. Jak´ y je vztah mezi velikost´ı c-univerz´ aln´ıho haˇsovac´ıho systému a velikost´ı c? Lze zkonstruovat mal´ y c-univerzáln´ı systém pro c < 5? Zde hraje roli fakt, ˇze pˇri c = 5 se oˇcekávaná délka ˇretˇezce m˚ uˇze pohybovat aˇz kolem hodnoty 10. ˇ Pouˇzit´ı Cebyˇ sevovy nerovnosti m´ısto Markovovy nerovnosti dáv´ a kvadratick´ y odhad pravdˇepodobnosti, ˇze délka ˇretˇezce je o t vˇetˇs´ı neˇz oˇcekávaná hodnota. Za jak´ ych okolnost´ı d´ av´ a lepˇs´ı odhad? Lze pouˇz´ıt i vyˇsˇs´ıch moment˚ u. Jak pouˇz´ıt Markovou nerovnost a oˇcekávanou délku maximáln´ıho ˇretˇezce pro volbu haˇsovac´ı funkce. Pro jaké parametry lze pouˇz´ıt následuj´ıc´ı model? Dáno m, základn´ı velikost tabulky, pro i = 0, 1, . . . c-univerzáln´ı haˇsovac´ı systém Hi z univerza do tabulky s m2i ˇrádky a koeficienty li . Uloˇzen´ı S ⊆ U : dáno i takové, ˇze kdyˇz i > 0, pak plat´ı m2i−2 ≤ |S| ≤ m2i , kdyˇz i = 0, pak plat´ı |S| ≤ m, a je zvolená hi ∈ Hi . Prvek s ∈ S je uloˇzen v ˇretˇezci hi (s) a kaˇzd´ y ˇretˇezec má délku nejv´ yˇse li . Pˇri operaci INSERT, kdyˇz se poruˇs´ı poˇzadavek na velikost |S|, pak se zvˇetˇs´ı i o 1 a náhodnˇe se zvol´ı hi ∈ Hi . Kdyˇz se poruˇs´ı poˇzadavek na délku ˇretˇezc˚ u, pak se vol´ı nové hi ∈ Hi . V obou pˇr´ıpadech se volba opakuje tak dlouho, dokud nen´ı splnˇena podm´ınka na ˇretˇezce. Operace DELETE se ˇreˇs´ı stejnˇe. Problémy: Jak volit parametry li ? V pˇr´ıpadˇe ˇreˇsen´ı koliz´ı dvojit´ ym haˇsován´ım nebo haˇsován´ım s lineárn´ım pˇridáván´ım je tˇreba dát silnˇejˇs´ı podm´ınky na velikost |S|. Jaké? S jakou pravdˇepodobnost´ı se pˇrepoˇc´ıtává uloˇzen´ı S s novou haˇsovac´ı funkc´ı?

33

Perfektn´ı haˇsov´ an´ı Jiné ˇreˇsen´ı koliz´ı je perfektn´ı haˇsován´ı. Idea je nalézt pro danou mnoˇzinu haˇsovac´ı funkci, která nemá kolize. Nev´ yhoda: Metoda nepˇripouˇst´ı operaci INSERT (pro nov´ y vstup nem˚ uˇzeme zaruˇcit, ze nebude kolize). Metodu lze prakticky pouˇz´ıt pro u ´lohy, kde lze oˇcekávat hodnˇe operac´ı MEMBER a operace INSERT se témˇeˇr nevyskytuje (kolize se ˇreˇs´ı pomoc´ı malé pomocné tabulky, kam se ukládaj´ı koliduj´ıc´ı data). Zadán´ı u ´lohy: Pro danou mnoˇzinu S ⊆ U chceme nalézt haˇsovac´ı funkci h takovou, ˇze 1) pro s, t ∈ S takové, ˇze s 6= t, plat´ı h(s) 6= h(t) (tj. h je perfektn´ı haˇsovac´ı funkce pro S); 2) h haˇsuje do tabulky s m ˇrádky, kde m je pˇribliˇznˇe stejnˇe velké jako |S| (nen´ı praktické haˇsovat do pˇr´ıliˇs velk´ ych tabulek – ztrác´ı se jeden ze základn´ıch d˚ uvod˚ u pro haˇsován´ı); 3) h mus´ı b´ yt rychle spoˇcitatelná – jinak haˇsován´ı nen´ı rychlé; 4) uloˇzen´ı h nesm´ı vyˇzadovat moc pamˇeti, nejv´ yhodnˇejˇs´ı je analytické zadán´ı (kdyˇz zad´ an´ı h bude vyˇzadovat moc pamˇeti, napˇr. kdyˇz by byla dána tabulkou, pak se ztrác´ı stejn´ y d˚ uvod k pouˇzit´ı jako v bodu 2). Kompenzace: Nalezen´ı haˇsovac´ı funkce m˚ uˇze potˇrebovat v´ıce ˇcasu. Provád´ı se jen na zaˇcátku u ´lohy. Uvedené poˇzadavky motivuj´ı následuj´ıc´ı pojem. Mˇejme univerzum U = {0, 1, . . . , N − 1}. Soubor funkc´ı H z U do mnoˇziny {0, 1, . . . , m − 1) se naz´ yvá (N, m, n)-perfektn´ı, kdyˇz pro kaˇzdou S ⊆ U takovou, ˇze |S| = n, existuje h ∈ H perfektn´ı pro S (tj. h(s) 6= h(t) pro kaˇzdá dvˇe r˚ uzná s, t ∈ S). Tento pojem budeme vyˇsetˇrovat v následuj´ıc´ı pˇrednáˇsce.

34

Pˇredn´ aˇska 5 Perfektn´ı haˇsov´ an´ı Pˇripomenut´ı: U = {0, 1, . . . , N − 1} pro nˇejaké pˇrirozené ˇc´ıslo N , S ⊆ U . Funkce h : U − → {0, 1, . . . , m − 1} je perfektn´ı pro mnoˇzinu S, kdyˇz h(s) 6= h(t) pro kaˇzdou dvojici r˚ uzn´ ych prvk˚ u z S. Naˇs´ım c´ılem je pro mnoˇzinu S nalézt m a funkci h : U − → {0, 1, . . . , m − 1} takovou, ˇze 1) h je perfektn´ı haˇsovac´ı funkce pro S; 2) m je pˇribliˇznˇe stejnˇe velké jako |S| (nen´ı praktické haˇsovat do pˇr´ıliˇs velk´ ych tabulek – ztrác´ı se jeden ze základn´ıch d˚ uvod˚ u pro haˇsován´ı, efektivn´ı vyuˇzit´ı pamˇeti); 3) h mus´ı b´ yt rychle spoˇcitatelná – jinak haˇsován´ı nen´ı rychlé; 4) uloˇzen´ı h nesm´ı vyˇzadovat moc pamˇeti, nejv´ yhodnˇejˇs´ı je analytické zadán´ı (kdyˇz zad´ an´ı h bude vyˇzadovat moc pamˇeti, napˇr. kdyˇz by byla dána tabulkou, pak se ztrác´ı stejn´ y d˚ uvod k pouˇzit´ı jako v bodu 2). Tyto nároky jsou kompenzovány menˇs´ımi nároky na ˇcas pˇri hledán´ı h a m. Protoˇze nev´ıme, zda taková h existuj´ı, nejprve vyˇsetˇr´ıme mnoˇziny perfektn´ıch haˇsovac´ıch funkc´ı. Definujeme: Mˇejme univerzum U = {0, 1, . . . , N − 1}. Soubor funkc´ı H z U do mnoˇziny {0, 1, . . . , m − 1) se naz´ yvá (N, m, n)-perfektn´ı, kdyˇz pro kaˇzdou S ⊆ U takovou, ˇze |S| = n, existuje perfektn´ı h ∈ H pro S. Vyˇsetˇr´ıme vlastnosti (N, m, n)-perfektn´ıch soubor˚ u funkc´ı.

Doln´ı odhady na velikost Mˇejme funkci h z U do mnoˇziny {0, 1, . . . , m−1}. Nalezneme poˇcet mnoˇzin S ⊆ U takov´ ych, ˇze h je perfektn´ı funkce pro S a |S| = n. Funkce h je perfektn´ı pro S ⊆ U , právˇe kdyˇz pro kaˇzdé i = 0, 1, . . . , m − 1 je |h−1 (i) ∩ S| ≤ 1. Odtud poˇcet tˇechto mnoˇzin je X n−1 Y { |h−1 (ij )| | 0 ≤ i0 < i1 < · · · < in−1 < m}. j=0

Vysvˇetlen´ı: h(S) = {ij | j = 0, 1, . . . , n − 1}. Toto ˇc´ıslo je maxim´ aln´ı, kdyˇz |h−1 (i)| = N pro kaˇzdé i. Tedy h m˚ uˇze b´ yt perfektn´ı nejv´ yˇse m m N n m pro n ( m ) mnoˇzin (ˇc´ıslo n urˇcuje poˇcet posloupnost´ı 0 ≤ i0 < i1 < · · · < in−1 < m). n-prvkov´ ych podmnoˇzin universa je N , tedy n N |H| ≥

m n

nN . ( m )n

Pˇredpokládejme, ˇze H = {h1 , . . . , ht } je (N, m, n)-perfektn´ı soubor funkc´ı. Definujme indukc´ı soubor mnoˇzin Ui : U0 = U a pro i > 0 je Ui nejvˇetˇs´ı podmnoˇzina Ui−1 , co do velikosti, taková, ˇze hi je konN i−1 | pro vˇsechna i > 0. Z |U0 | = N plyne |Ui | ≥ m zdé stantn´ı na Ui . Pak |Ui | ≥ |Um i . Pro kaˇ i = 1, 2, . . . , t je hj (Ui ) jednobodová mnoˇzina pro kaˇzdé j ≤ i. Proto ˇzádná hj pro j ≤ i nen´ı perfektn´ı pro mnoˇzinu S ⊆ U takovou, ˇze |S ∩ Ui } ≥ 2. Protoˇze H je (N, m, n)-perfektn´ı, log N N mus´ı b´ yt |Ut | ≤ 1, a tedy m t ≤ 1. Proto t ≥ log m .

35

Vˇ eta. Kdyˇz H je (N, m, n)-perfektn´ı soubor funkc´ı, pak |H| ≥ max{

N n m N n, n (m)

log N }. log m

Existence Mˇejme univerzum U = {0, 1, . . . , N − 1} a soubor funkc´ı H = {h1 , h2 , . . . , ht } z univerza U do mnoˇziny {0, 1, . . . , m − 1}. Reprezentujeme tento soubor pomoc´ı matice M (H) typu N × t s hodnotami {0, 1, . . . , m − 1} tak, ˇze v x-tém ˇrádku a i-tém sloupci matice M (H) pro x ∈ U a i = 1, 2, . . . , t je hodnota hi (x). Pak ˇzádná funkce z H nen´ı perfektn´ı pro mnoˇzinu S = {s1 , s2 , . . . , sn } ⊆ U , právˇe kdyˇz podmatice M (H) tvoˇrená ˇrádky s1 , s2 , aˇz sn a vˇsemi sloupci nemá prost´ y sloupec. Takov´ ych matic je nejv´ yˇse n

(m −

n−1 Y

(m − i))t m(N−n)t .

i=0

Qn−1 Vysvˇetlen´ı: mn je poˇcet vˇsech funkc´ı z S do {0, 1, . . . , m−1}, i=0 (m−i) je poˇcet prost´ ych funkc´ı z S do {0, 1, . . . , m − 1}, a tedy poˇcet vˇsech podmatic s n ˇrádky takov´ ych, ˇze ˇz´ adn´ y Qn−1 n t jejich sloupec nen´ı prost´ y, je (m − i=0 (m − i)) . Tyto podmatice m˚ uˇzeme libovolnˇe (N−n)t doplnit na matici typu N × n a pro kaˇzdou matici je tˇechto doplnˇen´ı m . Podmnoˇzin U velikosti n je N , tedy poˇcet vˇsech matic, které nereprezentuj´ı (N, m, n)n perfektn´ı systém, je menˇs´ı neˇz n−1 Y N n (m − i))t m(N−n)t . (m − n i=0

Vˇsech matic je mNt a kdyˇz n−1 Y N n (m − (m − i))t m(N−n)t < mNt , n i=0

(*)

pak nutnˇe existuje (N, m, n)-perfektn´ı systém. Následuj´ıc´ı v´ yrazy jsou ekvivalentn´ı s nerovnost´ı (∗) Qn−1 ln N N n i=0 (m − i) Qn−1 )<1 ⇔ t≥ . (1 − (m−i) mn n i=0 − ln(1 − ) mn Protoˇze ln N ze n ≤ n ln N a protoˇ − ln(1 −

Rn n−1 Pn−1 Y x i (m − i) i )dx ln(1− m ln(1− m ) i=0 0 ) ≥ (1 − ) = e ≥ e n m m i=0

Qn−1 i=0

36

kde integrál je roven m[(1 −

n n n n n2 )(1 − ln(1 − )) − 1] ≥ m[(1 − )(1 + ) − 1] = m m m m m n2

dostáváme, ˇze kdyˇz t ≥ n(ln N )e m , pak (*) plat´ı, a tedy existuje (N, m, n)-perfektn´ı soubor funkc´ı. Existence (N, m, n)-perfektn´ıho souboru funkc´ı ale nezaruˇcuje splnˇen´ı poˇzadavk˚ u 2), 3) a 4). Abychom uspˇeli, pouˇzijeme ideu z metody univerzáln´ıho haˇsován´ı. Pˇredpoklady: U = {0, 1, . . . , N − 1}, kde N je prvoˇc´ıslo. Mˇejme S ⊆ U o velikosti n. Budeme uvaˇzovat funkce hk (x) = (kx mod N ) mod m

pro k = 0, 1, . . . , N − 1.

Pro i = 0, 1, . . . , m − 1 a k = 0, 1, . . . , N − 1 oznaˇcme bki = |{x ∈ S | (kx mod N ) mod m = i}|. V´ yznam bki : Hodnoty bki lze povaˇzovat za veliˇciny, které ukazuj´ı odchylku od perfektnosti. Vˇsimnˇeme si, ˇze kdyˇz bki ≥ 2, pak (bki )2 − bki ≥ 2, protoˇze n2 − n ≥ 2, kdyˇz n ≥ 2. Na druhou stranu bki ≤ 1 implikuje (bki )2 − bki = 0. Tedy z

Pm−1 i=0

bki = n plyne

Pm−1 Vˇ eta. Funkce hk je perfektn´ı, pr´ avˇe kdyˇz i=0 (bki )2 − n < 2. PN−1 Pm−1 Nyn´ı odhadneme v´ yraz k=1 ( i=0 (bki )2 ) − n . N−1 X k=1

(

m−1 X

(bki )2 )

i=0

N−1 X

−n =

N−1 X k=1

(

m−1 X i=0

|{x ∈ S | hk (x) = i}|2 ) − n =

|{(x, y) | x 6= y, x, y ∈ S, hk (x) = hk (y)}| =

k=1

X

|{k | 1 ≤ k < N, hk (x) = hk (y)}|.

x,y∈S,x6=y

Zvolme x, y ∈ S taková, ˇze x 6= y. Pak hk (x) = hk (y), právˇe kdyˇz (kx mod N −ky mod N ) = N N 0 mod m, a to je ekvivalentn´ı s t´ım, ˇze k(x − y) ≡ rm mod N pro nˇejaké r = −⌈ m ⌉, −⌈ m ⌉+ N 1, . . . , −1, 1, 2, . . . , ⌈ m ⌉.

37

Vysvˇetlen´ı: Kdyˇz x > y, pak k(x − y) > 0, a tedy hk (x) = hk (y) je ekvivalentn´ı s t´ım, N ˇze k(x − y) ≡ rm mod N pro r = 1, 2, . . . , ⌈ m ⌉. Kdyˇz x < y, pak k(x − y) < 0, a tedy N hk (x) = hk (y) je ekvivalentn´ı s t´ım, ˇze k(x − y) ≡ rm mod N pro r = −1, −2, . . . , −⌈ m ⌉. Protoˇze pro r˚ uzná x a y a pro jedno r existuje právˇe jedno k takové, ˇze k(x−y) ≡ rm mod N (protoˇze ZN je tˇeleso, tato rovnice má jediné ˇreˇsen´ı), dostáváme, ˇze pro x, y ∈ S, x 6= y N existuje nejv´ yˇse 2 m − 1 r˚ uzn´ ych k = 1, 2, . . . , N − 1. Odtud N−1 X k=1

(

m−1 X i=0

(bki )2 ) − n ≤

X

x,y∈S,x6=y

2⌈

n(n − 1) N ⌉ − 1 ≤ (N − 1)2 . m m

Pm−1 Pm−1 Proto existuje k takové, ˇze i=0 (bki )2 ≤ 2 n(n−1) + n. Protoˇze i=0 (bki )2 ≥ n pro vˇsechna m Pm−1 ych k, ˇze i=0 (bki )2 ≤ 4 n(n−1) + n. k, existuje alespoˇ n N2 takov´ m

Tvrzen´ı. Kdyˇz n = m, pak Pm−1 (a) existuje deterministick´ y algoritmus, kter´ y nalezne k takové, ˇze i=0 (bki )2 < 3n ˇcase O(nN ); Pm−1 (b) existuje pravdˇepodobnostn´ı algoritmus, kter´ y nalezne k takové, ˇze i=0 (bki )2 < 5n v ˇcase O(n). D´ ale (c) existuje deterministick´ y algoritmus, kter´ y pro m = 1+n(n−1) v ˇcase O(nN ) nalezne k takové, ˇze hk je perfektn´ı; (d) existuje pravdˇepodobnostn´ı algoritmus, kter´ y pro n = 1 + 2n(n − 1) v ˇcase O(n) nalezne k takové, ˇze hk je perfektn´ı. Pm−1 k 2 D˚ ukaz. Mˇejme n = m. Protoˇze spoˇc´ıtán´ı e k vyˇzaduje ˇcas O(n), i=0 (bi ) pro pevn´ Pm−1 k 2 + n = 3n − 2 < systematick´ ym prohledán´ım nalezneme k takové, ˇze i=0 (bi ) ≤ 2 n(n−1) n 3n, v ˇcase O(nN ). T´ım je dok´ azáno a). Pro náhodnˇe zvolené k, Prob(

m−1 X

(bki )2 ≤ 4

i=0

n(n − 1) 1 + n = 5n − 2 < 5n) ≤ n 2

a dostáváme tvrzen´ı b). (Vol´ıme náhodnˇe k, dokud nen´ı splnˇeno tvrzen´ı). Kdyˇz m = 1 + n(n − 1), pak systematick´ ym prohledán´ım vˇsech moˇznost´ı nalezneme k Pm−1 k 2 n(n−1) takové, ˇze i=0 (bi ) ≤ 2 1+n(n−1) + n < n + 2, v ˇcase O(nN ) a c) plyne z pˇredchoz´ı vˇety. Kdyˇz m = 1 + 2n(n − 1), pak pro náhodnˇe zvolené k plat´ı s pravdˇepodobnost´ı ≤ 12 , ˇze Pm−1 k 2 2n(n−1) ı d) plyne z pˇredchoz´ı vˇety. i=0 (bi ) ≤ 1+2n(n−1) + n < n + 2. Nyn´

Takto zkonstruované perfektn´ı haˇsovac´ı funkce nesplˇ nuj´ı poˇzadavek 2) (m = Θ(n2 )). Pouˇzijeme následuj´ıc´ı postup. Pm−1 Pm−1 1) Nalezneme k takové, ˇze pro m = n plat´ı i=0 (bki )2 < 3n (respektive i=0 (bki )2 < 5n). Pro i = 0, 1, . . . , m − 1 nalezneme mnoˇzinu Si = {s ∈ S | hk (s) = i}; 2) Pro kaˇzdé i = 0, 1 . . . , m−1 takové, ˇze Si 6= ∅, nalezneme pro m = 1+n(n−1) (respektive m = 1 + 2n(n − 1)) takové ki , ˇze hki je perfektn´ı na Si . Definujme ci = 1 + |Si |(|Si | − 1), kdyˇz Si 6= ∅, a ci = 0, kdyˇz Si = ∅. Pi−1 3) Pro i = 0, 1, . . . , m definujme di = cme hk (x) = l. Pak j=0 cj a pro x ∈ U oznaˇ g(x) = dl + hkl (x).

38

Vˇ eta. Zkonstruovan´ a funkce g je perfektn´ı, hodnota g(x) se pro kaˇzdé x ∈ U spoˇc´ıt´ a v ˇcase O(1), v deterministickém pˇr´ıpadˇe haˇsuje do tabulky velikosti < 3n a je nalezena v ˇcase O(nN ), v pravdˇepodobnostn´ım pˇr´ıpadˇe haˇsuje do tabulky velikosti < 9n a je nalezena v ˇcase O(n). Pro jej´ı zak´ odov´ an´ı jsou tˇreba hodnoty k a ki pro i = 0, 1, . . . , m − 1. Tyto hodnoty jsou v rozmez´ı 1, 2, . . . , N − 1, a tedy vyˇzaduj´ı O(n log N ) pamˇeti. D˚ ukaz. Protoˇze g(Si ) pro i = 0, 1, . . . , m − 1 jsou navzájem disjunktn´ı a hki je perfektn´ı na Si , dostáváme, ˇze g je perfektn´ı. Pro v´ ypoˇcet hodnoty g(x) jsou tˇreba dvˇe násoben´ı, dvoj´ı v´ ypoˇcet zbyteku pˇri dˇelen´ı a jedno sˇc´ıtán´ı (hodnoty di jsou uloˇzené v pamˇeti). Proto v´ ypoˇcet g(x) vyˇzaduje ˇcas O(1). Dále dm je horn´ı odhad na poˇcet ˇradk˚ u v tabulce. Protoˇze 2 k 2 pro Si 6= ∅ máme |Si |(|Si | − 1) + 1 ≤ |Si | = (bi ) , dostáváme v deterministickém pˇr´ıpadˇe Pm−1 Pm−1 dm = i=0 ci ≤ i=0 (bki )2 < 3n a k nalezneme v ˇcase O(nN ). Protoˇze ki nalezneme v ˇcase O(|Si |N ), lze g zkonstruovat v ˇcase O(nN +

m−1 X i=0

|Si |N ) = O(nN + N

m−1 X

|Si |) = O(2nN ) = O(nN ).

i=0

Pm−1 V pravdˇepodobnostn´ım pˇr´ıpadˇe je 2|Si |(|Si |−1)+1 ≤ 2|Si |2 −|Si | a odtud dm = i=0 ci ≤ Pm−1 k Pm−1 k 2 case O(n) a ki v ˇcase O(|Si |). To i=0 bi < 10n − n = 9n a k nalezneme v ˇ i=0 2(bi ) − znamená, ˇze g nalezneme v ˇcase O(n). Zbytek je jasn´ y. Tedy zkonstruovaná haˇsovac´ı funkce splˇ nuje poˇzadavky 1), 2) a 3), ale poˇzadavek 4) nen´ı splnˇen. Mˇejme pˇrirozené ˇc´ıslo m a q je poˇcet vˇsech prvoˇc´ısel, které dˇel´ı m. (p1 , p2 , . . . je rostouc´ı posloupnost vˇsech prvoˇc´ısel). Pak q Y

Rq Pq q q ln xdx ln i pi > q! = e i=1 m≥ ≥e 1 = eq ln( e )+1 ≥ ( )q . e i=1 nme tento fakt Proto existuje konstanta c, ˇze q ≤ c lnlnlnmm . Shrˇ Vˇ eta. Nechˇt δ(m) =poˇcet prvoˇc´ısel, které dˇel´ı m. Pak δ(m) = O( logloglogmm ). Mˇejme S = {s1 < s2 < · · · < sn } ⊆ U . Oznaˇcme di,j = sj − si pro 1 ≤ i < j ≤ n, pak Q 2 si mod p 6= sj mod p, právˇe kdyˇz di,j 6= 0 mod p. Oznaˇcme D = 1≤i<j≤n di,j ≤ N (n ) . Pak poˇcet prvoˇc´ıseln´ ych dˇelitel˚ u ˇc´ısla D je nejv´ yˇse c lnlnlnDD a tedy mezi prvn´ımi 1 + c lnlnlnDD prvoˇc´ısly existuje prvoˇc´ıslo p takové, ˇze si mod p 6= sj mod p pro kaˇzdé 1 ≤ i < j ≤ n. To znamená, ˇze funkce φp (x) = x mod p je perfektn´ı pro S. Podle vˇety o rozloˇzen´ı prvoˇc´ısel existuje konstanta a taková, ˇze pt ≤ at ln t pro kaˇzdé t, tedy ln D ln D ln D ln D ) ln(1 + c ) ≤ 2ac ln(2c )≤ ln ln D ln ln D ln ln D ln ln D ln D ln D ln D + 2ac ln( ) = O(ln D) = O(n2 ln N ). 2ac ln 2c ln ln D ln ln D ln ln D

p ≤a(1 + c

39

Vˇ eta. Pro kaˇzdou n-prvkovou mnoˇzinu S ⊆ U existuje prvoˇc´ıslo p o velikosti O(n2 ln D) takové, ˇze funkce φp (x) = x mod p je perfektn´ı pro S. Test, zda funkce φp (x) = x mod p je perfektn´ı pro S, vyˇzaduje ˇcas O(n log n). Tedy systematické hledán´ı nejmenˇs´ıho p, ˇze φp je perfektn´ı pro S, vyˇzaduje ˇcas O(n3 log n log N ). Nejmenˇs´ı p takové, ˇze φp je perfektn´ı pro S, je prvoˇc´ıslo. Navrhneme pravdˇepodobnostn´ı algoritmus pro nalezen´ı p. Existuje konstanta a taková, ˇze mezi prvn´ımi an2 ln N prvoˇc´ısly je alespoˇ n polovina takov´ ych prvoˇc´ısel p, ˇze φp je perfektn´ı pro S. Algoritmus pak opakuje následuj´ıc´ı krok, dokud nenalezne perfektn´ı funkci vyberme náhodnˇe prvoˇc´ıslo p mezi prvn´ımi an2 ln N prvoˇc´ısly a otestujme, zda φp je perfektn´ı Odhad oˇcekávaného poˇctu ne´ uspˇeˇsn´ ych krok˚ u. 2 Náhodnˇe zvolené ˇc´ıslo p ≤ an ln N je prvoˇc´ıslo s pravdˇepodobnost´ı Θ( ln(an21 ln N) ) a pro prvoˇc´ıslo p je φp perfektn´ı s pravdˇepodobnost´ı ≥ 12 . Tedy náhodnˇe zvolené ˇc´ıslo p ≤ an2 ln N y poˇcet ne´ uspˇeˇsn´ ych test˚ u splˇ nuje test s pravdˇepodobnost´ı Θ( ln(an21 ln N) ), a proto oˇcekávan´ 2 je O(ln(an ln N ). Tedy oˇcekávan´ y ˇcas algoritmu je O(n log n(log n + log log N )). Vˇ eta. Pro danou mnoˇzinu S ⊆ U takovou, ˇze |S| = n, deterministick´ y algoritmus nalezne prvoˇc´ıslo p = O(n2 log N ) takové, ˇze φp (x) = x mod p je perfektn´ı pro S, a pracuje v ˇcase O(n3 log n log N ), a pravdˇepodobnostn´ı algoritmus nalezne prvoˇc´ıslo p = O(n2 log N ) takové, ˇze φp je perfektn´ı, v oˇcek´ avaném ˇcase O(n log n(log n + log log N ). Deterministick´ y algoritmus nalezne nejmenˇs´ı prvoˇc´ıslo s poˇzadovanou vlastnost´ı. Pravdˇepodobnostn´ı algoritmus nalezne prvoˇc´ıslo, které m˚ uˇze b´ yt podstatnˇe vˇetˇs´ı, ale jeho velikost je 2 omezena an log N pro konstantu a, která je vˇetˇs´ı neˇz konstanta v odhadu na velikost p v deterministickém algoritmu. Nyn´ı navrhneme postup na konstrukci perfektn´ı haˇsovac´ı funkce pro mnoˇzinu S ⊆ U . 1) Nalezneme prvoˇc´ıslo q0 ∈ O(n2 log N ) takové, ˇze φq0 (x) = x mod q0 je perfektn´ı funkce pro S. Poloˇzme S1 = {φq0 (s) | s ∈ S}. 2) Nalezneme prvoˇc´ıslo q1 takové, ˇze 1 + n(n − 1) ≤ q1 ≤ 2 + 2n(n − 1). Pak existuje l ∈ {1, 2, . . . , q0 − 1} takové, ˇze hl (x) = ((lx) mod q0 ) mod q1 je perfektn´ı pro S1 ⊆ {0, 1, . . . , q0 − 1}. Poloˇzme S2 = {hl (s) | s ∈ S1 }. 3) Podle pˇredchoz´ı vˇety zkonstruujme perfektn´ı haˇsovac´ı funkci g pro podmnoˇzinu S2 univerza {0, 1, . . . , q1 − 1} do tabulky s ménˇe neˇz 3n ˇrádky. Poloˇzme f (x) = g(hl (φq0 (x))). Konstruovaná haˇsovac´ı funkce je f . V´ ysledek: f je perfektn´ı haˇsovac´ı funkce pro S, protoˇze sloˇzen´ı perfektn´ıch haˇsovac´ıch funkc´ı je zase perfektn´ı funkce, a tedy poˇzadavek 1) je splnˇen. f haˇsuje S do tabulky s ménˇe neˇz 3n ˇrádky, a tedy splˇ nuje poˇzadavek 2). Protoˇze kaˇzd´ a z funkc´ı g, hl , φq0 se vyˇc´ısl´ı v ˇcase O(1), i vyˇc´ıslen´ı funkce f vyˇzduje ˇcas O(1) a poˇzadavek 3) je splnˇen. Funkce φq0 je jednoznaˇcnˇe urˇcena ˇc´ıslem q0 ∈ O(n2 log N ). Funkce hl je urˇcena ˇc´ısly q1 ∈ O(n2 ) a l ∈ O(q0 ). Funkce g je urˇcena n + 1 ˇc´ısly velikosti O(q1 ). Tedy zadán´ı f vyˇzaduje pamˇet o velikosti O(log n + log log N + n log n) = O(n log n + log log N ).

40

Lze ˇr´ıct, ˇze poˇzadavek 4) je splnˇen. V´ ypoˇcet φq0 vyˇzaduje ˇcas O(n3 log n log N ). V´ ypoˇcet hl vyˇzaduje ˇcas O(n(n2 log N )) = O(n3 log N ) (pouˇzité univerzum je {0, 1, . . . , q0 }). V´ ypoˇcet g vyˇzaduje ˇcas O(nn2 ) = O(n3 ) (zde univerzum je {0, 1, . . . , q1 }). Celkovˇe, v´ ypoˇcet f vyˇzaduje ˇcas O(n3 log n log N ). Lze pouˇz´ıt i pravdˇepodobnostn´ı algoritmy pro nalezen´ı g, hl a φq0 . Pak haˇsujeme do tabulky s ménˇe neˇz 9n ˇrádky, ale oˇcekávan´ y ˇcas pro nalezen´ı f je O(n log n(log n + log log N )). Tuto metodu navrhli Fredman, Koml´ os a Szemerédi.

41

Pˇredn´ aˇska 6 Nev´ yhody navrˇzené metody: Navrˇzená metoda pracuje pro m < 3n, ale nezajist´ı m = n. Lze ˇr´ıct, ˇze pamˇeˇt je efektivn´ı vyuˇzitá? Existuje metoda, která by umoˇznila návrh perfektn´ı haˇsovac´ı funkce pro m = n? Z v´ ysledk˚ u pro (N, m, n)-perfektn´ı soubory funkc´ı plyne existence (N, n, n)perfektn´ıho souboru pro nN > en+ln(n) ln(N ). Zm´ın´ıme se orientaˇcnˇe o parametrizované metodˇe, která navrhuje perfektn´ı haˇsovac´ı funkci pro S ⊆ U a pro m = |S|. Parametr bude pˇrirozené ˇc´ıslo r, které urˇcuje, jaké hypergrafy jsou uˇzity pˇri konstrukci funkce. Proto nejdˇr´ıve pˇripomeneme pár definic. Dvojice (X, E), kde X je mnoˇzina a E je systém r-prvkov´ ych podmnoˇzin X, se naz´ yv´ a yvaj´ı hrany r-hypergrafu. Cyklus je hypergraf (X, E), kde r-hypergraf. Prvky v E se naz´ kaˇzd´ y vrchol leˇz´ı alespoˇ n ve dvou r˚ uzn´ ych hranách. Naopak r-hypergraf (X, E) se naz´ yv´ a acyklick´ y, kdyˇz ˇzádn´ y jeho podhypergraf nen´ı cyklus. Nyn´ı pop´ıˇseme metodu, která je rozdˇelena do dvou krok˚ u. Je dáno S ⊆ U takové, ˇze |S| = n. Krok 1) Mˇejme r-hypergraf (V, E), kde |E| = n. Nalezneme zobrazen´P ıg :V − → {0, 1, . . . , m− r 1} takové, ˇze funkce h : E − → {0, 1, . . . , m − 1} definovaná h(e) = i=1 g(vi ) mod m, kde e = {v1 , v2 , . . . , vr }, je prostá (m´ısto sˇc´ıtán´ı modulo m m˚ uˇzeme pouˇz´ıt libovolnou grupovou operaci na mnoˇzinˇe {0, 1, . . . , m − 1}). Pro acyklick´ y r-hypergraf lze funkci g zkonstruovat následuj´ıc´ım postupem. Zvol´ıme bijekci h : E − → {0, 1, . . . , m − 1} a pak definujeme g následovnˇ e : kdyˇ z e = {v , v , . . . , v } a g(v ) je definov´ ano pro i = 2, 3, . . . , r, pak g(v1 ) = 1 2 r i Pr h(e) − i=2 g(vi ) mod m. Protoˇze pro kaˇzd´ y acyklick´ y r-hypergraf existuje vrchol, kter´ y leˇz´ı v jediné hranˇe, lze tento postup pouˇz´ıt ke konstrukci g pomoc´ı indukce (a tedy m´ ame algoritmus pro konstrukci g). Krok 2) Nalezneme r funkc´ı f1 , f2 , . . . , fr : S − → V takov´ ych, ˇze (V, E), kde E = {{f1 (x), f2 (x), . . . , fr (x)} | x ∈ S}, je acyklick´ y r-hypergraf. Autoˇri dok´ azali, ˇze nejvhodnˇejˇs´ı alternativa je, kdyˇz zobrazen´ı f1 , f2 , . . . , fr jsou náhodná zobrazen´ı náhodnˇe zvolená. Bohuˇzel taková zobrazen´ı neum´ıme zkonstruovat, ale autoˇri ukázali, ˇze pro tyto u ´ˇcely lze pouˇz´ıt náhodn´ y v´ ybˇer funkc´ı z nˇejakého c-univerzáln´ıho souboru funkc´ı. Autoˇri ukázali, ˇze jejich algoritmus vyˇzaduje O(rn+|V |) ˇcasu a O(n log n+r log |V |) pamˇeti. Tento metapostup navrhli Majewski, Wormald, Havas a Czech (1996). Pro praktické pouˇzit´ı je problematická reprezentace r-hypergrafu a i náhodná volba funkc´ı f1 , f2 , . . . , fr (viz pˇredchoz´ı diskuze o c-univerzalitˇe). Z poˇzadavk˚ u na perfektn´ı haˇsovac´ı funkci je opˇet problémem splnˇen´ı poˇzadavku 4). Nev´ım, jak je uvedená metoda prakticky pouˇzitelná a zda se nˇekde pouˇz´ıvá.

42

Metoda navrˇzená Fredmanem, Komlosem a Szemeredim nepodporuje operaci INSERT. To vedlo k navrˇzen´ı modifikace, která by INSERT podporovala. Navrˇzená metoda je kombinac´ı metody Fredmana, Komlose a Szemerediho s metodou, která ˇreˇs´ı pˇreplnˇen´ı, a obecnou metodou dynamizace vyhledávac´ıho problému (viz letn´ı semestr). Operace DELETE realizujeme principem faleˇsného DELETE. Popis reprezentace: Je dána konstanta c taková, ˇze 0 < c < 1, a funkce σ takov´ a, ˇze σ(n) ∈ Θ(n). Reprezentovaná mnoˇzina S ⊆ U = {0, 1, . . . , N − 1} taková, ˇze |S| = n. Dána ˇc´ısla q ˇ i = 0 a n ≤ q, nebo i > 0 a 2i−1 q ≤ n ≤ 2i q. Zvol´ıme ˇc´ıslo a ∈ a i taková, ˇze bud {1, 2, . . . , N − 1} takové, ˇze σ(2i q)−1 X (bai ) < n i=0

(zde uvaˇzujeme funkce ha (x) = (ax mod N ) mod σ(2i q) a modifikac´ı pˇredchoz´ıho postupu dostaneme, ˇze existuje funkce σ taková, ˇze alespoˇ n polovina a splˇ nuje tuto nerovnost). qi Pro kaˇzdé i je dáno qi takové, ˇze 2 ≤ |Si | ≤ qi pro kaˇzdé i = 0, 1, . . . , σ(2i q) − 1, kde Si = {s ∈ S | ha (s) = i}. Poloˇz´ıme si = 2qi (qi − 1). Pˇredpokládáme, ˇze je splnˇeno σ(2i q)−1

(∗)

X i=0

si ≤

32(2i q)2 + 4(2i q) σ(2i q)

a pro kaˇzdé i = 0, 1, . . . , σ(2i q)−1 je zvoleno ai takové, ˇze funkce hai (x) = (ai x mod N ) mod qi je perfektn´ı pro Si . Kaˇzdá mnoˇzina Si je uloˇzena do tabulky s si ˇrádky. Dále je uloˇzena promˇenná count taková, ˇze 0 ≤ count ≤ (1 + c)2i q. Neformáln´ı popis operac´ı: Operace INSERT(x). Kdyˇz x nen´ı prvkem mnoˇziny S a |Si |+1 > qi nebo count ≥ (1+c)2i q, pak pˇridáme x do S a nalezneme celou novou reprezentaci. Kdyˇz x nen´ı prvkem mnoˇziny S a |Si | + 1 ≤ qi a count < 2i q, pak spoˇc´ıtáme i = ha (x) a vloˇz´ıme x do tabulky reprezentuj´ıc´ı Si . Pokud na m´ıstˇe hai (x) je oznaˇcen´ y prvek nebo pokud je m´ısto prázdné, vloˇz´ıme tam x a odstran´ıme oznaˇcen´ı. Pokud tam je nˇejak´ y prvek Si , pak nalezneme nové ai takové, aby hai bylo perfektn´ı pro mnoˇzinu Si ∪ {x}, a spoˇc´ıtáme reprezentaci mnoˇziny Si ∪ {xi } vzhledem k nové funkci hai (pˇritom odstran´ıme oznaˇcené prvky). Zvˇetˇs´ıme count o 1. DELETE(x). Kdyˇz x ∈ S, pak oznaˇc´ıme x. Kdyˇz count ≥ (1 + c)2i q, pak nalezneme celou novou reprezentaci, jinak zvˇetˇs´ıme count o 1. Nová reprezentace: Vytvoˇr´ıme seznam prvk˚ u v S (odstran´ıme oznaˇcené prvky). Nalezneme ˇ ˇc´ıslo i takové, aby bud i = 0 a |S| ≤ q, nebo 2i−1 q ≤ |S| ≤ 2i q, pak nalezneme a takové, aby platilo (*). Nalezneme Si = {s ∈ S | ha (s) = i}. Poloˇz´ıme qi = 2|Si | a nalezneme ai takové, aby hai bylo perfektn´ı pro Si , a spoˇc´ıtáme reprezentaci Si pomoc´ı hai . Poloˇz´ıme count = 0. Uvedená metoda vyˇzaduje O(n) prostoru, operace MEMBER vyˇzaduje O(1) ˇcasu v nejhorˇs´ım pˇr´ıpadˇe a oˇcekávaná amortizovaná sloˇzitost operac´ı INSERT a DELETE je také O(1). Dokonce byly nalezeny doln´ı odhady, které ukazuj´ı, ˇze uvedená metoda je optim´ aln´ı.

43

Extern´ı haˇsov´ an´ı ˇ s´ıme jin´ Reˇ y problém – uloˇzen´ı dat na extern´ı pamˇeˇt. Hlavn´ı problém – minimalizovat pˇr´ıstup na extern´ı pamˇeˇt. Pˇredpoklady: Extern´ı pamˇeˇt je rozdˇelena na stránky, kaˇzdá stránka obsahuje b poloˇzek (dat) (pˇredpokládáme, ˇze b > 1, jinak to nemá smysl). Vˇzdy v jednom kroku naˇcteme celou stránku do intern´ı pamˇeti nebo celou stránku v intern´ı pamˇeti v jednom kroku zap´ıˇseme na extern´ı medium. Tyto operace jsou ˇrádovˇe pomalejˇs´ı neˇz oprace v intern´ı pamˇeti. Náˇs c´ıl: Nalézt zp˚ usob ukládán´ı dat do stránek extern´ı pamˇeti, aby se minimalizoval poˇcet operac´ı s extern´ı pamˇet´ı. Pˇredpokládejme, ˇze h : U − → {0, 1}∗ je prostá funkce taková, ˇze délka h(u) je stejn´ a pro vˇsechny prvky univerza U . Oznaˇcme k délku h(u) pro u ∈ U . Pak h je haˇsovac´ı funkce. Nechˇt S ⊆ U , pak pro slovo α délky menˇs´ı neˇz k definujme h−1 S (α) = {s ∈ S | −1 ˇ α je prefix h(s)}. Rekneme, ˇze α je kritické slovo, kdyˇz 0 < |hS (α)| ≤ b a pro kaˇzd´ y −1 ′ ′ vlastn´ı prefix α slova α plat´ı |hS (α )| > b. Pro kaˇzdé s ∈ S existuje právˇe jedno kritické slovo α, které je prefixem h(s). Definujme d(s) pro s ∈ S jako délku kritického slova, které je prefixem h(s) a (.S) = max{délka(α) | α je kritické slovo} = max{d(s) | s ∈ S}. Mnoˇzinu S reprezentujeme tak, ˇze je jednoznaˇcná korespondence mezi kritick´ ymi slovy a stránkami extern´ı pamˇeti slouˇz´ıc´ımi k reprezentaci S. Na stránce pˇr´ısluˇsej´ıc´ı kritickému slovu α je reprezentován soubor h−1 S (α). Problém: jak nalézt stránku kritického slova α? ˇ sen´ı: Adresáˇr je funkce, která kaˇzdému slovu α o délce d(S) pˇriˇrad´ı adresu str´ Reˇ anky pˇredpisem kdyˇz kritické slovo β je prefizem α, pak k α je pˇriˇrazena stránka koresponduj´ıc´ı s β, jinak je k α pˇriˇrazena stránka NIL – speciáln´ı prázdná stránka. −1 Korektnost: Pro r˚ uzná kritická slova β a γ plat´ı h−1 zdé S (β) ∩ hS (γ) = ∅, a tedy pro kaˇ slovo α délky d(S) existuje nejv´ yˇse jedno kritické slovo, které je prefixem α. Kdyˇz α je slovo délky d(S), pak nastane jeden z tˇechto tˇr´ı pˇr´ıpad˚ u: −1 e slovo β, které je prefixem α; (1) h−1 S (α) 6= ∅, pak 0 < |hS (α)| ≤ b a existuje kritick´ ′ ′ (α) = ∅ a existuje prefix α slova α takov´ y , ˇ z e o < |h−1 (2) h−1 S S (α )| ≤ b, pak existuje kritické slovo, které je prefixem α′ (a tedy také prefixem α); ˇ h−1 (α′ ) = ∅ nebo |h−1 (α′ )| > b zd´ y prefix α′ slova α plat´ı bud (3) h−1 S S S (α) = ∅ a pro kaˇ (pak k α je pˇriˇrazena stránka NIL.

Mˇejme slovo α o délce d(S). Oznaˇcme c(α) nejkratˇs´ı prefix α′ slova α takov´ y, ˇze str´ anka pˇriˇrazená slovu β o délce d(S), které má α′ za prefix, je stejná jako stránka pˇriˇrazen´ a α. −1 Vˇsimnˇeme si, ˇze kdyˇz hS (α) 6= ∅, pak c(α) je kritické slovo. Plat´ı silnˇejˇs´ı tvrzen´ı, které tvrd´ı, ˇze následuj´ıc´ı podm´ınky jsou ekvivalentn´ı: (1) stránka pˇriˇrazená slovu α je r˚ uzná od NIL; (2) c(α) je kritické slovo; (3) nˇejak´ y prefix α je kritické slovo.

44

Vˇsimnˇeme si, ˇze znalost adresáˇre umoˇzn ˇuje nalézt slovo c(α) pro kaˇzdé slovo o délce d(S). Lineárn´ı uspoˇrádán´ı na slovech délky n nazveme lexikografické, kdyˇz α < β, právˇe kdyˇz α = γ0α′ a β = γ1β ′ pro nˇejaká slova γ, α′ a β ′ . Lexikografické uspoˇrádán´ı vˇzdy existuje a je jednoznaˇcné. Reprezentace adresáˇre: Je to seznam adres stránek o délce 2d(S) takov´ y, ˇze adresa na i-tém m´ıstˇe odpov´ıdá i-tému slovu délky d(S) v lexikografickém uspoˇrádán´ı. Pˇr´ıklad: U je mnoˇzina vˇsech slov nad {0, 1} o délce 5, h je identická funkce a b = 2. Reprezentujme mnoˇzinu S = {00000, 00010, 01000, 10000}. Pak d(00000) = d(00010) = d(01000) = 2, d(10000) = 1, kritická slova jsou 00, 01 a 1 a adresáˇr je (m´ısto adresy str´ anky uvedeme mnoˇzinu, která je na této stránce uloˇzena) 00 7→ {00000, 00010},

01 7→ {01000},

10 7→ 11 7→ {10000}.

Tedy c(00) = 00, c(01) = 01 a c(10) = c(11) = 1. Kdyˇz odstran´ıme prvek 10000, pak 1 pˇrestane b´ yt kritické slovo a adresáˇr bude m´ıt tvar 00 7→ {00000, 00010},

01 7→ {01000},

10 7→ 11 7→ NIL .

Zase plat´ı c(00) = 00, c(01) = 01 a c(10) = c(11) = 1. V adresáˇri je také uloˇzeno d(S). Slovn´ı popis operac´ı. Pˇredpokládáme, ˇze adresáˇr je uloˇzen v extern´ı pamˇeti na jedné str´ ance. MEMBER(x) 1) Spoˇc´ıtáme h(x) a nat´ ahneme adresáˇr do intern´ı pamˇeti. Vezmeme prefix α slova h(x) o délce d(S) a nalezneme adresu stránky pˇr´ısluˇsej´ıc´ı k α. Kdyˇz je to stránka NIL, pak x ∈ /S a konec, jinak pokraˇcujeme krokem 2). 2) Nat´ ahneme stránku pˇr´ısluˇsej´ıc´ı k α do intern´ı pamˇeti. Prohledáme ji a pokud neobsahuje x, pak x ∈ / S a konec. Kdyˇz obsahuje x, pak provedeme poˇzadované zmˇeny a str´ anku uloˇ z´ıme do extern´ı pamˇeti na jej´ı p˚ uvodn´ı m´ısto. Konec. INSERT(x) 1) Spoˇc´ıtáme h(x) a nat´ ahneme adresáˇr do intern´ı pamˇeti. Vezmeme prefix α slova h(x) o délce d(S) a nalezneme adresu stránky pˇr´ısluˇsej´ıc´ı k α a slovo c(α). Kdyˇz stránka pˇriˇrazen´ a k α je NIL, pokraˇcujeme krokem 3), v opaˇcném pˇr´ıpadˇe pokraˇcujeme krokem 2). 2) Nat´ ahneme stránku pˇriˇrazenou slovu α. Kdyˇz x je uloˇzeno na této stránce, pak skonˇc´ıme. Kdyˇz x nen´ı na této stránce, pak tam pˇridáme slovo x. Pokud na stránce je nejv´ yˇse b prvk˚ u, pak uloˇ z´ıme stránku na jej´ı p˚ uvodn´ı m´ısto a skonˇc´ıme. Kdyˇz na stránce je v´ıce neˇz b prvk˚ u, pak nalezneme nová kritická slova, která nám stránku rozdˇel´ı, a vytvoˇr´ıme dvˇe stránky – jednu uloˇ z´ıme na m´ısto p˚ uvodn´ı stránky a druhou uloˇ z´ıme na novou str´ anku. Pokraˇcujeme krokem 4). 3) Vytvoˇr´ıme v intern´ı pamˇeti novou stránku, která obsahuje x, nalezneme novou stránku v extern´ı pamˇeti a tam uloˇ z´ıme vytvoˇrenou stránku (vˇsem slov˚ um, která maj´ı c(α) za prefix, bude pˇriˇrazena tato stránka) a pokraˇcujeme krokem 4). 4) Nat´ ahneme opˇet adresáˇr do intern´ı pamˇeti, aktualizujeme adresy pˇriˇrazen´ ych str´ anek a pˇr´ıpadnˇe zvˇetˇs´ıme adresáˇr (to nastane, kdyˇz nˇejaké nové kritické slovo má délku vˇetˇs´ı neˇz d(S), pak nové d(S) je právˇe délka tohoto slova – obˇe kritická slova vzniklá v kroku 2) maj´ı stejnou délku). Aktualizovan´ y adresáˇr uloˇ z´ıme do extern´ı pamˇeti. Konec.

45

DELETE(x) 1) Spoˇc´ıtáme h(x) a nat´ ahneme adresáˇr do intern´ı pamˇeti. Vezmeme prefix α slova h(x) o délce d(S) a nalezneme adresu stránky pˇr´ısluˇsej´ıc´ı k α a slovo c(α). Kdyˇz stránka pˇriˇrazen´ a k α je NIL, pak skonˇc´ıme. Oznaˇcme β ′ slovo, které má stejnou délku jako c(α) a liˇs´ı se od c(α) pouze v posledn´ım bitu. Kdyˇz existuje slovo β délky d(S) takové, ˇze c(β) = β ′ , pak stránka pˇriˇrazená k β je kandidát. 2) Nat´ ahneme stránku pˇr´ısluˇsnou k slovu α do intern´ı pamˇeti. Kdyˇz tato stránka neobsahuje x, pak skonˇc´ıme. Kdyˇz tato stránka obsahuje x, pak odstran´ıme x z této str´ anky. Kdyˇz neexistuje kandidát nebo kdyˇz nová stránka a str´ anka kandidáta obsahuje v´ıce neˇz b prvk˚ u, pak novou stránku uloˇ z´ıme na jej´ı p˚ uvodn´ı m´ısto a skonˇc´ıme. 3) Kdyˇz nová stránka a stránka kandidáta maj´ı dohromady b prvk˚ u, pak nat´ ahneme stránku kandidáta do intern´ı pamˇeti. V intern´ı pamˇeti tyto stránky spoj´ıme do jedné a tuto stránku pak uloˇ z´ıme do extern´ı pamˇeti. 4) Nat´ ahneme adresáˇr, kde zaktualizujeme adresy stránek. Pokud jsme slouˇcili dvˇe str´ an′ ky, mus´ıme nalézt nové c(α) (je to nejkratˇs´ı prefix α slova α takov´ y, ˇze ke kaˇzdému slovu β o délce d(S), které má α′ za prefix, je pˇriˇrazena jedna z tˇechto adres: adresa str´ anky pˇriˇrazená k α, adresa stránky kandidáta, NIL) a kaˇzdému slovu o délce d(S), které m´ a nové c(α) za prefix, bude pˇriˇrazena adresa nové (spojené) stránky. Otestujeme, zda se adres´ aˇr nem˚ uˇze zkrátit (to nastane, kdyˇz adresy stránek pˇriˇrazené (2i + 1)-´ımu slovu a (2i + 2)-ému slovu o délce d(S) jsou stejné pro vˇsechna i, pak se tato slova spoj´ı a d(S) se zmenˇs´ı o 1). Upraven´ y adresáˇr uloˇ z´ıme. Konec. Následuj´ıc´ı vˇeta ukazuje, ˇze jsme náˇs hlavn´ı c´ıl splnili. Vˇ eta. Operace MEMBER vyˇzaduje nejv´ yˇse tˇri operace s extern´ı pamˇet´ı. Operace INSERT a DELETE vyˇzaduj´ı nejv´ yˇse ˇsest operac´ı s extern´ı pamˇet´ı. V naˇsem pˇr´ıkladu provedeme operaci INSERT(00001). Po pˇridán´ı prvku stránka p˚ uvodnˇe pˇriˇrazená k slovu 00 vypadá takto {00000, 00001, 00010}. Tuto stránku rozdˇel´ıme na str´ anky {00000, 00001} a {00010}. Pˇritom kritické slovo prvn´ı stránky je 0000 a druhé str´ anky je 0001. Takˇze d(S) = 4 a adresáˇr vypadá 0000 7→ {00000, 00001}, 0001 7→ {00010}, 0010 7→ 0011 7→ NIL, 0100 7→ 0101 7→ 0110 7→ 0111 7→ {0100}, 1000 7→ 1001 7→ 1010 7→ 1011 7→ 1100 7→ 1101 7→ 1110 7→ 1111 7→ {10000}. To znamená, ˇze kromˇe adresy 00 se ostatn´ı slova rozdˇelila na ˇctyˇri slova, ale adresy z˚ ustaly stejné. Jen u slova 00 vzniklá slova dostala r˚ uzné adresy. V p˚ uvodn´ım pˇr´ıkladu provedeme operaci DELETE(01000). Pak kandidát je 00 a po odstranˇen´ı prvku 01000 nastane spojen´ı tˇechto dvou stránek. Po aktualizaci adres dostane adresáˇr tvar 00 7→ 01 7→ {00000, 00010}, 10 7→ 11 7→ {10000} Pak k prvn´ımu a druhému slovu je pˇriˇrazena stejná stránka a stejnˇe tak k tˇret´ımu a ˇctvrtému slovu. Takˇze m˚ uˇzeme adresáˇr zmenˇsit. Pak d(S) = 1 a adresáˇr má podobu 0 7→ {00000, 00010}, 1 7→ {10000}. Vzniká ot´ azka, jak je tato metoda efektivn´ı. Hlavnˇe jak efektivnˇe vyuˇz´ıvá pamˇeˇt. Plat´ı

46

Vˇ eta. Pˇri reprezentaci mnoˇziny S o velikosti n je oˇcek´ avan´ y poˇcet pouˇzit´ ych str´ anek e 1+ 1b a oˇcek´ avan´ a velikost adres´ aˇre b ln 2 n .

n b ln 2

Prvn´ı tvrzen´ı ˇr´ıká, ˇze oˇcekávan´ y poˇcet prvk˚ u na stránce je b ln 2 ≈ 0.69b. Tedy zaplnˇeno je asi 69% m´ıst. Tento v´ ysledek nen´ı pˇrekvapuj´ıc´ı a je akceptovateln´ y. Horˇs´ı je to s adres´ aˇrem, jak ukazuje následuj´ıc´ı tabulka

velikost S 2 10 50 100

105 6.2 · 107 1.2 · 105 9.8 · 103 4.4 · 103

106 1.96 · 108 1.5 · 106 1.0 · 106 4.5 · 104

108 1.96 · 1011 2.4 · 108 1.1 · 108 4.7 · 106

1010 1.96 · 1014 3.9 · 1010 1.2 · 1010 4.9 · 108

kde jednotlivé ˇrádky odpov´ıdaj´ı hodnotám b uveden´ ych v prvn´ım sloupci. Protoˇze oˇcek´ avan´ a 1 avat, velikost adresáˇre se zvˇetˇsuje rychleji neˇz lineárnˇe (exponent u n je 1+ b ), tak nelze oˇcek´ ˇze tuto metodu lze vˇzdy pouˇz´ıt. V´ ypoˇcty i experimenty ukazuj´ı, ˇze pouˇzitelná je do velikosti |S| = 1010 , kdyˇz b ≈ 100. V tomto rozmez´ı je nár˚ ust adresáˇre jen kolem 5%. Pro vˇetˇs´ı n je tˇreba, aby b bylo jeˇstˇe vˇetˇs´ı.

Základní problém: Reprezentace množin a operace s nimi. V řadě úloh a algoritmů je tento

Recommend Documents