(#3) Hash Function (i)

Hash function 

hash function එක අප බොහෝවිට functions දෙකක එකතුවක් මගින් සාදාගනුලබයි. hash function එක h නම් 

  

       h(x)  =  h₂(h₁(x))

 ලෙස වෙයි. මෙහිදී අපට store කිරීමට අවශ්‍ය කරන key එක integer එකක් බවට පත්කරගැනීම h₁ function එකෙන් සිදු කරනු ලබයි.එම සොයාගනු ලබන integer  එක h₂  function  එකට ආදේශ කළ  විට එම key එකට අදාළ index number එක ගණනය කරගනු ලැබේ. Hash function එක සාදාගැනීමට අවශ්‍යකරන sub functions දෙක සාදාගන්නා ආකාර කිහිපයක් ඇත.මේවා ප්‍රධාන කොටස් දෙකකට බෙදා දැක්විය හැකිය.

1.     Hash Code Map (h₁ සෑදීමට බෝහවිට යොදාගනියි.)

2.     Compression Map (h₂ සෑදීමට බොහෝවිට යොදාගනියි.)

Perfect Hash Function

 Search time එක O (1) වනපරිදි hash function එකක් ගොඩනැගිය හැකිනම් එවනි function එකකට  perfect hash function එකක්යැයි  කියනු ලැබේ.

01.Hash Code Map

                               i.            Integer Cast

                             ii.            Summing Components

                          iii.            Polynomial Accumilation

අපට store  කිරීමට අවශ්‍ය කරන key එකේ ඇති කුමක් හෝ attribute එකක් භාවිතා කරමින් එය integer එකකට පරිවර්තනය කරගැනීම මෙහිදී සිදු කරයි. උදාහරණයක් ලෙස store කලයුතු වන්නේ වචනයක්නම් එහි අකුරු වල ASCII values වල එකතුව යොදාගැනීම හෝ bit size එක යොදාගැනීම වැනි දෑ දක්වියහැකිය.

i.Integer Cast

මෙමගින් key එකේ වෙනත් data type එකකින් ඇති bit, integer එකක් බවට convert කරගැනීම සිදු කරයි.key එක ඇති data type එක integer  data type එකට වඩා කුඩා bit size එකක් ඇති data type එකක්නම්  මෙම ක්‍රමය වඩාත් සුදුසුවෙයි..(උදා; byte, short, int, float in java)  long සහ doube සඳහා මෙමෙ ක්‍රමය සුදුසු නොවේ.

         

                          •  int intKey = (int) „A‟; /* intKey = 65 */

                          •   char charKey = (char) 78;

                               /* charKey = „N‟ */

Integer Casting මගින් යම්කිසි වෙනත් data type එකක් integer එකක් බවට පත්කිරීම සිදුකලහැකිය.මෙහිදී සිදුකරනු ලබන්නේ එයයි.වෙනත් data type එකක ඇති key එක integer එකක් බවට පත්කළ එය කෙලින්ම key එක store කිරීමට අවශ්‍ය කරන array index number  එක ලෙස යෝදාගතහැකිය.

ii.Summing Components

key එක string  එකක් වන අවස්ථා වලදී මෙය භාවිතා කලහැකිය.එවිට string එකේ ඇති characters වල ASCII values වල එකතුව ලබාගනියි.එම ලැබෙන එකතුව key එක store කරන array index number එක ලෙස යොදාගනියි.key එක ලෙස පහත වචන ඇති අවස්ථා සලකන්න.එවිට එමගින් array index number එක සාදාගන්නා ආකාරය පහත උදාහරණවලින් දක්වා ඇත.

iii.Polinomial Accumilation

මෙහිදී key එකේ ඇති යම් යම් attributes භාවිතා කරමින් polynomial එකක් (බහුපදයක් ) සාදාගැනීම සිදු කරයි.

 x₀a^k-1 +  x₁a^k-2  +……+ x_k-2a  + x_k-1  

 x_k-1 +  a(x_k-2 + a(x_k-3 +…..+ a(x₂ + a x₀))… )

  උදාහරණයක් ලෙස key එකට string එකක් ඇති අවසථාවක්  සලකමු.

එවිට , k = string එකේ ඇති characters ගණන

          x = character වල ASCII value එක

          a = string length එක 2න් බෙදූ විට ලැබෙන  අගය ලෙස ගනිමු.

x₀a^k-1 +  x₁a^k-2  +……+ x_k-2a  + x_k-1  

උදා: NOTE  යන වචනය key එක ලෙස ඇතැයි සලකන්න.

එවිට ,

k  = 4

a = 1

x₀= 78, x₁ = 79, x₂ = 84, x₃ = 69

Index number =  x₀a^k-1 +  x₁a^k-2  +……+ x_k-2a  + x_k-1  

                        =     78(2)^4-1  + 79 (2)^4-2  + 84 (2)^4-3  + 69 (2)^4-4

                                    =     78 (2)³     + 79(2)²    + 84 (2)¹   + 69(2)⁰ 

                        =     78* 8 + 79 * 4 + 84* 2 + 69 *1

                        =     624 + 316 + 168 + 69

                        =   1177

දැන් NOTE යන string එක array එකෙහි 1177 වන index එක තුල store කල හැක.