Двоструко хеширање

Двоструко хеширање (енгл. Double hashing) је техника са отвореним адресирањем u програмирању која се користи за отклањање колизија код хеш табела, у случају када се за 2 различите вредности добија исти хеш кључ.

Ова хеш функција слика стринг у цео број, у опсегу од 0-15. У случајевима "John Smith" и "Sandra Dee" долази до колизије.

Као код линеарног попуњавања, циклусно пребројавање почиње од почетне вредности за одређени интервал. Тај интервал се одређује помоћу две хеш функције, примарне $h_{1}$ и секундарне $h_{2}$ , које припадају скупу универзалних хеш функција. Помоћу њих, i-та позиција задате вредности к у табели $T$, одређује се по формули:

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

Насумичност двоструког хеширања

Ако је циљ смањити укупан број приступа меморији, идеални случај адресног хеширања је униформно хеширање (енгл. Uniform hashing). То јест, насумичним, униформним и независним избором две универзалне хеш функције $h_{1}$ and $h_{2}$ гради се таблица двоструког хеширања $T$. Сви елементи се смештају у таблицу хеширања $T$ помоћу изабраних функција.

Нека је $n$ број елемената смештених у $T$. Тада је фактор складиштења табеле $\alpha ={\frac {n}{|T|}}$.

Нека је $1>\alpha >0$. Бредфорд и Мајк Катехакис показали су да је очекивани број провера за неуспешне претраге у табели једнак ${\frac {1}{1-\alpha }}$.

Ефикасност и проблеми

Предност линеарног и квадратног попуњавања је у томе што су ове две технике успеле да искористе погодности које пружа кеш података (енгл. Data cache), приступајући локацијама које се налазе једне близу других у меморији. Код двоструког хеширања интервали су већи, стога се те погодности не могу искористити. Проблем решава складиштење података заједно са другим кључем- kao врсту , а први кључ - kao колону. Оваква организација омогућава нам да оперишемо над колоном , што спречава проблеме са кешом, као и потребу за рехеширањем другог кључа. Наредни пример описује поменуто решење :

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
}

Као и остале форме отвореног адресирања, са достизањем максималног капацитета хеш табеле, двоструко хеширање постаје линеарно. Једино решење је рехеширање, односно повећање димензије табеле.

Један од проблема је и тај, што секундарна хеш функција може достићи нулу. На пример, ако поставимо вредност $k=5$ , текућа функција биће једнака нули :

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

то јест, добијена вредност ће увек остати на почетној хеш вредности. Једно од решења је промена секундарне хеш функције у:

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

Овим осигуравамо да секундарна хеш функција увек буде различита од нуле.

Види још

• Хеш функција
• Хеш табела
• Линеарно попуњавање
• Квадратно проверавање

Спољашње везе

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