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

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

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

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

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

Нека је ${\displaystyle 1>\alpha >0}$. Бредфорд и Мајк Катехакис^[1] показали су да је очекивани број провера за неуспешне претраге у табели једнак ${\displaystyle {\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
}

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

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

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

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

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

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

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

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