[[Soubor:Hashovani.png|thumb|466x466px|Hašování - Operace: SEARCH, INSERT, DELETE<br/> Univerzum klíčů U a K⊆U je množina použitých klíčů |K| = n <br/>

Hašovací funkce h: U→{0,1,..,m−1} mapuje univerzum U do(menší) tabulky T [0,..,m−1], |U| > m <br/>
Kolize je situace: h(k<sub>i</sub>) = h(k<sub>j</sub>), pro k<sub>i</sub>≠k<sub>j</sub>; k<sub>i</sub>,k<sub>j</sub>∈K <br/>

Faktor naplnění: α = n/m ]]

{{Sources| 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}

Soubor:Univerz.png

  • 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ě c∣H∣m\frac{c |H|}{m} kolizních fcí ∀ dva různé prvky z univerza

    • tj. ∀x≠y∈U: |{h∈H: h(x)=h(y)}| ≤ c∣H∣m\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)

  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)=Σᵢ₌₀…ᵣ(aᵢ kᵢ) mod m

    • 💡 tj. *H *= {hₐ}

Dk (zkonstruované ''H'' je univerzální):

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) ⇒ (Σ aᵢ xᵢ) mod m = (Σ aᵢ yᵢ) mod *m * {{collapse|upravíme na:|

⇒ Σ aᵢ xᵢ ≡ Σaᵢ yᵢ (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 <u>H</u><u> je 1-univerzální</u>.

Perfektní hashování (🎓)

{{zkazky|* 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

}}{{collapse|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.

}} Soubor:Hashovani%20perfect.jpg

známe množinu klíčů předem ⇒ můžeme vytvořit hashování <u>bez</u> 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. ∀x≠y∈S: 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 h ∈ H perfektní pro S (💡 tj. bez kolizí).

Konstrukce perfektního hashování (MIT verze)

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

{{theorem|1=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.|2=#kolizí n čísel pro tabulku velkou n²}}

Dk (přímo):

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

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

(n2)1n2=n(n−1)21n2=n−12n=1−1n2<12\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}