2-изборно хеширање

2-изборно хеширање, такође познато као и 2-изборно уланчавање, је варијанта хеш табеле у којој се кључеви додају уз помоћ две хеш функције. Кључ се ставља на позицију у низу са најмање подударања. Потребна некаква метода решавања колизије, осим ако се кључеви чувају у скуповима. Искоришћеност ресурса у просечном случају успешне претраге је O(2 + (m-1)/n), m је број кључева а n је величина низа. Највећи могућ број колизија је $\log _{2}\ln n+\theta (m/n)$ са великом вероватноћом.

Како ради

2-изборно хеширање користи две хеш функције h1(x) и h2(x). Те две хеш функције треба да буду независне једна од друге и да немају ништа што их повезује. Захваљујући коришћењу две хеш функције било који integer x има две потенцијалне локације на коју могу да се складиште на основу иѕлаѕа функција h1(x) и h2(x). Иако постоје две хеш функције, још увек постоји само једна хеш табела, и обе функције уписују кључеве у исту табелу.

Имплементација

Најбитније стране ове хеш имплементације су уметање и претрага.

Уметање: Кад умећемо вредности обе хеш функције се рачунају се објекат који треба да се уметне. Објекат се затим ставља у скуп са мање објеката. Ако су скупови једнаке величине, подразумевана локација је h1(x) вредност.

Претрага: Ефикасне претраге се врше проверавањем оба скупа, тј. локације скупова на које су h1(x) и h2(x) мапиране за жељену вредност.

Брзина и ефикасност

Као што је случај са свим хеш табелама, учинак се посматра на највећем скупу. Иако има случајева где величине скупова могу да буду велике на основу вредности и хеш функција које се користе, то је ретко. Захваљујући коришћењу две хеш функције имамо две могуће локације за сваку вредност, због чега постоји још мања вероватноћа да ће дође до великих скупова. Очекивана величина скупа приликом коришћења 2-изборног хеширања је : θ(log(log(n))).

Битно: Принцип коришћења више хеш функција је оптимизиран помоћу две хеш функције. Неће доћи до побољшања ако се број хеш функција повећа - 3 хеш функције нису ефикасније 2.

Литература

• Paul E. Black, 2-choice hashing at the National Institute of Standards and Technology, Dictionary of Algorithms and Data Structures.