(#6) Open Addressing (i)

Open Addressing

මෙහිදී සියලුම elements අදාළ hash table එකේම store කරගැනීම සිදුකරනුලබයි.

යම්කිසි key එකක් element එකක් store වී ඇති slot එකකට යොමු වූ විට එම key එක නැවත element එකක් store වී නොමැති slot එකකට යොමු කිරීම මගින් collisions විසඳා ගැනීම සිදු කරනු ලබයි.මෙහිදී collisions විසඳා ගැනීමට ප්‍රධාන ක්‍රමවේදයන් 3ක් අනුගමනය කරයි.

01.Linear Probing

02.Quadratic Probing

03.Double Hashing

01.Linear Probing

මෙහිදී hash function එකෙන් ලබාදෙන slot එක වෙත ප්‍රථමයෙන්ම element එක යොමුකරනු ලබයි.එම slot එක හිස් එකක් නොවුනහොත් එතැන් සිට පහලට ඇති slots සියල්ලම check කරගෙන යන අතර හමුවන ප්‍රථම emphty slot එකෙහි element එක store කරයි.අපි මෙය පහත උදාහරණය මගින් පැහැදිලි කරගනිමු.

Given a hash table with m=11 entries and the following hash function h1

          h1(key) = key mod m

Insert the keys {22, 1, 13, 11, 24, 33} in the given order (from left to right) to the hash table

මෙහිදී ප්‍රථමයෙන් hash function එකට key values ආදේශ කර slot එක සොයාගත් යුතුය. 

  h  h(k) = 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 ß මෙම slot එක දැනටමත් පිරී ඇත (collision)

මෙවිට එතැන් සිට පහලට ඇති slot check කරගෙන යන අතර 1 හා 2 ද පිරී ඇති නිසා

ප්‍රථමයෙන් හමුවන empty slot එක වන්නේ 3යි .එමනිසා 3 වන slot එකෙහි 11 store කරනු ලැබේ.

        h(24) = 24mod 11 = 2 ß collision

2වන slot එක පිරී ඇති අතර එතැන් සිට පහලට check කරගෙන යයි. 3වන  slot එකද පිරී ඇති නිසා ප්‍රථමයෙන් අහුවන හිස් slot එක්වන 4හි 24 store කරයි.

              h(33) = 33mod 11 = 0 ß collision

0 පිරී ඇත. empty slot එකක් ලැබෙනතුරු පහලට check කරගෙන යයි. 0 සිට 4 දක්වා slot සියල්ලම පිරී ඇත.ප්‍රථමයෙන් සිදුවන හිස් slot එක වන්නේ 5යි එමනිසා එහි 33 store කරයි.

Algorithm

Hash-Insert(T,k)

i ß 0

repeat j ß h(k,i)

if T[j] = NIL

then T[j] ß k

return j

else i ß i + 1

until i = m

Error “ hash table overflow”

Hash-Search(T,k)

i ß 0

repeat j ß h(k,i)

if T[j] = k

then return j

i ß i + 1

until T[j] = NIL or i = m

return NIL

මෙය implement  කිරීමට පහසු ක්‍රමයක් වන අතර , නමුත් primary clustering යන ගැටලුව මතුවියහැකිය.එනම් store කිරීමට ප්‍රමාණවත් slot ප්‍රමාණයක් නොමැති වීම නිසා ඇතිවන ගැටලුවකි.clustering නිසා average search time එක  increase වීම සිදුවෙයි.

(#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

(#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 කල හැක.

(#2)Intruduction to Hashing

Searching  Algorithms

computer  science වලදී ගොඩක් වැදගත් දෙයක් තමයි searching algorithms කියල කියන්නේ.  විවිධ list වලින්  arrays වලින් items search කරගන්න අපිට සිද්දවෙනවා.එතැනදී යම්කිසි item එකක් අඩුම කාලයකින් සොයාගන්න searching algorithms භාවිතා කරනවා.මේ searching algorithms ප්‍රධාන වර්ග දෙකකි.

I)                    Sequential search

II)                  Binary search

i)Sequantial search

අදාළ item එක හමුවනතුරු list එකක් හෝ array එකක් දිගේ අනුපිළිවෙලින් සොයාගෙන යාමයි.

Best Case  O(1)

Worste Case  O(n)

ii)Binary search

list එක ප්‍රධාන කොටස් දෙකකට කඩා ඒ ඔස්සේ සොයාගෙන යාමයි. මේ සඳහා බොහෝ විට binary search tree එක උපයෝගී කරගනියි.

Best Case  O(1)

Worste Case  O(logn)

Comparison

                                                                         Insert                    Search

Ordered Array                                                   O(N)                      O(logN)

Ordered list                                                        O(N)                      O(N)

Unordered array                                                 O(1)                       O(N)

Unordered list                                                     O(1)                       O(N)

Different  Approach for Seaching

ඉහත ක්‍රමවල running time එක වැඩිවන අතර search එකේ efficiency එක අඩුවන නිසා search කිරීම සඳහා වෙනත් ක්‍රමයක් සොයාගන්නා ලදී.මෙහිදී අදාළ items ,araay එකක ගබඩා කරන අතර, අදාළ array index number එක item එක ඉදිරියෙන් සටහන්කර වෙනම table එකක් සාදාගනී.ඉන්පසු item එකක් සොයාගැනීමට අවශ්‍ය වූ විට table එක මගින් අදාළ item එක store කරා ඇති index number එක සොයාගත හැකිය.search time එක O(1) දක්වා අඩුකරගනීමටද හැකියාව ලැබෙයි.මේ ක්‍රමය සඳහා ප්‍රධාන වශයෙන් tables වර්ග දෙකක් යදාගනියි.

01.Direct Access Table

02.Hash Table

Key and universel set

මෙහිදී අපි key එකක් යන සංකල්පය භාවිතා කරයි.key එකක් යනු අපි store කරන item එක හැඳින්වීමට යොදාගන්නා සංකේතයකි. අපිට store කිරීමට අවශ්‍ය keys සියල්ලම ඇති set එක  universel set එක ලෙස හඳුන්වයි. එය (U) වලින් සංකේත කරයි.අපි එය උදාහරණයක් මගින් පැහැදිලිකරගනිමු.

අපිට 1 සිට 100 දක්වා වූ integer numbers වලින් තෝරාගත් 50 ක් array එකක store කළයුතුව තිබේයැයි  සලකන්න.එවිට අපි store කරන 1සිට  100දක්වා වූ integers , ‘keys’ ලෙස හඳුන්වන අතර ,මේ integers 100ම  අඩංගු  set  එක univesel set (universe) ලෙස හඳුන්වයි.මන්දයත් අප store කිරීමට තෝරාගන්නා integers ,50න්  ඕනෑම එකක් මෙම set එකට අයිතිවන නිසාය.

01.   Direct access table

Assumptions(උපකල්පන )

i.සෑම  key value එකක්ම අනන්‍ය වෙයි.(එක වගේ keys 2 ක් තිබිය නොහැකිය.)

ii.සෑම key එකක්ම universel set එකෙන් තෝරාගනියි.

Idea

Items ,Array එක තුළ store කරන අතර ,array එකෙහි  store කරනලද ස්ථානය හඳුනාගනුලබන  index number එක  key  එක මගින් ලබාදෙනු ලබයි.

•   T[0,1,….,m-1] යන array  එකක් සලකමු .(nodes  m ගණනක් ඇත.)
•   T වල ඇති සෑම slot එකක්ම U (universel set) එකේ ඇති key එකක් සමඟ සම්බන්ධය.
•   දැන් key එක k  වන x  element එකක් සලකමු.එවිට එය array  එකෙහි store  කර ඇති ස්ථානය  T[k]වලින් දක්වනු ලබයි.(array එකෙහි index number එක.)

                                           

•         අපි අදාළ element එක (x ) search කරගෙන යාමේදී T [k] null නම් එනම් එම slot එකෙහි item               එකක් නොමැතිනම් ,එවනි item එකක් ලිස්ට් එකේ නොමැති බව තහවුරු කරගතහැකිය.

   අවාසි

• store කලයුතු item ප්‍රමාණය array size එකට වඩා වැඩිනම් සියලුම items  store කල නොහැකිය.
• store කලයුතු item ප්‍රමාණයට සාපේක්ෂව array size එක ඉතා විශාලනම් විශාල වශයෙන් ඉඩ අපතේ යා හැකිය. (U <<<< T)

Hash Table

• key එකට අදාළ slot එක select කිරීම සඳහා function එකක් යොදාගනියි .එය h ලෙස හඳුන්වයි.
• එවිට key එක k වන  element එක store කරන slot එක h (k) වෙයි.
• මෙහි h යනු hash function එක වන අතර එයට key එක ආදේශ කලවිට එමගින් එය store කලයුතු slot එකේ index number එක ලබාදෙයි. 

                  T[0,1,2,.......,m-2,m-1]

                  h  :  U --> {0,1,...,m-1}

එවිට k යන key එක h(k) වලට hash කාලයයි කියනු ලැබේ.

වාසි

• අවශ්‍ය කරන array indexes පරාසය අඩු කරයි.
• storage space එකද අඩු කරයි.

·