(#7) Open Adressing (ii)

02.Qudratic Probing

මෙහිදී අප යොදාගන්නා ප්‍රධාන hash function එක භාවිතයෙන් table එකට keys map කරගනියි.collision එකක් සිදු වූ විට එය විසඳා ගැනීම සඳහා තවත් විශේෂිත වූ function එකක් යොදාගනියි. එය පහතින් දැක්වෙයි.

  c(1) = h(k) + i²

  c(2) = h(k) - i²

මෙහි i යනු 1,2,3,……(T_size-1)/2 දක්වා වූ පූර්ණ සංඛ්‍යාය.

h(k) function එක මගින් ලැබෙන slot number  එක පිරී ඇත්නම් ප්‍රථමයෙන් එම ලැබුණු number එකට 1²  (h(k) + i² ) එකතු කරයි.එමගින් ලැබෙන slot එකද පිරී ඇත්නම් ප්‍රථමයෙන්ම ලැබුණු අගයෙන් 1² අඩු කර බලයි. (h(k) - i²) එවිට ලැබෙන අගය ඍන අගයක්නම් එයට table size එක එකතු කරයි.එසේ ලැබුණු slot එකද පිරී ඇත්නම් නැවතත්  2²  එකතු කර බලයි. මෙලෙස හිස් slot එකක් ලැබෙනතුරු i සවල අගය වැඩි කරමින් i= (T_size-1)/2 දක්වා අගයන් ආදේශ කර බැලීම සිදු කරයි.

පෙර සාකච්චා කරනලද උදාහරණයම මෙම ක්‍රමයෙන් විසඳා බලමු.

h1(key) = key mod m

Insert the keys {22, 1, 13, 11, 24, 33}

       h(22) = 22 mod 11 = 0

        h(1) = 1 mod 11     = 1

        h(13) = 13 mod 11 = 2

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

දැන් 0ට 1² එකතු කර බලයි.

   h(11)  + 1²  = 0 + 1²   = 1 ß පිරී ඇත

   h(11)  - 1²  = 0 - 1²   = -1ß මෙය ඍන අගයකි.ඍන අගයක් ලැබුණු විට එයට table size එක එකතු කල යුතුය.

     h(11)  - 1²  + T_size   =  -1 + 11 = 10

10 හිස්වන අතර එමනිසා එහි 11 store කරනු ලැබේ.

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

          h(24)  + 1²  = 2 + 1 = 3

3වන slot එක හිස් වන අතර එහි 24 store කරයි.

  

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

   h(33)  + 1²  = 0 + 1²   = 1 ß පිරී ඇත

   h(33)  - 1²  = 0 - 1²   = -1ß මෙය ඍන අගයකි.

    h(33)  - 1²  + T_size   =  -1 + 11 = 10 ß මෙයද පිරී ඇත.

දැන් 2² එකතු කර බලයි.

       h(33)  + 2²  = 0 + 2²   = 4 මෙම slot එක හිස් වන අතර එමනිසා මෙහි 33 store කරනු ලැබේ.

03.Double hashing

මෙහිදී ප්‍රථම hashing function එකෙන් key එකට අදාළ slot එක සොයාගන්නා අතර collision එකක් ඇති උවහොත් දෙවන hashing function එකක් සාදාගෙන ප්‍රථම හා දෙවන hashing functions දෙකම සංයුක්ත කර සාදනු ලබන අලුත් hashing function එකක් භාවිතයෙන් index සොයයි.

    h₁(k)  = k mod m

    h₂(k)  = [k mod (m-1)] + 1

h(k, i) = [h₁(k) + i*h₂(k)] mod m

මුලින්ම h₁ function එක යොදාගෙන අදාළ slot එක සොයාගනියි.collision ඇතිවුවහොත්

h(k, i) function එක යොදාගෙන හිස්ව පවතින වෙනත් slot එකක් සොයාගනියි.පෙරලෙසම මෙහිද

  I = 1,2,3,……(T_size-1)/2  වෙයි.

කලින් ක්‍රමයේදී ලෙසම i = 1 යෙදු විට ලැබෙන slot එක හිස් නොමැතිනම් i= 2 යොදා බලයි.මෙලෙස හිස් slot එකක් ලැබෙනතුරු අගයන් ආදේශ කර බලයි.

පෙර උදාහරණයම මෙම ක්‍රමයෙන්ද විසඳා බලමු.

Insert the keys {22, 1, 13, 11, 24, 33}

    h₁(k)  = k mod m

    h₂(k)  = [k mod (m-1)] + 1

h(k, i) = [h₁(k) + i*h₂(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 ßcollision

දැන් 

h(k, i) = [h₁(k) + i*h₂(k)] mod m

h(11,1) = [h₁(11) + 1*h₂(11)] mod 11

                = [0 + 1 * {(11 mod 10) + 1}] mod 11

                = [0 + 1 * 1 + 1}] mod 11

                =  2 mod 11

                = 2 ß not empty

දැන් i=2 යොදා බලයි.

         h(11,2) = [h₁(11) + 2*h₂(11)] mod 11

                = [0 + 2 * {(11 mod 10) + 1}] mod 11

                = [0 + 2 * 2}] mod 11

                =  4 mod 11

                =4 දැන් 11 , 4 වන slot එකෙහි store කරයි.

 

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

            h(24,1) = [h₁(24) + 1*h₂(24)] mod 11

                = [2 + 1 * {(24 mod 10) + 1}] mod 11

                = [2 + 1 * (4 + 1)}] mod 11

                =  7mod 11

                = 7

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

            h(33,1) = [h₁(33) + 1*h₂(33)] mod 11

                = [0 + 1 * {(33 mod 10) + 1}] mod 11

                = [0 + 1 *( 3 + 1)}] mod 11

                =  4 mod 11

                = 4 ß not empty

            h(33,2) = [h₁(33) + 2*h₂(33)] mod 11

                = [0 + 2 * {(33 mod 10) + 1}] mod 11

                = [0 + 2 * 4}] mod 11

                =  8 mod 11

                =8

Open Addressing load factor (α)

මෙහිදී slot එකක ගබඩා කරන්නේ එකම element එකක් පමණක් නිසා load factor එක එකට වඩා වැඩිවිය නොහැක.

Analysis of Open Addressing

Unsuccessful Search

•Expected no. of probes required to find an empty location is at most {1/(1- α)}.

Successful Search

•Expected no. of probes in a successful search is at most {1/α ln 1/ (1- α)}.

Consider an open-address hash table with a load factor α. Find the nonzero value α for which the expected number of probes in an unsuccessful search equals twice the expected number of probes in a successful search.

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