2-izborno heširanje

2-izborno heširanje, takođe poznato kao i 2-izborno ulančavanje, je varijanta heš tabele u kojoj se ključevi dodaju uz pomoć dve heš funkcije. Ključ se stavlja na poziciju u nizu sa najmanje podudaranja. Potrebna nekakva metoda rešavanja kolizije, osim ako se ključevi čuvaju u skupovima. Iskorišćenost resursa u prosečnom slučaju uspešne pretrage je O(2 + (m-1)/n), m je broj ključeva a n je veličina niza. Najveći moguć broj kolizija je $\log _{2}\ln n+\theta (m/n)$ sa velikom verovatnoćom.

Kako radi

2-izborno heširanje koristi dve heš funkcije h1(x) i h2(x). Te dve heš funkcije treba da budu nezavisne jedna od druge i da nemaju ništa što ih povezuje. Zahvaljujući korišćenju dve heš funkcije bilo koji integer x ima dve potencijalne lokacije na koju mogu da se skladište na osnovu iѕlaѕa funkcija h1(x) i h2(x). Iako postoje dve heš funkcije, još uvek postoji samo jedna heš tabela, i obe funkcije upisuju ključeve u istu tabelu.

Implementacija

Najbitnije strane ove heš implementacije su umetanje i pretraga.

Umetanje: Kad umećemo vrednosti obe heš funkcije se računaju se objekat koji treba da se umetne. Objekat se zatim stavlja u skup sa manje objekata. Ako su skupovi jednake veličine, podrazumevana lokacija je h1(x) vrednost.

Pretraga: Efikasne pretrage se vrše proveravanjem oba skupa, tj. lokacije skupova na koje su h1(x) i h2(x) mapirane za željenu vrednost.

Brzina i efikasnost

Kao što je slučaj sa svim heš tabelama, učinak se posmatra na najvećem skupu. Iako ima slučajeva gde veličine skupova mogu da budu velike na osnovu vrednosti i heš funkcija koje se koriste, to je retko. Zahvaljujući korišćenju dve heš funkcije imamo dve moguće lokacije za svaku vrednost, zbog čega postoji još manja verovatnoća da će dođe do velikih skupova. Očekivana veličina skupa prilikom korišćenja 2-izbornog heširanja je : θ(log(log(n))).

Bitno: Princip korišćenja više heš funkcija je optimiziran pomoću dve heš funkcije. Neće doći do poboljšanja ako se broj heš funkcija poveća - 3 heš funkcije nisu efikasnije 2.

Literatura

• Paul E. Black, 2-choice hashing at the National Institute of Standards and Technology, Dictionary of Algorithms and Data Structures.