Hashing

Kratki uvod i malo teorije

Što je hashing?

Prilikom rješavanja zadataka često koristimo ispitivanje jednakosti nekakvih objekata. Ako se radi o intovima naš je problem vrlo jednostavan. Što ako imamo hrpu nizova intova i zanima nas koji od njih su međusobno jednaki? Možemo ih uspoređivati element po element, no to se ne čini previše efikasno. Pogledajmo o čemu se radi na malo apstraktnijoj razini.

Imamo neki veliki skup i njegov podskup čije elemente želimo brzo uspoređivati. Označimo veličinu jednog elementa s i pretpostavimo da je složenost usporedbe koju radimo na elementima . Za nešto veće ta složenost počinje utjecati na ukupnu složenost algoritma u kojem koristimo predviđenu usporedbu. Kako bismo tome doskočili uvodimo treći skup znatno manji od te posebnu funkciju . Za funkciju kažemo da je ravnomjerna ako mapira otprilike jednak broj elemenata u elemente . Pritom omjer nazivamo load factor i predstavlja očekivani broj elemenata koje mapira u neki element . Funkciju nazivamo hash funkcija, skup skupom svih mogućih ključeva, a skup skupom hash vrijednosti.

Hashing možemo definirati kao mapiranje nekih većih objekata u manje kako bismo ih lakše uspoređivali. Pritom postoji problem koji se naziva kolizija i posljedica je činjenice da ovim postupkom gubimo informacije i da se dvije vrijednosti mogu mapirati u istu hash vrijednost.

Jedan jednostavan primjer

Recimo da želimo implementirati trodimenzionalni niz intova čija je svaka dimenzija veličine milijun. Takav niz ne možemo realno ugurati u memoriju pa je potrebno iskoristiti neku drugu foru. Jedan od očitih pristupa bilo bi korištenje STL map strukture, ali ovdje nam je cilj pokazati što možemo izvesti korištenjem hash funkcija. Skup u ovom primjeru sadrži sve moguće trojke intova do milijun, dakle ima veličinu . Te ćemo trojke prvo morati smanjiti na neku prihvatljivu veličinu. Funkcija koju ćemo za trojku koristiti je sljedeća:

Za ćemo u našem slučaju uzeti broj , a za neki nasumični broj iz intervala . Nula i jedan se ovdje možda i ne čine kao najbolji izbor. Vrijednosti koje ćemo dobiti takvim mapiranjem trojki biti će puno manje od početnih pa ćemo za naš fiktivni niz N[x][y][z] zapravo koristiti nešto manji niz N[h(x,y,z)].

Kako će tu i tamo sigurno doći do preklapanja odnosno kolizije, morat ćemo doskočiti i tom problemu.

Chaining metdoa rješavanja kolizije

Ova metoda rješavanja preklapanja vrlo je jednostavna i vjerojatno prva pada na pamet kao nadogradnja naše dosadašnje ideje. Što ako N[h(x, y, z)] nije samo niz intova nego lista četvorki (x, y, z, v) ? Prva tri elementa (x, y, z) predstavljaju trojku a, vrijednost koja je toj trojki pridružena u našem nizu, odnosno N[x][y][z]. Ako želimo elementu na poziciji (x, y, z) dodijeliti neku vrijednost prvo ćemo ga potražiti u listi koja mu je pridružena već opisanom funkcijom. Ako ga ne nađemo na kraj liste dodat ćemo četvorku (x, y, z, v). Ako ga pak pronađemo jednostavno ćemo modificirati vrijednost u pripadajućoj četvorki.

Upravo smo vrlo jednostavno implementirali jako velik niz. No jedna stvar još nije jasna. Kako znamo da će naša funkcija ravnomjerno raspoređivati trojke?

Mala analiza hash funkcije

Funkcija koju smo definirali polinom je u . Pogledajmo što dobijemo izjednačavanjem funkcije za dvije trojke i :

Jednakost dakle dobivamo u slučaju kada je nultočka nekog trećeg polinoma modulo . Polinom je maksimalno drugog stupnja pa tako ima maksimalno dvije različite nultočke (ovo usput nije odmah očito i vrijedi samo za prost ). Vjerojatnost da je nasumični nultočka ovog polinoma tako je , oko za naš , što smatramo jako malim brojem i možemo očekivati da će funkcija biti prilično ravnomjerna.

Sada ako netko ne poznaje naš izbor i vrlo mu je teško namjestiti primjer u kojem se puno trojki mapira u istu vrijednost. Osim ovakve analize moguće je funkciju implementirati i isprobati u praksi. Tu treba imati na umu i "pravilne" inpute koji iz perspektive hash funkcije ne bi smjeli biti drukčiji od nasumičnih.

Dobro je primijetiti kako se ovaj primjer jednostavno poopći i na razne druge tipove indeksa i time dobivamo strukturu hash tablice, vrlo korisnu za brzo mapiranje.

Podatkovna struktura hash tablica podržava sljedeće operacije:

takav da ili NULL

Podatkovna struktura hash tablica neće biti detaljno opisana u ovom članku.

Pročitaj dalje

© 2014. Gustav Matula, Matija Šantl Creative Commons License

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License