02.Compression Map
මෙහිදී h1 මගින් සොයාගන්නාලද integer එක භාවිතා කොට store කිරීම සඳහා index number එකක් සොයාගැනීම සිදු කරයි.මෙහිද ප්රධආන ආකාර කිහිපයක් ඇත.
i.Division Method
ii.Mid-Square function
iii.Extraction
iv.Radix Transformation
v.Truncation
vi.MAD Method
i.Division
key එක k ලෙස ගනිමු. මෙහිදී බොහෝ විට mod කිරීම (modulus) සංඛ්යාවක් යම්කිසි සංඛ්යාවකින් බෙදා ශේෂය පිළිතුර ලෙස ලබා ගැනීම සිදු කරයි.බොහෝ විට key එක බෙදනු ලබන්නේ table size එකෙනි.එවිට ලැබෙන පිළිතුර හැමවිටම table size එකට වඩා කුඩා වීම එයට හේතුවයි.
h(k) = K mod TSize
K = { 44, 56, 79}
h: U → {0, 1, ..., 10 }
h( k ) = k mod 11
උදාහරණයක් ලෙස 44 යන key එක සලකා බලමු.
h( k ) = k mod 11
h( 44) = 44 mod 11
= 0
h( k ) = k mod m
m සඳහා අගයක් තෝරා ගැනීමේදී පහත නීති අනුගමනය කල යුතුය.
2 බලයන් m ලෙස යොදා නොගනියි.
decimal අගයන් keys ලෙස ඇති විට m සඳහා 10 බලයන් යොදා නොගනියි.
වඩාත් සුදුසු වන්නේ 2 බලයන්ට එතරම්ම සමීප නොවන ප්රථමක (prime ) සංඛ්යාය.
ii.Mid Square Function
key එක වර්ගකල ලැබෙන පිළිතුරෙහි මැද ඇති ඉලක්කම් කිහිපයක් index number එක ලෙස තෝරාගැනීම මෙහිදී සිදු කරයි.key එක string එකක්නම් hash code map වලදී යොදාගත් ක්රමයක් භාවිතා කරමින් ප්රථමයෙන් එය integer එකක් බවට පත්කරගෙන සිටිය යුතුය.
උදාහරණයක් ලෙස 3121 key එක ලෙස ඇතැයි සලකන්න
h (3121) = (3121)2 = 9740641
h(3121) = 406
iii.Extraction
key එක ඉතා විශාල සංඛ්යාවක් වන අවස්ථා වලදී ඉන් කොටසක් වෙන් කරගෙන index number එක ලෙස භාවිතා කරයි.මෙහිදී මුල කොටස ,මැද කොටස ,අග කොටස හෝ තෝරාගත් වෙනත් ඕනෑම කොටසක් භාවිතා කල හැකිය.
උදාහරණයක් ලෙස 123456789 යන key එක සලකන්න .
first four digits 1234
last four digits 6789
the first two combined with last two 1289 or
some other combination
iv.Radix Transformation
කිසියම් පාදයකින් ඇති key එකක් වෙනත් පාදයකට හරවා එය index එක ලෙස භාවිතා කිරීම මෙහිදී සිදු කරයි.පාදය වෙනස් කිරීමෙන් පසු ලැබෙන අගය විශාල වැඩිනම් එය mod කිරීම හෝ වෙනත් ක්රමයක් මගින් කුඩා අගයක් බවට පත්කරගත්හැකිය.
h(34510) = 4239
index number = 423
vi.Truncation
key එකේ ඇති part එකක් ඉවත් කර දමා ඉතිරිය index එක ලෙස භාවිතා කිරීමයි.
Employee number: 001364789
Table size: 1000
- h(x) = (last three digits) = 789
- h(x) = (digits 4, 6, 8) = 348
- h(x) = partition in 3-digits, add together,
and truncate
= (001) + (364) + (789) = 1154 and ignore last bit
vii.MAD
Multiple add and devide
මෙහිදී පහත දැක්වෙන ආකාරයේ සූත්රයක් භාවිතා කරයි.
h(k) = [(ak + b) mod p] mod n
n table size එකට වඩා කුඩා ප්රථමක (prime) සංඛ්යාවක් විය යුතුය.
a හා b ධන නිඛිල (integers) විය යුතුය.
a mod n ≠0 විය යුතුය ,නැතහොත් සියලුම සංඛ්යා b වල එකම අගයක් කරා map විය හැක.
Simple Uniform Hashing
ඕනෑම element එකක් තෝරාගත් slot එකකට යොමු වීමට ඇති සම්භාවිතාව සමාන නම් එය simple uniform hashing ලෙස හඳුන්වනු ලබයි.
Load Factor(α)
Hash function එකෙහි efficiency එක මැනීම සඳහා මෙය භාවිතා කරන අතර α හි අගය 1 ට ආසන්න වන තරමට function එකේ efficiency එක වැඩිය.
a = the number of elements stored in the table
the size of the table’s array
