Státnice - Hašování I2/Universal

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
Hašování - Operace: SEARCH, INSERT, DELETE
Univerzum klíčů U a K⊆U je množina použitých klíčů |K| = n
Hašovací funkce h: U→{0,1,..,m−1} mapuje univerzum U do(menší) tabulky T [0,..,m−1], |U| > m
Kolize je situace: h(ki) = h(kj), pro ki≠kj; ki,kj∈K
Faktor naplnění: α = n/m

Založeno na MIT přednášce v AJ popisující princip universálního a perfektního hašování. Lepší pro pochopení základu, než se zmateně dívat na 10 stránek vzorečků :). slidy zapisky

abychom si vylepšili naše šance že fce h bude fungovat dobře, budeme jí brát náhodně z obecnější (konečné) množiny H fcí mapujících universum klíčů U do tabulky {0,1,..,m−1}

1-universalni system
  • tj. H ⊆ { h | h: U → {0,1,..,m−1} }
  • třída fcí H je c-univerzální - pokud má v tabulce velké m maximálně $ \frac{c |H|}{m} $ kolizních fcí ∀ dva různé prvky z univerza
    • tj. ∀xyU: |{hH: h(x)=h(y)}| ≤ $ \frac{c |H|}{m} $
    • 💡 tj. čím menší c tím méně kolizí a fce jsou "různorodější"

Konstrukce 1-univerzálního H (MIT verze)[editovat | editovat zdroj]

  1. podmínka: mějme prvočíslo m
  2. pre-process: klíč k se rozdělí na r+1 číslic, tedy k = ⟨k₀,k₁,...,kᵣ⟩; kᵢ ∈ {0,1,...,m-1}.
    • 💡 tj. klic k zapíše v číselné soustavě o základu m
  3. náhodnost: vezmeme náhodně a = ⟨a₀,a₁,...,aᵣ⟩; aᵢ ∈ {0,1,...,m-1}
  4. hashovací fce: hₐ(k)=Σᵢ₌₀…ᵣ(akᵢ) mod m
    • 💡 tj. H = {hₐ}
Dk (zkonstruované H je univerzální):[editovat | editovat zdroj]

a) Celkový počet hashovacích fcí v třídě: | H |=mʳ⁺¹ protože každé z r+1 aᵢ může nabývat m možných hodnot

b) Počet hashovacích funkcí které pro různá x a y kolidují:

Buď x=⟨x₀,x₁,...,xᵣ

y=⟨y₀,y₁,...,yᵣ⟩ různé klíče (liší se aspoň v jedné číslici).

BÚNO, předpokládejme že x a y se liší v první číslici; na pozici 0.

Pokud x a y kolidují, pak: hₐ(x) = hₐ(y) ⇒ (Σ axᵢ) mod m = (Σ ayᵢ) mod m

upravíme na:  

⇒ Σ axᵢ ≡ Σayᵢ (mod m)

⇒ Σ aᵢ (xᵢ - yᵢ ) ≡ 0 (mod m)

a₀ ( x₀ - y₀ ) + Σ aᵢ (xᵢ - yᵢ ) ≡ 0 (mod m)

[Note: the above step applies because m is prime and x₀y₀, therefore ( x₀ - y₀ )⁻¹ exists]

a₀ = ( ( -Σ aᵢ (xᵢ - yᵢ )) ( x₀ - y₀ )⁻¹ ) mod m

Z předchozího vyplývá že jakmile jsou vybrány hodnoty a₁,...,aᵣ , přesně 1 hodnota a₀ způsobí kolizi x a y. Spočítáním možných hodnot a₀ způsobujících kolize x a y nám dává počet hₐ z H působících kolize x a y.

To se rovná počtu možných kombinací a₁,...,aᵣ což je mʳ protože každá z r číslic má m možných hodnot.

Část a) nám dala celkový počet hashovacích fcí: mʳ⁺¹

Část b) nám dala počet fcí způsobujících kolize mezi x a y: mʳ

Tedy počet fcí způsobujících kolize ve třídě je: mʳ = mʳ⁺¹/m = 1|H|/m , a tedy H je 1-univerzální.

Perfektní hashování (🎓)[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • Hašování (2013, Kolman) - Mal som rozprávať o hašování všeobecne, čo to je, prečo to riešime a pridať čo prináša univ. a perfektné hašovanie. Vydal som zo seba nejaký všeobecný úvod, spomenul som štandardné spôsoby riešenia kolízii a čím sa od seba odlišujú (bez presného popisu algoritmov), spomenul som univerzálne hašovanie a perfektné hašovanie. Spolu so zopár otázkami na univerzálne hašovanie (c-univerzálny systém) to bohato stačilo.
  • Perfektni hashovani (2013, Hladik) - nejake odhady velikosti systemu (Koubkovi materialy), konstrukce a idee podle prednasky z MIT (tak jak tu nekde je zmineno v jinem vlakne)
  • univerzalni a perfektni hasovani (2011 , postarsi pan, ktereho jsem nikdy predetim nevidel) - A hned po ranu...bum prask...univerzalni a perfektni hasovani, abychom se nenudili. Tady mi hodne pomohla prednaska z MIT http://videolectures.net/mit6046jf05_leiserson_lec08/ a to, ze neznal koubkovy definice a konstrukce. No, neco jsem tam tvoril, obcas vypadal zmatene, obcas ze to tak nejak zna taky...nakonec vypadal spokojene


zkazky I1/4  
  • perfektní Hashování (2014, MJ) - popsal jsem 1-univerzální systém, jak se vytvoří a jak ho použiji na perfektní hashování. To jsem popsal a nastínil jak se to spočítá.
  • perfektní hashování (2011, Majerech) - Předvedl jsem konstrukci z Leisersonovy přednášky na MIT a spočetl jsem že očekávaná prostorová složitost je O(n), ještě jsem byl ochotný počítat horní mez pro pravděpodobnost kolize na druhé úrovni, ale Majerech chtěl, abych zkusil recyklovat výpočet z té první. Ukázalo se, že to moc nejde, ale o to bylo zkoušení zajímavější:). Do výpočtů lehce šťoural, ale ne nějak hnidopišsky, spíš asi šlo o to zjistit, jestli vím, co počítám.
perfektní hashování - pomocí 2 univerzálních, v 1.tabulce jsou parametry pro 2.univerzální hashovací funkci (z konstrukce univerzálního výše)

známe množinu klíčů předem ⇒ můžeme vytvořit hashování bez kolizí ( MEMBER v O(1) ), ale má to svojí cenu: tabulka bude statická (INSERT je velmi obtížný)

  • Idea: 2-úrovňové univerzální hashování, s kolizemi na 1. ale bez kolizí na 2.úrovni
  • hashovací funkce h je perfektní pro množinu S, pokud nemá kolize ∀ dva různé prvky z S
    • 💡 tj. ∀xyS: h(x) ≠ h(y)
    • Soubor funkcí H: U = {0,1,..,N−1} → {0,1,..,m−1} je (N,m,n)-perfektní, pokud ∀S U takové, že |S| = n existuje hH perfektní pro S (💡 tj. bez kolizí).

Konstrukce perfektního hashování (MIT verze)[editovat | editovat zdroj]

Velikost level-1 tabulky dáme na m = n a velikost level-2 tabulky mᵢ = nᵢ² . Celkem budeme potřebovat O(n) paměti.

Věta (#kolizí n čísel pro tabulku velkou n²)H je třída univ.fcí pro tabulku velikosti m = n². Pak kdyz pouzijeme nahodnou funkci z H na zahasovani n cisel, tak očekávaný počet kolizí je menši nez 1/2.

Dk (přímo):

Z definice univerzálnosti, pravděpodobnost kolize 2 klíčů při fci h je $ \frac{1}{m} = \frac{1}{n²} $ .

Protože máme $ \binom{n}{2} $ párů klíčů co mohou kolidovat, předpokládaný počet kolizí je:

$ \binom{n}{2} \frac{1}{n²} = \frac{n(n-1)}{2} \frac{1}{n²} = \frac{n-1}{2n} = \frac{1-\frac{1}{n}}{2} < \frac{1}{2} $