- indexovanie klucom
- priamy pristup, pretoze kluc je priamo adresou
- rozsah klucov zodpoveda priamo rozsahu indexov
- asymptoticka zlozitost je theta(1)
- rozptylovanie
- funguje vypoctom adresy z hodnoty kluca
- priemerna zlozitost je omega(1)
- porovnanie klucov
- toto je asociativne vyhladavanie
- patri sem napriklad sekvencne vyhladavanie, BVS,
- zlozitost omega(log(n))
ak mame vela pamate => index. klucom
ak mame vela casu => sekvencne vyhladavanie
ak nemame ani jedno => rozptylovanie
Hashing
- vhodne pre vyhladavanie, ale nevhodne pre triedenie
- adresuje na zaklade rozptylovacej funkcie h(k)
- zobrazujem mnozinu klucov K z univerza do itnervalu adries <Amin, Amax>
- rozptylovacia funkcia by mala byt jednoducha a rychla a je silne zavisla na vlastnostiach klucov a ich reprezentacii v pamati
- mala by generovat minimum kolizii a rovnomerne vyuzivat adresny priestor
- ak dojde ku kolizi => bud je zla fcia, pretoze vracia prilis blizke hodnoty, alebo spatne pocita, ak to nie je pripad, tak musime kolizie riesit
- kolizie spomaluju aplikaciu
- sposoby riesenia su zretazene rozptylovanie a otevrene rozptylovanie
zretazene rozptylovanie
- mame prvu h(k), napr. h(k) = k mod 3 (takze 3 je potom rozsah adries pre umiestnenie prvkov)
- ak dojde ku kolizii, teda mame synonymum, tak potom prvok zretazim do spojoveho zoznamu za prvok, s ktorym kolidujem
- toto retazenie nazyvam retazou synonym a ma idealne dlzku alfa = n/m, kde alfa > 1, n je pocet prvkov a m velkost tabulky < m
- vkladanie = O(1)
- vyberanie, mazanie = O(n) ak to ide fakt zle, alebo O(1+alfa) priemerne
- vyplati sa, pretoze sa neplytva pamatou
otvorene rozptylovanie
- pocet prvkov je vopred znamy
- tu sa nebudu pouzivat ukazatele, ale bude sa ukladat do pola
- su dve moznosti ako ukladat prvky, ked dojde ku kolizii - Linear Probing a Double Hashing
- Linear Probing v pripade kolizie ulozi prvok na dalsie miesto v poradi, ktore je volne, vytvara tak zhluky, ktore mozu byt az prilis dlhe
- Double hashing pri kolizii pouzije druhu hashovaciu funkciu a ked nevyjde ani to, tak pouzije linear probing,
funkcia moze vyzerat takto: h(k) = (k mod 5 + i*h2(k)) mod 5, h2(k) = (k + 3i)mod5 ak to nevyjde na 1x , tak vloz o 3 pozice dalej (v pripade prveho neuspechu)
problemom je, ako zaplnit tabulku
- tabulka moze byt viac zaplenena, kym zacne klesat vykonnost a operacie trvaju umerne zaplnenosti tabulky, vhodne je tak 3/4, 9/10
