{"id":3189,"date":"2025-06-06T02:12:12","date_gmt":"2025-06-06T02:12:12","guid":{"rendered":"https:\/\/diznr.com\/?p=3189"},"modified":"2025-06-06T02:12:12","modified_gmt":"2025-06-06T02:12:12","slug":"gate-cseit-database-collision-in-hashing-collision-hashing","status":"publish","type":"post","link":"https:\/\/www.reilsolar.com\/pdf\/gate-cseit-database-collision-in-hashing-collision-hashing\/","title":{"rendered":"GATE CSEIT\/Database\/Collision in Hashing Hashing collision."},"content":{"rendered":"

GATE CSEIT\/Database\/Collision in Hashing Hashing collision.<\/p>\n

[fvplayer id=”292″]<\/p>\n

Hashing and Collision Handling in Databases (GATE CSE\/IT)<\/strong><\/h3>\n

\u00a0What is Hashing?<\/strong><\/h3>\n

Hashing is a technique used in database indexing & data structures<\/strong> to store and retrieve data efficiently. It uses a hash function<\/strong> to convert keys into a fixed-size address (hash value).<\/p>\n

Formula for Hash Function:<\/strong><\/p>\n

h(K)=Kmod\u2009\u2009Mh(K) = K \\mod M<\/span>h<\/span>(<\/span>K<\/span>)<\/span>=<\/span><\/span>K<\/span><\/span>mod<\/span><\/span>M<\/span><\/span><\/span><\/span><\/span><\/p>\n

where:<\/p>\n

    \n
  • K<\/strong> = Key<\/li>\n
  • M<\/strong> = Number of available slots (bucket size)<\/li>\n<\/ul>\n

    Example:<\/strong> If we insert key 25<\/strong> into a hash table of size 10<\/strong> using h(K) = K mod 10<\/code>, we get:<\/p>\n

    h(25)=25mod\u2009\u200910=5h(25) = 25 \\mod 10 = 5<\/span>h<\/span>(<\/span>25<\/span>)<\/span>=<\/span><\/span>25<\/span><\/span>mod<\/span><\/span>10<\/span>=<\/span><\/span>5<\/span><\/span><\/span><\/span><\/span><\/p>\n

    So, 25 is stored in index 5<\/strong>.<\/p>\n

    \u00a0What is Collision in Hashing?<\/strong><\/h3>\n

    A collision<\/strong> occurs when two keys produce the same hash value.
    For example, if 25 and 35<\/strong> both hash to index 5<\/strong>, we have a collision.<\/p>\n

    Why Collisions Occur?<\/strong><\/p>\n

      \n
    1. Limited number of slots<\/strong> in the hash table.<\/li>\n
    2. Different keys hashing to the same index<\/strong>.<\/li>\n
    3. Poor hash function choice<\/strong>.<\/li>\n<\/ol>\n

      \u00a0Collision Handling Techniques<\/strong><\/h3>\n

      \u00a0Open Addressing (Probing Techniques)<\/strong><\/h3>\n

      The key is placed in an alternative location if a collision occurs.<\/p>\n

      (a) Linear Probing<\/strong><\/h4>\n

      \u00a0If a collision occurs, check the next available slot<\/strong> (i.e., h(K)+ih(K) + i<\/span>h<\/span>(<\/span>K<\/span>)<\/span>+<\/span><\/span>i<\/span><\/span><\/span><\/span>).
      Example:<\/strong> If 25<\/code> and 35<\/code> both hash to index 5<\/strong>, store 35<\/code> in 6<\/strong>.
      Issue:<\/strong> Clustering (many keys get stored together).<\/p>\n

      Formula:<\/strong><\/p>\n

      h(K,i)=(h(K)+i)mod\u2009\u2009Mh(K, i) = (h(K) + i) \\mod M<\/span>h<\/span>(<\/span>K<\/span>,<\/span>i<\/span>)<\/span>=<\/span><\/span>(<\/span>h<\/span>(<\/span>K<\/span>)<\/span>+<\/span><\/span>i<\/span>)<\/span><\/span>mod<\/span><\/span>M<\/span><\/span><\/span><\/span><\/span><\/p>\n

      (b) Quadratic Probing<\/strong><\/h4>\n

      \u00a0Checks the next available slot in a quadratic sequence<\/strong> (i\u00b2<\/code>).
      Example:<\/strong> If 25<\/code> hashes to 5<\/strong>, the next checked slots are (5+1\u00b2, 5+2\u00b2, 5+3\u00b2, …)<\/strong>.
      Reduces clustering but may lead to secondary clustering.<\/strong><\/p>\n

      Formula:<\/strong><\/p>\n

      h(K,i)=(h(K)+i2)mod\u2009\u2009Mh(K, i) = (h(K) + i^2) \\mod M<\/span>h<\/span>(<\/span>K<\/span>,<\/span>i<\/span>)<\/span>=<\/span><\/span>(<\/span>h<\/span>(<\/span>K<\/span>)<\/span>+<\/span><\/span>i<\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span>)<\/span><\/span>mod<\/span><\/span>M<\/span><\/span><\/span><\/span><\/span><\/p>\n

      (c) Double Hashing<\/strong><\/h4>\n

      \u00a0Uses two hash functions<\/strong> to reduce clustering.
      Example:<\/strong> If h1(K) = 5<\/code>, use a second function (h2(K)<\/code>) to determine the next slot.<\/p>\n

      Formula:<\/strong><\/p>\n

      h(K,i)=(h1(K)+i\u00d7h2(K))mod\u2009\u2009Mh(K, i) = (h1(K) + i \\times h2(K)) \\mod M<\/span>h<\/span>(<\/span>K<\/span>,<\/span>i<\/span>)<\/span>=<\/span><\/span>(<\/span>h<\/span>1<\/span>(<\/span>K<\/span>)<\/span>+<\/span><\/span>i<\/span>\u00d7<\/span><\/span>h<\/span>2<\/span>(<\/span>K<\/span>))<\/span><\/span>mod<\/span><\/span>M<\/span><\/span><\/span><\/span><\/span><\/p>\n

      \u00a0Separate Chaining (Linked List in Buckets)<\/strong><\/h3>\n

      \u00a0Each slot in the hash table stores a linked list<\/strong> of values.
      \u00a0If multiple keys hash to the same index, they are stored in a linked list<\/strong> at that index.
      Example:<\/strong> If 25<\/code> and 35<\/code> both hash to 5<\/strong>, they are stored in a linked list at index 5<\/strong>.<\/p>\n

      Advantage:<\/strong> Efficient for large hash tables.
      Disadvantage:<\/strong> Increased memory usage due to linked lists.<\/p>\n

      \u00a0Choosing the Best Collision Resolution Technique<\/strong><\/h3>\n
      \n\n\n\n\n\n\n\n\n
      Method<\/strong><\/th>\nPros<\/strong><\/th>\nCons<\/strong><\/th>\n<\/tr>\n<\/thead>\n
      Linear Probing<\/strong><\/td>\nSimple, easy to implement<\/td>\nCauses clustering<\/td>\n<\/tr>\n
      Quadratic Probing<\/strong><\/td>\nReduces clustering<\/td>\nMay not find empty slots<\/td>\n<\/tr>\n
      Double Hashing<\/strong><\/td>\nAvoids clustering<\/td>\nSlightly complex<\/td>\n<\/tr>\n
      Separate Chaining<\/strong><\/td>\nHandles collisions well<\/td>\nRequires extra memory<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n

      \u00a0Example GATE Question (Hashing Collision Handling)<\/strong><\/h3>\n

      Question:<\/strong> A hash function is defined as h(K) = K mod 10<\/strong>. Given keys 23, 43, 13, 27, 33<\/strong>, insert them using linear probing<\/strong> in a hash table of size 10.<\/p>\n

      Solution:<\/strong>
      Step 1:<\/strong> Compute hash values.<\/p>\n

      \n\n\n\n\n\n\n\n\n\n
      Key<\/th>\nHash Value (h(K) = K mod 10<\/code>)<\/th>\nPlacement (Using Linear Probing)<\/th>\n<\/tr>\n<\/thead>\n
      23<\/td>\n23 mod 10 = 3<\/code><\/td>\nSlot 3<\/strong><\/td>\n<\/tr>\n
      43<\/td>\n43 mod 10 = 3<\/code><\/td>\nCollision<\/strong> \u2192 Next slot 4<\/strong><\/td>\n<\/tr>\n
      13<\/td>\n13 mod 10 = 3<\/code><\/td>\nCollision<\/strong> \u2192 Next slot 5<\/strong><\/td>\n<\/tr>\n
      27<\/td>\n27 mod 10 = 7<\/code><\/td>\nSlot 7<\/strong><\/td>\n<\/tr>\n
      33<\/td>\n33 mod 10 = 3<\/code><\/td>\nCollision<\/strong> \u2192 Next slot 6<\/strong><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n

      Final Hash Table:<\/strong><\/p>\n

      \n
      Index: 0 1 2 3 4 5 6 7 8 9 <\/span>
      \nKeys: - - - 23 43 13 33 27 - - <\/span>
      \n<\/code><\/div>\n<\/div>\n

      \u00a0Conclusion<\/strong><\/h3>\n

      Hashing is essential for fast data access in databases.<\/strong>
      Collisions occur when multiple keys hash to the same index.<\/strong>
      Various techniques like open addressing & separate chaining help resolve collisions.<\/strong>
      Choosing the right method depends on efficiency, memory, and clustering avoidance.<\/strong><\/p>\n

      Would you like more examples or Python code implementations<\/strong>?<\/p>\n

      Here\u2019s a focused explanation on Collisions in Hashing<\/strong>, tailored for GATE CSE\/IT \u2013 Databases<\/strong>:<\/p>\n

      \n

      \ud83d\udd01 Collision in Hashing<\/h2>\n

      \ud83c\udfaf What is a Collision?<\/h3>\n

      A collision<\/strong> occurs when two different keys<\/strong> hash to the same index<\/strong> in the hash table.<\/p>\n

      \n

      Let h(k1) = h(k2)<\/code> but k1 \u2260 k2<\/code> \u2192 this is a collision<\/strong>.<\/p>\n<\/blockquote>\n

      Hash collisions are inevitable<\/strong> due to the pigeonhole principle<\/strong> when:<\/p>\n