Dvostruko heširanje

Ova heš funkcija slika string u ceo broj, u opsegu od 0-15. U slučajevima "John Smith" i "Sandra Dee" dolazi do kolizije.

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 $h_{1}$ i sekundarne $h_{2}$ , koje pripadaju skupu univerzalnih heš funkcija. Pomoću njih, i-ta pozicija zadate vrednosti k u tabeli $T$, određuje se po formuli:

$h(i,k)=(h_{1}(k)+i\cdot h_{2}(k))\mod |T|.$

Nasumičnost dvostrukog heširanja

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 $h_{1}$ and $h_{2}$ gradi se tablica dvostrukog heširanja $T$. Svi elementi se smeštaju u tablicu heširanja $T$ pomoću izabranih funkcija.

Neka je $n$ broj elemenata smeštenih u $T$. Tada je faktor skladištenja tabele $\alpha ={\frac {n}{|T|}}$.

Neka je $1>\alpha >0$. Bredford i Majk Katehakis pokazali su da je očekivani broj provera za neuspešne pretrage u tabeli jednak ${\frac {1}{1-\alpha }}$.

Efikasnost i problemi

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 $k=5$ , tekuća funkcija biće jednaka nuli :

$h_{2}(k)=5-(k\mod 7)$

to jest, dobijena vrednost će uvek ostati na početnoj heš vrednosti. Jedno od rešenja je promena sekundarne heš funkcije u:

$h_{2}(k)=(k\mod 7)+1$

Ovim osiguravamo da sekundarna heš funkcija uvek bude različita od nule.

Vidi još

• Heš funkcija
• Heš tabela
• Linearno popunjavanje
• Kvadratno proveravanje

Spoljašnje veze

• Algoritmi, Miodrag Živković
• How Caching Affects Hashing, Gregory L. Heileman and Wenbin Luo 2005.
• Hash Tables