Univerzálne triedy hashovacích funkcií
Veronika KrajCová, Martin KvoCka, Marek Trgina
20.5.2010
1 Úvod
Rozne vstupy pre program moZeme vnímat' ako prvky z triedy probie-mov, priCom výstupom programu je spravne rieSenie daneho problému. Ak hovoríme o priemernom výkone programu, spravidla priemerujeme jeho výsledky cez triedu probiemov, ktore program riesi. Pani Gill, Rabin, Strassen a Solovay na niektorych triedach problemov pouZili iny prístup. Navrhli, aby si program nahodne vybral algoritmus z triedy algoritmov, ktorym bude problem riesit'. Tymto sposobom boli schopny ohranicit' priemerny vykon triedy algoritmov pre najhorsí mozny vstup. Tento priemer na najhorsom vstupe moze byt'lepsí nezz vykon l'ubovol'neho konkrétneho algoritmu na tomto vstupe. Tento prístup prekonava niektoré problemy, ako:
1. Klasicka analyza (priemerovanie cez triedu vstupov) musí poätat's distribúciou vstupov. Tieto predpoklady vsak v urätych prípadoch nemusia platit'.
2. Dosledkom (1) je zze nemozme klasicky analyzovaťpriemerny vykon podprocedury nezavisle na hlavnej casti programu, pretozze hlavna cast'môze rozhodit'distribúciu dat.
3. Ak programu predlozzíme najhorsí mozny vstup, tak neexistuje spôsob ako sa vyhnut'jeho slabej vykonnosti. Avsak, pri pouzzití algoritmu z triedy algoritmov by sme mohli detekovat', ze je pomaly na danom vstupe, a zvolit'iny algoritmus.
2
V nasledujúcom texte ukážeme použitie tohto prístupu pri hashovaní. Ukážeme že ak je trieda funkcií zvolená správne, potom priemerný výkon programu na ľubovoľnom vstupe bude aspon taký dobrý ako jednotliva funkcia, žvolena s vedomím konkrétneho vstupu. Taktiež predvedieme niektoré triedý hashovacích funkcií ktoré žaruCia, že každa vžorka ž priestoru vstupov bude rovnomerne distribuovana dostatocným poctom funkcií tak abý kompenžovala slabý výkon algoritmu v prípade nestastnej volbý funkcie.
2   Univerzálne triedy hash funkcií
Znacenie:
Vsetký hashovacie funkcie budu mapovat'množinu A do B, pricom vždý bude | A | > | B |. A budeme nažývat' množinou kl'ucov, B žas množinou indexov. Nech f je hash funkcia a ôf (x, y) je 1 ak x = y a f (x) = f (y), inak 0. Teda ôf (x, y) je 1 ak x a ý stí rožne prvký A ktoré sa mapuju na rovnaku hodnotu pomocou funkcie f. Ak f, x, y nahradíme množinou, potom sätavame cež vsetký prvký v množine. Teda, ak H je kolekcia hash funkcií, x G A a S C A, potom Ôh(x, S) žnamena:
If GH1yGSôf (x y)
Vlastnosti univeržalných tried: Nech H je trieda funkcií ž A do B. O H vravíme že je universal2 ak pre
vsetký x, y ž A, ôH (x, y) <     .To žnamena, že H je universal2 ak žiaden
par rožných kl'ucov nie je mapovaný na tie iste indexý viac než jedno | B | -tinou funkcií. Tvrdenie 1:
Pre každu kolekciu hash funkcií (nie nutne universal-i) existuje x, y G A take že
| H|   | H|
Tvrdenie 2:
Nech x je l'ubovol'ný prvok A a S podmnožina A. Nech f je funkcia žvolena nahodne ž universal2 triedý funkcií (s rovnakou pravdepodobnosťou). Potom ocakavaný pocet prvkov ž S s ktorými x koliduje, teda ôf (x, S), je
3
Zaujíma nás použitie týchto funkcii pri operáciách ukladania a získavania dát. Ak mame sekvenciu R požiadaviek (vloženie alebo výber) do nejakej databaze, a hash funkciu f, potom definujeme cenu R vzhľadom na f ako C( f, R), teda ako sumu cien jednotlivých požiadaviek. Cena jednotlivej požiadavky zodpovedajúcej prvku x je jedna plus pocet rožných predtým vložených y pre ktore f (x) = f (y).
Tato funkcia cený odraža najhorsiu cenu vloženia alebo najdenia prvkov v uložisti a navratovu schemu v ktorej každý prvok B je asociovaný so spojovaným žožnamom, a prvok x je uložený v tomto žožname asociovaný s
f(x).
Nasledujúci teorém dava pekný odhad na occakavantí cenu pomocou universal2 tried hashovacích funkcií používajucich spojovaný žožnam na riesenie kolížií.
Tvrdenie 3:
Nech R je sekvencia r požiadaviek ktore žahrnaju k vložení. Dalej nech H je universal2 trieda hashovacích funkcií. Potom ak žvolíme f nahodne ž H, ocakavana cena je:
C(f, R) < r(1 + |B)
Specialný prípad tohto tvrdenia je ak vel'kost'k je žhruba rovnaka B, potom je ocakavana cena 2r. Vsimnite si, že toto linearne ohraniccenie platí pre ľubovoľní! sekvenciu požiadaviek, nie len pre "priemermi" požiadavku. Vo vacsine aplikacií vsak existuje horna hranica na pocet prvkov ktore je možno uložit', teda B može být'vhodne žvolene. Ak žiadna horna hranica neexistuje, možme jej vel'kost'volit'dýnamický a žnovu prehashovat'ak sa voľba ukaže ako prílis mala. Rehashovanie totiž možme urobit'v linearnom ccase, niekedý aj real-time.
Možme ukažat', že ocakavana cena (spriemerovana cež hashovacie funkcie) ľubovoľnej požiadavký je praktický rovnaka ako ocakavana cena (spriemerovana cež možne požiadavký) ľubovoľnej jednotlivej hash funkcie aplikovanej na nahodnu požiadavku po nahodných vloženiach. Dovod je nasledovný: Nech a = |A| a b = |B|. Argument ž tvrdenia 1 implikuje že ak je f lubovoľna hash funkcia a x a y su žvolene nahodne ž A, tak pravdepodobnosť ôf (x, y) je > (1/b — 1/a). Potom teda pravdepodobnosť ôf (x, S) je > | S | (1/b — 1/a), kde S je nahodna podmnožina A ktora bola predtým uložena. Teda cena požiadavký je aspon 1 + | S|(1/b — 1/a).
Taktiež je možne ohraniccit' pravdepodobnosť že pre danu sekvenciu
4
požiadaviek R je výkon náhodne zvolenej funkcie horší než tolerovateľný na R. Kedže vieme že C (f, R) muší být'ašpon r, možme predpokladat'že ak k je žhruba rovnake ako | B|, pravdepodobnosť že C (f, R) > t — r je menej ako 1/(t — 1). Pre niektoré triedý hašhovacích funkcii je možne vývodit' odhad na štandardnU odchýlku alebo výššie momentý cený nahodne žv-olenej funkcie na konkrétnom R. Toto nam umožní žíškat'ovel'a lepší odhad toho že pravdepodobnosť C(f, R) bude vel'ka.
3   Niektoré universal2 triedy
Prva trieda universaÍ2 hašhovacích funkcií ktoru uvedieme je vhodna na použitie v šituaciach, ked' bitová ret'ažce reprežentujuce kluce je možne jednoducho našobit'pocítacom. Zoberme A = 0,1,a — 1 a B = 0,1, • • •, b — 1. Nech p je prvoäšlo take že p > a. Nech g je nejaka funkcia žo Zp do B, ktora co najprešnejšie mapuje rovnaký pocet prvkov Zp na každý prvok ž B. Formalne požadujeme |{y G Zp|g(y) = z}| < [p] pre všetký z G B.
Prirodžena voľba pre g je žvýšok modulo b. Ak b = 2k pre nejake k, toto predštavuje pošledných k bitov v binarnej reprežentacii y.
Nech m a n ští prvký Zp kde m = 0. Definujeme hmn : A — Zp ako hm,n(x) = (mx + n)modp. Potom definujeme fmin(x) = g(hmn(x)). Trieda H je množina {fm>n |m, n inZpm = 0}. Takato trieda H je universal2.
Algoritmý šu cašto analýžovane ža predpokladu že našobenie žaberie jednotku cašu a pocet našobení býva považovaný ža cenu algoritmu. Tento model je vhodný v prípadoch, ked'neexištuju operacie ktoré bý bolo možne výkonaťneohranicený pocet krat ža každe našobenie. Ked'je použíta trieda universal2 hašhovacích funkcií, pocet odkažov do pamate ža kazzduí požži-adavku je možne ohranicit' špriemerovaním nad všetkými funkciami v triede ako v tvrdení (3). Takže tento model je vhodný a hašhovacie funkcie v triede uvedenej výššie je v inom možne výkonat'ža koštantný caš. Takže v tomto modeli, pre ľubovoľní! šekvenciu požiadaviek ma algoritmuš linearnu Cašovll žložitošťvžladom k pocitu požžiadaviek.
Trieda universal2 popíšana výššie nie je vhodna v prípadoch ked' šu kluce príliš dlhe na to, abý ich bolo možžne našobit' použítím jednej inštrukcie. NašledujlUce tvrdenie dava špoošob akýým rožšírit' triedu funkcií pre dlhe kluce.
Tvrdenie 4:
5
Predpokladajme že \B\ je mocninou 2 a H je trieda funkcií z A do B taká, že pre každe i G B: \{ f G H\f (x) © f (y) = i}\ = ^, kde © znaCí operaciu XOR. Potom možme definovat' universal2 triedu hashovacích funkcií z AxA do B takto. Pre f, g G H definujeme Hfg ((x, y)) = f (x) © g( y). Potom tato nova trieda hashovacích funkcií J = {h f g \ f, g G H} je universal2 a zaroven splna podmienky v tomto tvrdení. Toto tvrdenie sa uplne nevzťahuje na universal2 triedu funkcií, ktora bola uvedena vyssie, a to preto ze H nie je mocninou 2 a preto ze pocet funkcií pre ktore platí f (x) © f( y) = 0, i.e.5H (x, y), je v skutocnosti mensí ako \ H\/\B\.
Nasleduje trieda funkcií, ktore nevyzaduju nasobenie, co moze byt' vyhoda v rôznych aplikaciach. Zoberme si A ako mnozinu i-cifernych císel o zaklade a a B ako mnozinu binarnych císel dlzky j. Potom \ A\ = oča\B\ = 2j. Nech M je trieda polí dlzky ia, ktorých prvky su binarne ret'azce dlzky j. Pre m G M, nech m(k) je binarny ret'azec ktory je k-ty prvok m, a pre x G A, nech xk je k-ta císlica x v bazi a. Definujeme
f m (x) = m(x\ + 1) © m(x\ + x2 + 2) +-----h (m(sumlk=1 xk + k)
Trieda H je mnozina {fm\m G M}. Tato trieda splna vlastnosti universal2. Pre dane B, kazda funckia v H ma linearnu casovu zlozzitost'vzhl'adom k dlzke kluca.
4 Záver
Programatori casto stravia dlhu dobu pri tom, aby odladili hashovacie funkcie pre aplikacie kde je kriticke dosiahnutie uniformneho rozlozze-nia. Dosiahnutie tohto ciela moze byt' zlozite, pretoze je potrebne aby ocľakavana vstupna mnozzina bola usporiadana takym spoosobom, zze to nespoosobí nedostatocny vykon hashovacej funkcie. Jednou z praktick-ych vlastností triedy universal2 funkcií je, ze sa v triede nachadza mnoho pouziteľnych funkcií. Jednoduchym nahodnym vyberom hashovacej funkcie z tejto triedy je mozne dosiahnuť uniformne rozlozzenie. A tym, ze sa pouzita funkcia mení pri kazdom vykonaní programu, je mozne dosiahnuť dobry vykon v priemernom prípade. Pouzitie universal2 tried dava moznosťdobrého odhadu medzí, v ktorych sa bude pohybovaťpriemerny vykon algoritmu pouzívajuceho hashovanie.
6
Literatüra
[1] Dilip V. Sarwate. A Note on Universal Classes of Hash Functions.. [cited 2010-5-14]. Available at: journal Information Processing Letters,
vol. 10
[2] George Markowsky, J.Lawrence Carter, Mark N. Wegman. Analysis ofuniversal class ofhash functions [online]. [cited 2010-5-14]. Available at: http://laptops.maine.edu/HashFunctions.pdf.
[3] Martin Dietzfelbinger and Friedhelm Meyer. A new universal class ofhash functions and dynamic hashing in real time . [cited 2010-5-14]. Available at: Lecture Notes in Computer Science, vol. 443/1990.
7