Hash tablica Flashcards
Što je podatkovna struktura hash (rasuta) tablica te kako se i zbog čega ista koristi?
To je podatkovna struktura u kojoj se ključevi raspoređuju u ćelije polja primjenom hash funkcije i koristi se u svrhu redukcije potrebnog memorijskog prostora.
Zbog čega nastaju kolizije u hash tablici te kako ih je moguće minimizirati?
Nastaju kada hash funkcija za 2 različita ključa rezultira istim indeksom. Ne postoji hash funkcija koja će u potpunosti eliminirati kolizije, ali kod dobrih funkcija će se minimizirati broj kolizija na način da će se uniformno rasporediti elementi po polju.
Nabrojite i objasnite svojstva dobre hash funkcije.
Mali utrošak resursa, određenost, uniformnost.
Mali utrošak resursa označava da heširanje mora biti superiorno u odnosu na alternativne pristupe razmještanja elemenata.
Određenost označava da za isti ulazni ključ, hash funkcija uvijek mora rezultirati istom izlaznom vrijednosti.
Uniformnost označava da se ključevi moraju što je moguće ravnomjernije rasporediti u raspoloživom rasponu prostora za pohranu.
Koji su nedostaci metode (modularnog) dijeljenja?
Uzastopne vrijednosti ključeva će se preslikati u uzastopne hash vrijednosti. Iako neće doći do kolizije između uzastopnih vrijednosti ključeva, uzastopni indeksi polja će biti zauzeti što može dovesti do smanjena performansi.
Objasnite složenost najboljeg i najgoreg slučaja primjene linearnog ispitivanja.
Najbolji slučaj je kada je vrijednost pronađena i to je onda O(1) jer smo je našli u konstantnom vremenu, najgori slučaj je O(n) u kojem moramo pretražiti cijelu tablicu jer se vrijednost nalazi na zadnjem mjestu, ili je uopće nema u tablici.
Nabrojite i objasnite prednosti i nedostatke primjene linearnog ispitivanja.
Njegove performanse ovise o distribuciji ulaznih vrijednosti te je njegov glavni nedostatak klasteriranje koje povećava rizik da će na mjestu jedne kolizije doći do još kolizija. Prednost je što je ono relativno brzo ako se tražena vrijednost nalazi pri početku tablice.
Nabrojite i objasnite prednosti i nedostatke primjene kvadratnog ispitivanja.
Prednost je to što je efikasno pri načinu pohrane podataka u memoriju, ali nedostatak je u tome što pri kvadratnom ispitivanju istražujemo samo mali dio tablice te se povećava broj mogućih višestrukih kolizija.
Nabrojite i objasnite prednosti i nedostatke primjene dvostrukog heširanja.
Prednost je to što se minimizira pojavljivanje ponovnih kolizija i smanjuju se učinci klasteriranja. Nedostatak je to što se performanse smanjuju kad je tablica blizu maksimalne popunjenosti, pa onda treba raditi novu.
Objasnite obilježja rješavanja kolizija pomoću tehnike ulančavanja (otvorene hash tablice).
To je princip riješavanja kolizija u kojem je u svakoj ćeliji hash tablice pohranjen pokazivač do vezane liste sačinjene od podatkovnih vrijednosti koje su heširanje na adresu/indeks te ćelije.
Nabrojite i objasnite operacije koje se izvršavaju na otvorenoj hash tablici.
Umetanje, brisanje i traženje. Traženje je ekvivalentno pretraživanju jednostruko vezane liste. Umetanje dodaje podatkovnu vrijednost na početak, kraj ili neku drugu lokaciju unutar vezane liste heširane lokacije. Brisanje funkcionira tako da pretražimo tablicu i uklonimo traženi element ako postoji.
Objasnite složenost operacija koje se izvršavaju na otvorenoj hash tablici.
Cijena umetanja podatkovne vrijednosti iznosi O(1) dok cijena pretraživanja i brisanja iznosi O(m) gdje m predstavlja broj elemenata liste heširane lokacije.
Cijena pretraživanja i brisanja je veća zbog ispitivanja unosa na odabranoj lokaciji za željeni ključ.
Nabrojite i objasnite prednosti i nedostatke ulančavanja (otvorene hash tablice).
Glavna prednost otvorene hash tablice je to što ostaje djelotvorna i kada je broj pohranjenih podatkovnih vrijednosti mnogo veći od broja lokacija u hash tablici, a nedostaci su da performanse opadaju kad se pohrani više vrijednosti u tablicu, a kod pohrane vrijednosti, nekad je potrebno alocirati značajnu količinu memorijskog prostora za pokazivač na sljedeći element.
Nabrojite i objasnite razlike između zatvorene i otvorene hash (rasute) tablice.
Performanse otvorene tablice ostaju relativno dobre i kada je broj pohranjenih podatkovnih vrijednosti veći od broja dostupnih lokacija u tablici, dok kod zatvorene ne možemo pohraniti više od onog što nam omogućuju dostupne memorijske lokacija.
Objasnite obilježja heširanja (rasipanja) sa pretincima.
To je implementacija zatvorene hash tablice koja grupira tablicu u pretince tako da M ćelija (slots) podijelimo u B pretinaca (buckets). Svaki pretinac sadrži M/B ćelija. Dakle, stvara se više memorijskog prostora
Nabrojite i objasnite prednosti i nedostatke heširanja (rasipanja).
Prednosti: Za pohranu indeksa nije potreban dodatan prostor kao kod ostalih podatkovnih struktura i omogućen je brz pristup podacima te učinkovit ažuriranje istih. Nedostaci: Zbog manjka lokaliteta i slijednog dohvaćanja po ključu operacije umetanja i dohvaćanja podatkovnih vrijednosti su prilično nasumične. Teško je odabrati djelotvornu hash funkciju; često su loše.
