Comment
Author: Admin | 2025-04-28
H1(72) = 72 % 13 = 7, now this is a collision because the 7th location is already occupied, we need to resolve this collision using double hashing.hnew = [ h1(72) + i * h2(72) ] % 13= [ 7 + 1 * ( 1 + 72 % 11) ] % 13= 1Location 1st is already occupied in the hash-table, hence we again had a collision. Now we again recalculate with i = 2hnew = [ h1(72) + i * h2(72) ] % 13= [ 7 + 2 * ( 1 + 72 % 11) ] % 13= 8Location 8th is empty in hash-table and now we can place key 72 in there.Fifth key = 14, h1(14) = 14%13 = 1, now this is again a collision because 1st location is already occupied, we now need to resolve this collision using double hashing.hnew = [ h1(14) + i * h2(14) ] % 13= [ 1 + 1 * ( 1 + 14 % 11) ] % 13= 5Location 5th is empty and we can easily place key 14 there.Sixth key = 50, h1(50) = 50%13 = 11, 11th location is already empty and we can place our key 50 there.Since all the keys are placed in our hash table the double hashing procedure is completed. Finally, our hash table looks like the following,Why Use Double Hashing?Double Hashing is one of the popular collision resolution techniques. The other popular variants which serve the same purpose are Linear Probing and Quadratic Probing. But if other techniques are available, then why do we need double hashing in the first place?Double Hashing offers better resistance against clustering. A major reason for this is the use of dual functions. Dual functions enable double hashing to perform a more uniform distribution of keys, resulting in lower collisions.Advantages of Double Hashing in Data StructureAfter each collision, we recompute the new location for the element in the hash-table. For successive collisions, this generates a sequence of locations. If the sequences are unique then the number of collisions are less.Double Hashing creates most unique sequences, providing a more uniform distribution of keys within the hash-table.If the hash function is not good enough, the elements tend to form grouping in the hash-table. This problem is known as clustering. Double Hashing is least prone to clustering.Practice Problem Based on Double HashingProblem Statement 1:Given the two hash functions,h1(k) = k mod 23 and h2(k) = 1 + k mod 19. Assume the table size is 23. Find the address returned by double hashing after 2nd collision for the key = 90.Solution:We will use the formula for double hashing-h(k,i) = ( h1(k) + i * h2(k) )%mAs it is given, k = 90,
Add Comment