(#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 වීම සිදුවෙයි.