(#4) Hash Function (ii)

02.Compression Map

මෙහිදී h₁  මගින් සොයාගන්නාලද 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)²   = 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(345₁₀) = 423₉

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