Dvostruko heširanje
Dvostruko heširanje (engl. Double hashing) je tehnika sa otvorenim adresiranjem u programiranju koja se koristi za otklanjanje kolizija kod heš tabela, u slučaju kada se za 2 različite vrednosti dobija isti heš ključ.
Kao kod linearnog popunjavanja, ciklusno prebrojavanje počinje od početne vrednosti za određeni interval. Taj interval se određuje pomoću dve heš funkcije, primarne i sekundarne , koje pripadaju skupu univerzalnih heš funkcija. Pomoću njih, i-ta pozicija zadate vrednosti k u tabeli , određuje se po formuli:
Nasumičnost dvostrukog heširanja uredi
Ako je cilj smanjiti ukupan broj pristupa memoriji, idealni slučaj adresnog heširanja je uniformno heširanje (engl. Uniform hashing). To jest, nasumičnim, uniformnim i nezavisnim izborom dve univerzalne heš funkcije and gradi se tablica dvostrukog heširanja . Svi elementi se smeštaju u tablicu heširanja pomoću izabranih funkcija.
Neka je broj elemenata smeštenih u . Tada je faktor skladištenja tabele .
Neka je . Bredford i Majk Katehakis[1] pokazali su da je očekivani broj provera za neuspešne pretrage u tabeli jednak .
Efikasnost i problemi uredi
Prednost linearnog i kvadratnog popunjavanja je u tome što su ove dve tehnike uspele da iskoriste pogodnosti koje pruža keš podataka (engl. Data cache), pristupajući lokacijama koje se nalaze jedne blizu drugih u memoriji. Kod dvostrukog heširanja intervali su veći, stoga se te pogodnosti ne mogu iskoristiti. Problem rešava skladištenje podataka zajedno sa drugim ključem- kao vrstu , a prvi ključ - kao kolonu. Ovakva organizacija omogućava nam da operišemo nad kolonom , što sprečava probleme sa kešom, kao i potrebu za reheširanjem drugog ključa. Naredni primer opisuje pomenuto rešenje :
pData[hk_2][hk_1]
int hv_1 = Hash(v)
int hv_2 = Hash2(v)
int original_hash = hv_1
while(pData[hv_2][hv_1]){
hv_1 = hv_1 + 1
}
Kao i ostale forme otvorenog adresiranja, sa dostizanjem maksimalnog kapaciteta heš tabele, dvostruko heširanje postaje linearno. Jedino rešenje je reheširanje, odnosno povećanje dimenzije tabele.
Jedan od problema je i taj, što sekundarna heš funkcija može dostići nulu. Na primer, ako postavimo vrednost , tekuća funkcija biće jednaka nuli :
to jest, dobijena vrednost će uvek ostati na početnoj heš vrednosti. Jedno od rešenja je promena sekundarne heš funkcije u:
Ovim osiguravamo da sekundarna heš funkcija uvek bude različita od nule.
Vidi još uredi
Reference uredi
- ^ P. G. Bradford and M. Katehakis: A Probabilistic Study on Combinatorial Expanders and Hashing, SIAM Journal on Computing 2007 (37:1), 83-111. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.2647
Spoljašnje veze uredi
- Algoritmi, Miodrag Živković
- How Caching Affects Hashing, Gregory L. Heileman and Wenbin Luo 2005.
- Hash Tables