240px|мини|десно|Ова хеш функција слика стринг у цео број, у опсегу од 0-15. У случајевима "John Smith" и "Sandra Dee" долази до колизије.
Двоструко хеширање () је техника са отвореним адресирањем u програмирању која се користи за отклањање колизија код хеш табела, у случају када се за 2 различите вредности добија исти хеш кључ.
Као код линеарног попуњавања, циклусно пребројавање почиње од почетне вредности за одређени интервал. Тај интервал се одређује помоћу две хеш функције, примарне и секундарне , које припадају скупу универзалних хеш функција. Помоћу њих, i-та позиција задате вредности к у табели , одређује се по формули:
Насумичност двоструког хеширања Ако је циљ смањити укупан број приступа меморији, идеални случај адресног хеширања је униформно хеширање (). То јест, насумичним, униформним и независним избором две универзалне хеш функције and гради се таблица двоструког хеширања . Сви елементи се смештају у таблицу хеширања помоћу изабраних функција.
Нека је број елемената смештених у . Тада је фактор складиштења табеле .
Нека је . Бредфорд и Мајк Катехакис показали су да је очекивани број провера за неуспешне претраге у табели једнак .
Ефикасност и проблеми Предност линеарног и квадратног попуњавања је у томе што су ове две технике успеле да искористе погодности које пружа кеш података (), приступајући локацијама које се налазе једне близу других у меморији. Код двоструког хеширања интервали су већи, стога се те погодности не могу искористити. Проблем решава складиштење података заједно са другим кључем- 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 }
Као и остале форме отвореног адресирања, са достизањем максималног капацитета хеш табеле, двоструко хеширање постаје линеарно. Једино решење је рехеширање, односно повећање димензије табеле.
Један од проблема је и тај, што секундарна хеш функција може достићи нулу. На пример, ако поставимо вредност , текућа функција биће једнака нули :
то јест, добијена вредност ће увек остати на почетној хеш вредности. Једно од решења је промена секундарне хеш функције у:
Овим осигуравамо да секундарна хеш функција увек буде различита од нуле.
Види још Хеш функција Хеш табела Линеарно попуњавање Квадратно проверавање
Референце
Спољашње везе Algoritmi, Miodrag Živković How Caching Affects Hashing, Gregory L. Heileman and Wenbin Luo 2005. Hash Tables
Категорија:Хеширање