(#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 එකද අඩු කරයි.

·