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