Izbor dobre hash funkcije h(k) je osnovni problem kod koriscenja hash tabela za pretrazivanje. Funkcija h bi trebalo da raspodeli elemente naseg skupa sto je moguce ravnomernije u polja hash tabele. Kljucni kriterijum je da bi broj sudara trebalo da bude sto manji.

Ako je P(k) verovatnoca da se kljuc k pojavljuje u nasem skupu, tada bi, ako postoji m polja u nasoj hash tabeli, uniforma hash funkcija h(k) osigurala da:

Ponekad je ovo jednostavno obezbediti. Na primer, ako su kljucevi slucajno rasporedjeni u intervalu (0,r], tada funkcija

obezbedjuje ravnomerno hashiranje.

Preslikavanje kljuceva u prirodne brojeve

Posto smo preslikali kljuceve u skup prirodnih brojeva, imamo puno mogucnosti za hash funkciju.

1. Koristiti funkciju mod:

   h(k) = k mod m.

   Pri koriscenju ovog metoda, izbegavaju se odredjene vrednosti m. Obicno se izbegavaju stepeni dvojke, jer k mod 2^b jednostavno daje b najnizih bitova broja k. Osim u slucaju da znamo da su svih 2^b mogucih vrednosti najnizih bitova podjednako verovatne, ovo ne bi bio dobar izbor, jer se neki bitovi kljuca ne koriste u hash funkciji.

   U principu, prosti brojevi koji su bliski stepenima dvojke izgledaju kao povoljan izbor za m.

   Na primer, ako imamo 4000 elemenata, i izabrali smo organizaciju sa oblascu prelivanja, ali zelimo da sto je vise moguce smanjimo verovatnocu sudara, tada bismo mogli da izaberemo m = 4093. (4093 je najveci ceo broj manji od 4096 = 2¹².)

2. Koristiti metod mnozenja:
   • Pomnoziti kljuc konstantom A, 0 < A < 1,
   • Ostaviti samo razlomljeni deo proizvoda,
   • Pomnoziti ovu vrednost sa m.

   Prema tome, hash funkcija je:

   h(k) = floor(m * (kA - floor(kA)))

   U ovom slucaju, vrednost m nije kriticna i obicno se bira stepen dvojke, tako da mozemo da dobijemo sledecu efikasnu proceduru na vecini racunara:

   • Izabrati m = 2^p.
   • Pomnoziti w bita kljuca k sa floor(A * 2^w) da bi se dobio proizvod sa 2w bita.
   • Ostaviti samo p najznacajnijih bitova donje polovine ovog proizvoda.

     Izgleda da je

     A = (sqrt(5)-1)/2 = 0.6180339887

     veoma dobar izbor (videti Knuth, "Sorting and Searching", 3. tom u seriji "The Art of Computer Programming").

3. Koristiti univerzalno hashiranje:

   Zlobni protivnik bi uvek mogao da izabere kljuceve tako da se oni svi preslikavaju u isto polje hash tabele, prouzrokujuci prosecno O(n) vreme za pretrazivanje. Univerzalno hashiranje pokusava da izbegne ovu situaciju birajuci hash funkciju slucajno iz skupa hash funkcija. Ovo smanjuje verovatnocu da ce hash funkcija dati lose ponasanje i u proseku daje dobre performanse.

Kljucni pojmovi

Univerzalno hashiranje

Tehnika za slucajan izbor hash funkcije kako bi se uvek dobile solidne prosecne performanse.

Dalje na Algoritamske tehnike Nazad na Sadrzaj

© John Morris, 1998. Prevod sa engleskog, Dragan Stevanovic, 2002.