02.Qudratic
Probing
මෙහිදී අප යොදාගන්නා ප්රධාන hash function එක භාවිතයෙන් table එකට keys map කරගනියි.collision එකක් සිදු වූ විට එය විසඳා ගැනීම සඳහා තවත් විශේෂිත
වූ function
එකක් යොදාගනියි. එය පහතින් දැක්වෙයි.
c(1) = h(k) + i2
c(2) = h(k) - i2
මෙහි i යනු 1,2,3,……(Tsize-1)/2
දක්වා වූ පූර්ණ සංඛ්යාය.
h(k) function එක මගින් ලැබෙන slot number එක පිරී ඇත්නම් ප්රථමයෙන් එම ලැබුණු number
එකට 12 (h(k) + i2 )
එකතු කරයි.එමගින් ලැබෙන slot එකද පිරී ඇත්නම් ප්රථමයෙන්ම ලැබුණු අගයෙන් 12 අඩු කර බලයි. (h(k) - i2) එවිට ලැබෙන අගය ඍන අගයක්නම් එයට table size එක එකතු කරයි.එසේ ලැබුණු slot එකද පිරී ඇත්නම් නැවතත් 22 එකතු
කර බලයි. මෙලෙස හිස් slot එකක් ලැබෙනතුරු i සවල අගය වැඩි කරමින් i= (Tsize-1)/2
දක්වා අගයන් ආදේශ කර බැලීම සිදු කරයි.
පෙර සාකච්චා කරනලද උදාහරණයම මෙම ක්රමයෙන් විසඳා
බලමු.
h1(key) = key mod m
Insert the keys {22, 1,
13, 11, 24, 33}
h(22) = 22 mod 11 = 0
h(1) = 1 mod 11 = 1
h(13) = 13 mod 11 = 2
h(11) = 11 mod 11
=0 ßcollision
දැන්
0ට 12 එකතු කර බලයි.
h(11) + 12 = 0 + 12 = 1 ß පිරී ඇත
h(11) - 12 = 0 - 12 = -1ß මෙය ඍන අගයකි.ඍන අගයක් ලැබුණු විට එයට table size එක එකතු කල යුතුය.
h(11) - 12 + Tsize
= -1 + 11 = 10
10 හිස්වන
අතර එමනිසා එහි 11 store කරනු ලැබේ.
h(24)
= 24mod 11 = 2 ß collision
h(24) + 12 = 2 + 1
= 3
3වන
slot එක හිස් වන අතර එහි 24 store කරයි.
h(33) = 33mod 11 = 0 ß collision
h(33) + 12 = 0 + 12 = 1 ß පිරී ඇත
h(33) - 12 = 0 - 12 = -1ß මෙය ඍන අගයකි.
h(33)
- 12 + Tsize
= -1 + 11 = 10 ß මෙයද පිරී ඇත.
දැන්
22 එකතු කර බලයි.
h(33) +
22 = 0 + 22 = 4 මෙම slot එක හිස් වන අතර එමනිසා
මෙහි 33 store කරනු ලැබේ.
03.Double hashing
මෙහිදී
ප්රථම hashing function එකෙන්
key එකට අදාළ slot එක සොයාගන්නා අතර collision එකක් ඇති උවහොත් දෙවන hashing function එකක් සාදාගෙන ප්රථම හා
දෙවන hashing functions
දෙකම සංයුක්ත කර සාදනු ලබන අලුත් hashing function එකක් භාවිතයෙන් index සොයයි.
h1(k) = k mod m
h2(k) = [k mod (m-1)] + 1
h(k, i) = [h1(k) + i*h2(k)]
mod m
මුලින්ම h1 function එක යොදාගෙන අදාළ slot එක
සොයාගනියි.collision ඇතිවුවහොත්
h(k, i) function එක යොදාගෙන හිස්ව පවතින වෙනත් slot එකක්
සොයාගනියි.පෙරලෙසම මෙහිද
I = 1,2,3,……(Tsize-1)/2
වෙයි.
කලින් ක්රමයේදී ලෙසම i = 1 යෙදු විට ලැබෙන slot එක
හිස් නොමැතිනම් i= 2 යොදා බලයි.මෙලෙස හිස් slot එකක් ලැබෙනතුරු අගයන් ආදේශ කර
බලයි.
පෙර උදාහරණයම මෙම ක්රමයෙන්ද විසඳා බලමු.
Insert the keys {22, 1,
13, 11, 24, 33}
h1(k) = k mod m
h2(k) = [k mod (m-1)] + 1
h(k, i) = [h1(k) + i*h2(k)]
mod m
h(22) = 22 mod 11 = 0
h(1) = 1 mod 11 = 1
h(13) = 13 mod 11 = 2
h(11) = 11 mod 11
=0 ßcollision
දැන්
h(k, i) = [h1(k) + i*h2(k)]
mod m
h(11,1) = [h1(11) + 1*h2(11)]
mod 11
= [0 + 1 * {(11 mod 10) + 1}] mod 11
= [0 + 1 * 1 + 1}] mod 11
= 2 mod 11
= 2 ß not empty
දැන් i=2 යොදා බලයි.
h(11,2) = [h1(11) + 2*h2(11)] mod 11
= [0 + 2 * {(11 mod 10) + 1}] mod 11
= [0 + 2 * 2}] mod 11
= 4 mod 11
=4 දැන් 11 , 4 වන slot
එකෙහි store කරයි.
h(24)
= 24mod 11 = 2 ß collision
h(24,1) = [h1(24)
+ 1*h2(24)] mod 11
= [2 + 1 * {(24 mod 10) + 1}] mod 11
= [2 + 1 * (4 + 1)}] mod 11
= 7mod 11
= 7
h(33)
= 33mod 11 = 0 ß collision
h(33,1) = [h1(33)
+ 1*h2(33)] mod 11
= [0 + 1 * {(33 mod 10) + 1}] mod 11
= [0 + 1 *( 3 + 1)}] mod 11
= 4 mod 11
= 4 ß not empty
h(33,2) = [h1(33) + 2*h2(33)]
mod 11
= [0 + 2 * {(33 mod 10) + 1}] mod 11
= [0 + 2 * 4}] mod 11
= 8 mod 11
=8
Open Addressing load factor (α)
මෙහිදී slot එකක ගබඩා
කරන්නේ එකම element එකක් පමණක් නිසා load factor එක එකට වඩා වැඩිවිය
නොහැක.
Analysis of Open Addressing
Unsuccessful Search
•Expected no. of probes required to find an
empty location is at most {1/(1- α)}.
Successful Search
•Expected no. of probes in a successful search
is at most {1/α ln 1/ (1- α)}.
Consider an open-address hash table with a
load factor α. Find the nonzero value α for which the expected number of probes
in an unsuccessful search equals twice the expected number of probes in a
successful search.
