{{Sources| Založeno na , z různých zápisků k předmětu Datové struktury I, a výtahů k

09/10: Hašování: rešení kolizí, univerzální hašování, perfektní hašování. Mapování datových struktur do stránek vnejší pameti pocítace.

14/15: Hašování: rešení kolizí, univerzální hašování, perfektní hašování.

}} [[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í fce h: U→{0,1,..,m−1} mapuje univerzum U do(menší) tabulky T [0,..,m−1], |U| > m (pracuje v O(1))<br> Kolize je situace: h(ki) = h(kj), pro ki≠kj; ki,kj∈K<br>

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

'''Hašování: řešení kolizí''' (interní hashování) (7×🎓)

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

  • Hašování (2013, Majerech) - Vyjmenoval jsem předpoklady, základní typy hašování, očekávaná délka řetězce separovaných řetězců (kromě definice univerzálního hašování jediný vzoreček, který se po mně chtěl), základy univerzálního hašování, na perfektní už se nedostalo. Zkoušející byl Majerech - hodně šťoural, ale zajímaly ho praktické aspekty použití spíš než vzorečky (i když kolegu přede mnou dusili na definici nějakých vyhledávacích stromů).

  • Hashování, řešení kolizí, srovnání metod (2012, DB)

  • Reseni kolizi v hashovani a univerzalni hashovani (2012, Majerech) - Na uvod klasicky vycet ruznych reseni kolizi ("ten sklep v tom, jak ho popisujete, vam k nicemu nebude, podle me"), pak dlouhe paceni toho, ze se pri velkem load factoru da tabulka zvetsit (vubec me nenapadlo, ze je potreba to rict, ale M. byl chapavy a pockal si, az jsem se chytil za nos), pak povidani o rozdilu mezi randomizovanou slozitosti a ocekavanou slozitosti ("co kdyz budete mit robota nad pacientem, co z nej strika krev, bude vam tohle hashovani stacit?"), diskuse o doplneni RB stromu do jednotlivych bucketu a tak. Slabsi povahy by si mohly myslet, ze je to na vyhazov, ale to vubec neni pravda, M. je velmi inteligentni a korektni a i zkouseni je u nej prilezitost k vysvetleni zajimavosti. Bylo fajn, ze se neptal na algebraicke principy fungovani c-univerzalnich systemu, ale spis mu slo o porozumeni, jak to funguje a v cem je to dobre/spatne.

  • hashovanie a trie (2011, Dr. Zeman) - Nastastie taka prehladova otazka, kedze som ju odpovedal ako poslednu, tvoril som to pocas odpovedania, rozpisal som druhy hashovania, potom zmienil univerzalne (principy ~ ku kazdej S vyberieme nejaku fciu z H, H c-univerzalna, napisal som funkciu h_ab(x), a ze je c-univerzalna), perfektne hashovanie, opat som zacal ako to principialne funguje a v polovici som bol zastaveny a ze mam este o triach porozpravat, tak som opat vysvetlil princip, dalej ako sa to potom komprimuje (v style, potom vznechame tie uzly, kde nedochadza k plodnemu vetveniu, potom to mozeme zapisat do tabulky, tu do dvoch poli, etc), spokojnost

  • reseni kolizi v hashovani (2011, Koubek) - napsat vsechny algoritmy a porovnat je z hlediska pametove a casove narocnosti, prumerna delka retezcu, jak to ovlivni cachovani

  • přehled hašování (řešení kolizí) (2009)

  • Hashovani (2005,Kopecky) - Nahodil jsem ruzny strategie reseni kolizi (jen jak to funguje, zadny casy ani vypocty, ani to pak nechtel) + zvetsovani tabulky (takovyto prehashovani) - pak po me chtel jeste dynamizaci

}} v datovkách se bralo (a u státnic ze zkouší) hlavně In-memory hashování:

*celá tabulka je v paměti *každý poličko obsahuje jeden záznam

  • limitovaný prostor

'''Řetězení '''(Chaining)

[[Soubor:Hashovani chaining.png|thumb|563x563px|Hašování separovanými řetězci (chaining)

při kolizi vytvoříme v tabulce spojový seznam ]]

'''Separované řetězce''' (separate chaining)

Při kolizi vytvoříme v tabulce spojový seznam.

Paměťová náročnost je pro každý seznam O(1+l(i)), kde l(i) je délka toho seznamu.

Optimalizace: s uspořádanými separovanými řetězci - seznamy jsou uspořádány podle velikosti, rychlejší op.SEARCH (když dojdu v řetězci za místo, kde by byl hledaný prvek, můžu skončit).

Očekávaná délka řetězců:

  • stř.hodnota: E(l) = α = n / m

  • rozptyl: var(l) = n/m (1 - 1/m)

{{collapse|Dk (Očekávaná délka řetězců):|Pro odhad složitosti alogritmů předpokládáme, že: *Hashovací funkce h rozděluje data rovnoměrně

  • Sama reprezentovaná množina S je náhodný výběr z U s rovnoměrným rozdělením

Tyto předpoklady v praxi ale splněny být nemusí.

Pro odhad složitosti se počítá očekávaná délka řetězců. Označme délku <math> i\,\!</math>-tého řetězce jako <math> \mathbf{l}(i)\,\!</math>. Potom pravděpodobnost, že tento řetězec má délku <math> l\,\!</math>, odpovídá binomickému rozdělení:

:<math>P(\mathbf{l}(i) = l) = p_{n,l} = \mathbf{}\binom{n}{l}\left(\frac{1}{m}\right)^{l}\left(1-\frac{1}{m}\right)^{n-l}\,\!</math>

Toto je jen aproximace (pro nekonečnou velikost univerza i seznamů), pro případ, že <math> N>>n^2 m\,\!</math>, ale lze použít. Očekávaná délka řetězce pak vychází jako (rozepíšu faktoriál a vytknu <math> \frac{n}{m}\,\!</math>, pak změním rozsah sumace <math> 1\dots n\,\!</math> (protože násobení <math>l=0</math> mi nic nedá), pak můžu z <math>l-1</math> udělat <math>l</math> a sumovat <math> 0\dots n-1\,\!</math>):

:<math>E(l)=\sum_{l=0}^{n}lp_{n,l}=\frac{n}{m}\sum_{l=0}^{n-1}\mathbf{}\binom{n-1}{l}(\frac{1}{m})^l(1-\frac{1}{m})^{n-1-l}=\frac{n}{m}(\frac{1}{m}+1-\frac{1}{m})^{n-1}=\frac{n}{m}=\alpha\,\!</math>

Vlastně tu ale objevujeme Ameriku tím, že počítáme střední hodnotu binomicky rozdělené veličiny s parametrem <math>\frac{1}{m}</math> -- ze vzorce nám vyjde to samé. Stejně tak rozptyl ze vzorce vyjde <math>\frac{n}{m}\left(1 - \frac{1}{m}\right)</math>.

}} Očekávaná délka nejdelšího řetězce (ocekávaný nejhorší případ):

E(NP) = O (log n / log log n)

{{collapse|Dk(Očekávaná délka nejdelšího řetězce):|

Tento údaj však sám o sobě nestačí, počítá se i očekávaný nejhorší případ (očekávaná délka nejdelšího řetězce). Ta se definuje následovně:

:<math>EMS = \sum_{j}j P(\max_{i} \mathbf{l}(i) = j) = \sum_{j} P(\max_{i}\mathbf{l}(i) \geq j )\,\!</math>

Z toho (pravděpodobnost disjunkce jevů je <math>\leq\,\;</math> součet jednotlivých pravděpodobností; vyčíslení: počet podmnožin správné velikosti a pravděpodobnost, že mají stejný hash):

:<math>P(\max_{i}\mathbf{l}(j)\geq j ) \leq \sum_{i}P(\mathbf{l}(i)\geq j) \leq m \mathbf{}\binom{n}{j}(\frac{1}{m})^j = \frac{\prod_{k=0}^{j-1}(n-k)}{j!}(\frac{1}{m})^{j-1} \leq n (\frac{n}{m})^{j-1}\frac{1}{j!}\,\!</math>

Najdeme mezní hodnotu <math> j_0\,\!</math>, pro které <math> n(\frac{n}{m})^{j-1}\frac{1}{j!}\leq 1\,\!</math>. Označme <math> k_0 = \min\{k|n\leq k!\} \,\!</math>. Potom <math> j_0 \leq k_0\,\!</math>. Ze Stirlingovy formule plyne, že <math>\log x! = \Theta(x\log x)\,\!</math>. Z toho odvodíme (hodně neformálně, asymptoticky):

:<math>\log k_0! = k_0 \log k_0 = O(\log n)\,\;</math> :<math>\log k_0 + \log\log k_0 \approx \log k_0 = O(\log\log n)\,\;</math>

:<math>k_0 = \frac{k_0 \log k_0}{\log k_0} = O(\frac{\log n}{\log\log n})\,\;</math>

A <math>j_0 = O(k_0)</math>. Pro <math> \alpha\leq 1\,\!</math> platí, že <math> EMS = O(j_0)\,\;</math>:

:<math>EMS=\sum_{j}P(\max_{i}\mathbf{l}(i)\geq j)\leq \sum_{j}\min\{1,n(\frac{n}{m})^{j-1}\frac{1}{j!}\} = \sum_{j=1}^{j_0}1 + \sum_{j=j_0+1}^{\infty}(n(\frac{n}{m})^{j-1}\frac{1}{j!}) \leq j_0 + \sum_{j=j_0+1}^{\infty}\frac{n}{j!} = \dots \leq j_0 + \frac{1}{j_0}\,\!</math>

A tedy očekávaná délka nejdelšího řetězce je <math>O(\frac{\log n}{\log\log n})\,\;</math>. }}

Soubor:Hashovani premistovani.png

S přemísťováním

každé políčko má dva ukazatele (prev, next), s jejichž pomocí tvoří kolizní položky řetězec

  • INSERT - při kolizi je původní položka přemístěna

  • 💡 dá se říct že jde o implementaci separovaných řetězců v 1 tabulce

  • 💡nevýhoda: přemísťování při INSERTu zpomaluje

Se 2 ukazateli

*podobné předchozímu, políčko má ukazatele na začátek řetězce a následníka (begin, next) *prvky se nepřemisťují, místo toho může být začátek přesměrován pomocí prvního ukazatele

*💡 zrychlí INSERT a DELETE ale zpomalí SEARCH <br style="clear:both">

{{multiple image |align = tright

|direction = vertical

| image1 = LISCH.png | width1 = 400

| caption1 = standardní,bez pomocné paměti (LISCH, EISCH)

| image2 = Hasovani 3140668278711546393.png | width2 = 400

| caption2 = s pomocnou pamětí (LICH, EICH, VICH) }}

'''Srůstající''' hashování (coalesced chaining)

řetězce pomocí 1 ukazatele v hashovací tabulce navíc - odkaz na další prvek NEXT

💡 Nepodporují efektivní DELETE

💡 Očekávaná délka řetězce(poč.testů) při zaplněné tabulce: 3 a s pomocnou pamětí 2

Standardní, bez pomocné paměti -- "late insert standard" '''LISCH '''a "early insert standard" '''EISCH'''

  • LISCH (late-insertion standard) přidává se za poslední prvek řetězce, projití celého řetězce s testy na přítomnost prvku, potom vložení na libovolné volné místo v tabulce a připojení na konec řetězce

  • EISCH (early-insertion standard) v případě neprázdného řetězce vždy za 1. prvek, vložení na nějaké volné místo v tabulce a jen přepojení ukazatelů NEXT

S pomocnou pamětí -- "late insert" '''LICH''', "varied insert" '''VICH''', "early insert" '''EICH'''

paměť na dvě části:

  • (hash-funkcí) přímo adresovatelná

  • pomocná část (bez přístupu hash-funkcí)

Kolize ukládáme do pomocné části, pak teprve do přímo adresovatelné(oddalujeme srůstání řetězců). Chování se tak až dourčitého okamžiku podobá separovaným.

  • LICH(late-insertion) vždy přidává na konec řetězce

  • EICH(early-insertion) v případě neprázdného řetězce vždy za 1. prvek

  • VICH(varied-insertion) v pomocné paměti jako LICH, v přímo adresovatelné části jako EICH

<br style="clear:both"> {{multiple image

|align = tright |direction = horizontal

| image1 = Hashovani linear.png

| width1 = 292 | caption1 = Hašování s lineárním přidáváním (probing)

| image2 = Double.png

| width2 = 76 | caption2 = Dvojité hašování

}}

'''Otevřené adresování''' (open addressing)

'''Lineární zkoušení''' (přidávání, linear probing)

tabulka má jen klíč, kolizní prvky se dávají na první volné místo

  • např: h(k, i) = (h'(k) + i) mod m

    • 💡 "cyklická" paměť, tj. když dojdeme na konec, vkládáme od začátku.

    • 💡 nepoužívá žádné dodatečné položky v hashovací tabulce (nalezení dalšího prvku z řetězce je přímo v algoritmu)

  • 💡 spec. případ dvojitého pro h2(x) = 1

  • použitelné do zaplnění 75% pak moc velké shluky

  • DELETE se řeší přehashováním celého "clusteru" dat

'''Dvojité hashování''' (double hashing)

podobné, jakmile selže h1 použije se 0,1,... - násobek h2:

  • h(k, i) = (h1(k) + ih2(k)) mod m

Kukaččí hashování (cuckoo)

2 hashovací fce h₁ a h₂ :

  • INSERT - pokud je místo v tabulce určené h₁ plné, přehashujeme původní prvek pomocí h₂ (jako "kukačka")

    • 💡 "cyklická" paměť, tj. když dojdeme na konec, vkládáme od začátku

  • SEARCH pak projde max 2 pozice

Srovnání

Podle počtu testů v SEARCH:

  • VICH je při vhodném <math> \alpha\,\!</math> lepší než hashování se dvěma ukazateli.

  • Lineární přidávání se nedá použít pro <math> \alpha > 0.7\,\!</math>, dvojité hashování pro <math> \alpha > 0.9\,\!</math>.

  • Separované řetězce a obecné srůstající hashování používají víc paměti, přemísťování a dvojité hashování zas víc času, tj. nelze říct, které je jednoznačně lepší.

Implementační dodatky

  • Pro hledání volných řádků se většinou používá seznam (zásobník).

  • Přeplnění se většinou řeší držením <math> \alpha\,\!</math> v rozumném intervalu (<math>\langle 1/4, 1\rangle\,\!</math>) a přehashováním do jinak velké tabulky (<math> 2^i\cdot m\,\!</math>) při pře- nebo podtečení

  • V praxi se doporučuje přehashování odkládat (např. pomocnými tabulkami) a provádět při nečinnosti systému.

DELETE se ve strukturách, které ho nepodporují, řeší označením políčka jako smazaného s možností využití při vkládání. V případě, že polovina polí je blokovaná tímto způsobem, se vše přehashuje. Pro srůstající hashování se toto používat nemusí, máme metody na zachování náhodnosti rozdělení dat.

V praxi je výhodné, známe-li něco o rozdělení vstupních dat, aby ho hashovací funkce kopírovala (většinou to ale nejde), jinak musíme předpokládat rovnoměrnost, což zaručeno zdaleka není. Nutnost rovnoměrného rozdělení vstupních dat lze obejít (viz ).

'''Univerzální''' hashování (6×🎓)

{{zkazky|1=

  • Reseni kolizi v hashovani a univerzalni hashovani (2012, Majerech) - Na uvod klasicky vycet ruznych reseni kolizi ("ten sklep v tom, jak ho popisujete, vam k nicemu nebude, podle me"), pak dlouhe paceni toho, ze se pri velkem load factoru da tabulka zvetsit (vubec me nenapadlo, ze je potreba to rict, ale M. byl chapavy a pockal si, az jsem se chytil za nos), pak povidani o rozdilu mezi randomizovanou slozitosti a ocekavanou slozitosti ("co kdyz budete mit robota nad pacientem, co z nej strika krev, bude vam tohle hashovani stacit?"), diskuse o doplneni RB stromu do jednotlivych bucketu a tak. Slabsi povahy by si mohly myslet, ze je to na vyhazov, ale to vubec neni pravda, M. je velmi inteligentni a korektni a i zkouseni je u nej prilezitost k vysvetleni zajimavosti. Bylo fajn, ze se neptal na algebraicke principy fungovani c-univerzalnich systemu, ale spis mu slo o porozumeni, jak to funguje a v cem je to dobre/spatne.

  • 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.

  • univerzální hashování (2012, Grafika, Dvořák) - K tomu univ. hashování jsem napsal definici, definici c-univerzálního systému, konstrukci systému s důkazem c-univerzality (podle skript Koubka) a bez důkazu složitost operací. Tohle se mu sice líbilo, ale pak začal víc rozebírat tu složitost počtu operací a tam jsem už nic moc kloudnýho do kupy nedal. Nechtěl to dokázat, ale nějak interpretovat, a to se mi nedařilo. Zasekl jsem se u definice očekávané délky řetězce a snažil jsem se tu diskuzi stočit jinam, protože tady o tom jsem věděl kulový. :) Nakonec jsme to nechali být a ještě mě taky dostal otázkou, kdy se vybírá ten náhodnej index hashovací funkce. Já jsem si myslel, že se vybírá pro každý prvek nová, ale není to tak, protože bych pak nevěděl, kterou funkci jsem pro každej prvek použil. Prý se teda volí index jednou předtím, než přijdou data a pokud se ukáže, že vybraná funkce není dobrá, tak se potom může vybrat nová a tabulka celá přehashovat.

  • 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

  • Hašování (2013, Majerech) - Vyjmenoval jsem předpoklady, základní typy hašování, očekávaná délka řetězce separovaných řetězců (kromě definice univerzálního hašování jediný vzoreček, který se po mně chtěl), základy univerzálního hašování, na perfektní už se nedostalo. Zkoušející byl Majerech - hodně šťoural, ale zajímaly ho praktické aspekty použití spíš než vzorečky (i když kolegu přede mnou dusili na definici nějakých vyhledávacích stromů).

  • Univerzální hašování (2012, Čepek) - Definice (c)-univerzálního systému, potom jsem ukázal konstrukci 1-univerzálního podle MIT (na který jsem se koukal den předtím). Za deset minut bylo hotovo

  • Univerzální hašování (2004, Koubek) - Uplna katastrofa ovsem bylo univerzalni hashovani. Nejdriv jsem presvedcive dokazal, ze nevim co to je, pote jsem po nadhozeni napovedy (c-univerzalni posloupnost hashovacich funkci) dal s velkym usilim a dalsi pomoci dohromady definici a otazku jsem zakoncil marnym pokusem dokazat tvrzeni - nakonec mi to musel malem nadiktovat ...

}} {{collapse|zkazky I1/4|2= 

  • Univerzální hašování (2012, Koubek) - popsal jsem základní vlastnosti, odhad délky řetězců, minimální velikost a konstrukci 1-univerzálního hašování podle Leiserssona - doplňující dotazy na min. velikost c a ještě jestli lze zmenšit tu množinu funkcí

  • Univerzální Hashování (2014, Koubek) - MIT konstrukce bohatě stačila, padly nějaké dotazy na obecné vlastnosti, které chceme od univ. systému, proč to vůbec děláme, jak ˇje to ovlivněné pseudonáhodností místo náhodnosti.

  • Univerzální hashování (2014, Hladík) - Ukázal jsem tu konstrukci podle videa z MIT. Zajímaly ho jak je to obecněji pro c-univerzální systémy, měl doplňující otázky k velikosti množiny, něco jsem věděl něco ne.

  • Univerzální hashovaní (2013, Čepek) - Popsal jsem motivaci, pak konstrukci jak je v Koubkových skriptech. Pak očekávaný počet kolizí (takové to O(1+cα)). A pak dolní odhad na <math>\|I\|</math>. Všechno jsem psal samozřejmě s důkazy. Stačilo to a nic víc doc. Čepek nechtěl. Padly ještě nějaké dotazy ohledně hašování obecně. Nicméně otázka byla nakonec jedna z příjemnějších.

  • Univerzální hašování (2014, Koubek) - Po chvíli psaní mi to vzal a nakoukl (má poslední otázka a zbývali jsme tam poslední dva). Měl jsem tam úvodní povídání, první univerzální systém ze skript, lepší univerzální systém ze skript (vše bez důkazů). Stačilo mu to, jen měl pár kontrolních otázek.

  • Univerzalni hashovani (2011, cepek) - U univerzalniho hashovani bohate stacilo povidani z MIT prednasky, mnohokrat diky cloveku, ktery to video objevil. Rychlemu nasobeni jsem se branil, ale neubranil, vedel jsem jenom, ze se to nejspis nejak prevede na DFT. Cekal jsem nejhorsi, ale chopil se toho Vladan Majerech a behem asi 40 minut mi celou zalezitost metodou navadejicich otazek pred komisi vysvetlil, respekt:))

  • Hashovanie, riešenie kolízií, univerzálne hashovanie (2012, Vladan Majerech) - Dr. Majerech sa párkrát počas celého skúšania chodil pýtať (nielen mňa), či už chceme uňho odpovedať a tváril sa sklamane, že nikto nechce. :) Ja som si ho nechal nakoniec, pretože som tušil, že to hashovanie nebude úplne ono. Keď som nakoniec začal spisovať všetky možné hashovania (separované reťazce, s premiestňovaním, zrastajúce reťazce, bla bla bla) a napísal som prvý riadok z univerzálneho hashovania, tak ma prerušil, že nejdime sa toľko rozpisovať a začal som mu rozprávať, čo som spísal. Po chvíľke predstavovania Yet Another™ hashovacieho variantu ma prerušil, že to nemusíme, hlavne sa sústreďme na to univerzálne hashovanie. Ešte sa teda spýtal na výhody a nevýhody rozličných hashovacích stratégií, v čom som úplne jasno nemal a niečo som vymyslel, k niečomu som bol s (výdatnou) Majerechovou pomocou dokopaný. Potom som nejako opísal univerzálne hashovanie, avšak už som príliš nevedel o detailoch, na ktoré sa ma pýtal, okrem všeobecnej výhody (možnosti prehashovať pri raste reťazcov). Nespomenul som si na to, že sa používa viac systémov c-univerzálnych funkcií a vôbec som nikdy predtým nezistil, že sa počas práce s hashtabuľkou vedľa stavia preventívne nová. Nakoniec som ešte, už pomaly nevediac, ako sa volám, načrtol ideu príkladu na c-univerzálny systém, ale tam ma rozbilo to, cez čo moduliť (ax+b mod N, mod m? mod N mod m!). Celkovo si ma tam dr. Majerech celkom smažil, pokúšajúc sa o vylámanie nejakej znalosti. Na vyhodenie sa síce asi netváril, ale ja by som si za takúto odpoveď asi nič lepšie než trojku nedal.

}} {{:Státnice_-_Hašování_I2/Universal}}

Externí hashování (asi se už nezkouší?)

{{:Státnice - Hašování I2/Externí}} {{Statnice I2}}