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

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

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

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


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

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

Нека је број елемената смештених у . Тада је фактор складиштења табеле .

Нека је . Бредфорд и Мајк Катехакис[1] показали су да је очекивани број провера за неуспешне претраге у табели једнак .

Ефикасност и проблеми[уреди | уреди извор]

Предност линеарног и квадратног попуњавања је у томе што су ове две технике успеле да искористе погодности које пружа кеш података (енгл. 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
}

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

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

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

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

Види још[уреди | уреди извор]

Референце[уреди | уреди извор]

  1. ^ 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

Спољашње везе[уреди | уреди извор]