Collision Resolution - Double Hashing Method

howdy today we will be going over the double hashing method our objective is to use the double hashing method to create a hash table from a given input the double hashing method uses the regular h of k function right here uh that we would use in any normal hash k mod array size plus a unique h2 of k function multiplied by i now the h2 function will be provided to us it's not something that we derive and i is simply a counter keeping track of the number of times our given input has attempted to go into the array but it collided so i begins at zero for any given input so let's begin by trying to add two h of two and what is our i now our i is zero because so far we haven't even tried to put two into the array it has not collided is equal to 2 mod 11 which is equal to 2. so we put it and actually before putting 2n we check is there a collision no so we put it next we move on to 8 h of 8 0 will equal 8 mod 11. is there a collision no h of 10 0 will equal 10 mod 11. is there a collision no and we go on h of 11 0 is equal to 11 mod 11 which is equal to 0 we know 11 divided by 11 produces no remainder so far we've got an easy and now we need to put in 13. 13 mod 11 is equal to 2. is there a collision yes there is right here we can't put it into two because it's already filled so the double hashing method says at this point you increment i by one or i plus plus and you retry the hash function with the new i so 13 now with one now our function changes a little we bring down the one from i zero because we're still going to do 13 mod 11 that's the function 13 mod 11 so we bring that value down and to it we add i which is 1 times our h2 function what is h2 7 minus k mod 7 that will be 7 minus 13 mod with 7. and all of that don't forget we mod that with the table size so 13 mod 7 will yield 6 and seven minus six we know is one times one will equal one two we have two uh plus one with 11 which will equal 3. do we have a collision no so we can put 13 into 3 now now we're done with 13. done with all of these and we're at 19. so i does not continue to be one here remember i keeps track of each inputs attempt to go into the array so we have a 219 with 0 19 mod 11 will yield 8. do we have a collision we do right here so the algorithm says increment i and try again so again we're going to bring the 8 down and then we're going to do i multiplied with 19 7 minus 19 mod 7 all of that modded with 11. now 19 mod 7 will be 19 minus 14 5 7 minus 5 will equal 2 then we will have 8 plus 1 times 2. mod 11. we have 10 mod 11 that is equal to 10. so we can just go ahead and put it into 10 right oh wait we have another collision here the double hashing method takes care of this for us it says if you have a collision increment i so we will increment i and we will try again now at this point we've already done a lot of work so we can just bring some values down because the only thing that changed is the term with i so we bring down 8 again like from here too and we add not 1 but 2 times the value we already calculated 2 7 minus 19 mod 7 that did not change now we have 8 plus 4 12 mod 11 is equal to one okay can we put it into one we can so 19. now for tony we can just say we can try it out first okay tony mod 11 will equal 9 and we can just go ahead and put that right in no problem and we're done creating the hash table using the double hashing method from this given input

Channel: Furkan

Views: 749

Rating: 5 out of 5

Keywords:

Id: viRQwo4V0b4

Length: 8min 12sec (492 seconds)

Published: Thu Apr 01 2021