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

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

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

Као код линеарног попуњавања, циклусно пребројавање почиње од почетне вредности за одређени интервал. Тај интервал се одређује помоћу две хеш функције, примарне 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 . Bradford и Katehakis[1] показали су да је очекивани број провера за неуспешне претраге у табели једнак \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

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

Види још[уреди]

Референце[уреди]

  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

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