(#5)Pigeonhole Principle

Pigeonhole Principle

පරවියන් රඳවා තබනු ලබන කුඩා කුටි  Pigeonholes  ලෙස හඳුන්වයි.අපි  n පරවියන් ප්‍රමාණයක් m Pigeonholes ප්‍රමාණයකට දමන්නේනම්  n > m  වෙයිනම් අඩු තරමින් එක Pigeonhole එකක හෝ පරවියන් එකකට වැඩියෙන් රැදී සිටිය යුතුය. මෙය Pigeonhole principle  ලෙස හැඳින්වෙයි.

මෙය සම්භාවිතා මූලධර්ම ඇසුරෙන් මෙලෙස පැහැදිලි කරගතහැකිය. n පරවියන් ප්‍රමාණයක් අහඹු ලෙස m Pigeonholes ප්‍රමාණයකට 1/m  යන ඒකාකාර සම්භාවිතාවකින් යුතුව දමන්නේ නම් එක Pigeonhole එකක හෝ පරවියන් එකකට වඩා රඳවා තබාගැනීමේ සම්භාවිතාව   

      1 – ( m_n/mⁿ)  වෙයි.

       මෙහි  m_n  = ^mC_n   වෙයි.

මෙලෙස එක Pigeonhole එකකට පරවියන් එකකට වඩා යොමුවීමක් collision එකක් ලෙස හඳුන්වයි. මෙමෙ මූලධර්මය අපි hash tables වලටද යෝදාගන්නෙමු.පහත උදාහරණයෙන් පැහැදිලිකරගනිමු.

• What is the probability that no two hash keys collide(එකම storage location එකකට hash keys දෙකක් යොමුවීම.)?

මෙහිදී අසනු ලබන්නේ keys දෙකක් එකම slot එකකට යොමු නොවීමේ සම්භාවීතාවයි.

 h(k) = k mod 5

slots  5ක් ඇති table එකක් සලකමු.

• පළමු item එක දැමීමේදී slot 5ම හිස් නිසා collide වීමක් සිදු නොවේ.එම නිසා collide නොවීමේ සම්භාවිතාව = 5/5 = 1 වෙයි.
• දෙවන item එක දැමීමේදී හිස්ව ඇත්තේ slot 4ක් පමණි.එම නිසා collide වීමේ සම්භාවිතාව  1/5 කි.
• එමනිසා collide නොවීමේ සම්භාවිතාව  = 4/5 ක්  වෙයි.

මෙලෙස,

• 3 වන item එක දැමීමේදී collide නොවීමේ සම්භාවිතාව  = 3/5
• 4වන item එක දැමීමේදී collide නොවීමේ සම්භාවිතාව  = 2/5
• 5 වන item එක දැමීමේදී collide නොවීමේ සම්භාවිතාව  = 1/5

එමනිසා collide නොවීමේ මුළු සම්භාවිතාව = 5/5 * 4/5 * 3/5 * 2/5 * 1/5

                                                                         = 0.0384

එමනිසා keys 5ක් add කිරීමේදී එක collision එකක්

හෝ ඇති වීමේ සම්භාවිතාව  = 1- P₅  = 1- 0.0384 = 0.9616

Collisions

hashing  වලදී මෙම collision ඇති කිරීම මගින් keys ප්‍රමාණයට වඩා slots අඩුවෙන් ඇති table එකක වුවද අපිට සියලුම keys store කරගතහැකිය. එමගින් අවශ්‍යකරන memory space එක අඩුකරගතහැකිය. යම්කිසි hash table එකක ඇතිවන collisions ප්‍රමාණය අවම වෙයිනම් hash table එක හොඳින් ක්‍රියා කරන්නේයැයි කියනු ලැබේ.එමගින් O(1) search time එකක් ලබාගතහැකිය.මෙහි worste case එක O(n) විය හැකිය.එය දුර්වල hash table එකක් ලෙස හඳුන්වයි.එමෙන්ම මෙම collisions විසඳා ගැනීමටද අප ක්‍රමවේදයන් කිහිපයක් අනුගමනය කරයි.

Handling the Collisions

i.Open Addressing

ii.Chaining

iii.Bucket Addressing