(#8) Chaining

                 මෙහිදී collision එකක් ඇතිවූ විට එම element  එක වෙනත් slot  එකකට යොමු කරයි. collision එක ඇතිවූ slot එක හා අළුත් element  එක store කළ slot එක අතර link එකක් තබා ගැනීමද සිදු කරයි.

          

Chaining වල ප්‍රධාන ආකාර තුනක් පවතියි.

 i) Separate Chaining

ii) Coalesced Chaining

iii) Overflow Area

 i) Separate Chaining

මෙහිදී හැම collisions ඇතිවන slot එකකටම link list එකක් සම්බන්ධ කර වැඩිපුර ලැබෙන elements , link list ඒක තුළ store කරනු ලබය

Chaining - Load Factor

      මෙහිදී table එකේ slot ප්‍රමාණයට වඩා වැඩි elements ප්‍රමාණයක් table ඒක තුළ store කරන නිසා load factor (α) , 1ට වඩා විශාල වීම සිදුවිය හැකියි.(α > 1)

Analysis of Chaining

Unseccessful Search

·        Link list එක තුළ අදාළ element ඒක නොමැති අවස්ථාව .

   

Search time = θ(1+α)

Successful Search

·        Link list එක තුළ අ

·        අදාළ element ඒක ඇති අවස්තාව.

  

  Search time = θ(1+α)

ii) Coalesced Chainig

   මෙය chaining හා linear probing යන දෙකෙහි එකතුවක් වශයෙන් සැලකිය හැකිය. Empty slot එකක් සොයාගෙන collision විසඳාගන්නා අතර නමුත් collision ඒක ඇතිවූ slot එකේ සිට element ඒක store කරන ලද slot එකට link එකක් තබාගනියි.

iii) Overflow Area

මෙහිදී table එකේ වෙනම කොටසක් collision සඳහා වෙන්කර තබයි. මෙහි ප්‍රධාන table ඒක primary area ලෙස හඳුන්වන අතර collision සඳහා වෙන්කර ඇති කොටස overflow area ලෙස හඳුන්වයි. Collision එකක් ඇති වූ විට එම element එක කලින් වෙන් කරන ලද overflow area එකේ ඇති slot එකක් තුළ store කරන අතර collision එක ඇතිවූ  slot එකට  link එකක් තබාගනියි.