8.3 Hashing: Double Hashing | Collision Resolution technique | Data Structures and algorithms

hi guys welcome back today's topic is double hashing technique which is used to resolve the collision we have already discussed linear probing technique and quadratic probing technique okay please watch out those videos I will provide you the link below in the description box so let us start with double hashing technique I am going to take the same example these are our keys 3 2 9 6 11 13 7 into L M is 10 that is hash table Lucas eyes Joha that is 10 and our hash function is 2k plus 3 in the same one okay and we will use use the division method okay and double hashing technique to insert these elements as the name suggests see this double hashing technique means you are supposed to apply two times hash function so you are given two hash functions one is given this one h 1k 2k plus 3 and second hash function is given that is H 2k 3k plus 1 that is why it is known as double hashing to hash function you are given H 1 K and H 2 K now what is the formula here in double hashing technique if collision comes ok then you will apply double hashing technique and where you will insert that element where collision comes see insert ki at first free place from u plus V into I mod M okay and here is I will range from 0 to M minus 1 this is the simple rule see what was there in linear probing technique you have inserted insert ki at first free place from from nu plus I mod M this was a linear probing ok you you know the location will calculate using this hash function when you apply this hash function on these keys there then you will find out one location and that location we have you have denoted that location with u u plus I I is same as 0 to n minus 1 M is the size of hash table and mod M this was a linear problem what was there in quality probing it was u plus I square mod M insert ki at first free space from u plus I squared mod and this was the only difference but what is there in in double hashing technique you have to insert ki at first free place from u plus V into I then mod M we already know what is U what is I what is M but what is V now ok now here the double hashing front accounts you will calculate the value of V using that second hash function and where the value of u we would be calculated we would be calculated like this V is equal to H 2 K mod him okay because we are using this division method H 2 K whatever the second hash function is given more and this is how you will calculate this V so we have will have this you also then we can calculate V also I would have a 0 to n minus 1 and M also we have then we can easily resolve the collision ok now let's start see we have this the size of hash table is what 10 suppose this one is our hash tables from zero one two three four five six seven eight nine okay from zero to nine we have this one go one two three four five six seven eight nine this one is our hash table okay now calculate what is four first key key is three and now we will calculate the location where you can insert this three in this hash table and that thing you can say location and that would be represented by you okay second in this case you are supposed to calculate V also when collision comes what is value of V and then also we'll calculate the number of drops because sometimes you are asked how many number tell me or tell the tell me the number of probes total number of drops your while you are inserting this these keys into this hash table may be this question can be asked and the second question is maybe you can ask you'll be asked that what does the what is the order of these elements after inserting these elements in the hash table okay I will calculate these three things now for three what is the location simply when you know there is no collision then he'll simply inserting these elements into this hash table we will apply this h2k only in that case when collision comes so for three find out this location you how you will calculate apply this hash function h 1k h2k will be applied only in case of collision now what does this two into what is value of K here three plus three fine this one and you're supposed to you know use this division method then we'll this one is more below more below M M is what ten fine okay you know what does this value I think this would be 9 3 into 6 is 3 into 2 is 6 plus 3 9 9 more tennis 9:00 then go to the ninth place yes this is free we can insert three at this place okay now calculate four key to 2 into 2 plus 3 mod 10 this would be 7 go to the seventh place yes this is free we can insert to add this place and 4 3 & 2 we are not supposed to calculate the value of V because no collision comes but we will calculate this prob probably so what synonym simply in English Megara bowler than prob cos and anima what that searching where you can say you know some coach corn or something like that so you are inserting this tree ok and now if you have to search this 9 where is this 9 and you can simply insert this 3 at this place the number of probe is only 1 for 2 also number of probe is 1 because you only search the location 3 and this one is free you have inserted this 2 and this place now for next is 9 what is value of this 2 into 9 plus 3 mod then what should be the value we are calculating for this 9 I guess 21 this one is 21 21 more 10 is one go to this place one yes this one is 3 we can insert 9 at this place a number of probe would be 1 and will not calculate value of wafer 9 now 4 6 2 into 6 plus 3 we are applying this hash function okay and mode mod M M value is and what should be this value this 1 B is 5 6 into 2 is 12 12 plus 3 is 15 more 10 that is 5 go to fifth place yes this one is 3 we can insert 6 at this place no need to calculate V number of probe is only 1 now for 11 here collision comes 2 into 11 Plus 3 mod 10 and it should be I think 11 22 22 plus 3 is 25 25 more tennis pie and this one is five full so go to the fifth place is it free no we cannot insert eleven at this place because here we have already six is there now you have to resolve this collision and what is there you have to use double hashing technique okay okay now calculate now what would be applied in double hashing technique insert ki ki here is 11 you have to insert 11 at first free place from u plus V into I mod M now for 11 what is value of U we already know this one is U that is 5 plus what I would be from 0 to M minus 1 now calculate value of V you have to calculate value of V for 11 have to calculate value of V we would be calculated like this h2k more M okay and what is H 2 K here H 2 K is given 3 k plus 1 calculate value of V 4 11 what would be the value C h2 k h2 k is what 3 k plus 1 3 into what is value of k case the key for which you are searching the location however you can say that which collision comes status for which collision comes in there k is 11 plus 1 this one is h2 k and more m more M value is same that is n now tell me what is the value 11 into 3 is 33 34 34 mod 10 is what that is for fine now value of V is for now calculate C we can you can't say K insert this at this place for because this one is free no this one is value of V you have to put when you if we had this place and then you can calculate the free place or free location you can say now calculate you is what 4:11 you is what five plus V is what four into I am a new I value is suppose starting my K value is what zero and mode M that is ten five plus this one this would be zero five more ten is five go to first place but this is not free okay koib at me I'm a occurring I value will go from 0 to M minus one then I value would now become one now calculate five same value of who is five plus value of V is for Gentoo value of I would go from 0 to 1 and then mode and calculate for that is this one is five plus four that is nine nine mode and that is nine no this one is not free we cannot insert at this place okay okay go back me next what is value of I now five plus 4 into zero one now value of I would be two and value of U and we will remain same mod 10 what is this value 4 into 2 is 8 and 8 plus 5 is 13 13 mod 10 is what I guess 3 now go to third place yes this so location is free we can insert 11 at this place okay now tell me number of probes for this 11 first probe is what firstly we go to this when I evaluate it firstly how many khaki ahem fifth place bagel but that was not free for first foot prob then we went to ninth place second probe then finally we went to third here this one is free so total number of probes are three okay now let us take that another he next one next one is what 13 for 13 simply calculate value of you value of you would be calculated using this hash function that H 1 K 2 into 13 plus 3 and more and what should be this value 13 into 2 is 26 26 plus 3 is I guess 29 29 more 10 is what 9 this one is 9 go to the ninth place oh no this one is not free equally then comes now you have to apply double hashing technique ok well calculate value of V first of all what is value of V 430 value of who we would be calculated using this formula H 2 K mod M now what is H 2 K 3 K plus 1 value of V would be 3 into what is value of K here 13 plus 1 H 2 K this one mode mm is n now what is this value 13 into 3 is 39 39 plus 1 is what that is 40 40 mod 10 is what 0 okay okay then V value is 0 okay we have calculated the V value now put this V value and the splits okay what is value of U for 13 that is 9 9 plus V value is what 0 and sorry 0 into its starting I value of I is what also 0 and mod 10 what does this value that is nine only fine now if you calculate another next free location but 9 is not Drina then value of I would be zero to 1 but value who he is zero 'no so here if you will put 2 0 1 2 3 4 or m minus 1 that is 9 then it would remain zero and always the value would be 9 plus 0 more 10 that is 9 always you will get what 9 but 9 is not free so we cannot insert this 13 in this hash table ok that is the one another important point see although you have free spaces and hash table but it is not necessary that all your keys would be inserted at this place at sometimes may be you will not able to find out the free location but still there are free location like in this case always you will get what 9 it depends on these hash functions okay may be high feel change the hash function H 2k something else then value of we would not be 0 and then you can calculate the you can all easily find out the free location ok so it would be very necessary to you know choose the good hash function in the next video I will tell you the properties of a good hash function so this one is another case we cannot insert 1313 in this hash table okay okay and that is that is fine it is not the case that if 13 is not being inserted then it is wrong no no no no that is all that is fine it is not necessary that you you can insert all the keys in this hash table okay that is fine now next value of 13 kaha we cannot insert so leave it now next is 7 calculate the value of u 2 in to apply this hash function 2 into 7 plus 3 mod 10 and the value would be what I guess this 7 7 7 into 4 is 14 14 plus 3 is 17 17 more 10 is what 7 go to the seventh place oh no this one is not free collision comes at 7th also you have to calculate value of vie for this one what is value of e this one using this method division method h2 k h2 K is 3 K plus 1 3 into K is what 7 because we're calculating for this 7o k plus 1 and mode they're calculating value of V and mode and that is 10 this would be I guess to 21 plus on 22 22 more pennies to you have calculated value of V 2 but that is not the end you're supposed to calculate the free location this is really only okay put this value of V at this formula you you is what the 7 we have calculated for 7 use what 7 7 + V is what 2 into 0 starting my I value is what 0 mod n that is 7 7 is already full okay next is 7 plus 2 into increase I value by 1 that is 1 mod 10 that would be 7 plus 2 is 9 go to the 9th place for that is not free again next 7 plus V value is 2 into increase this value of I that is 2 mod 10 I guess this one is 4 4 plus 7 is 11 11 mode 10 is what one will go to this one place over this one isn't also not free next is what 2 plus 7 plus 2 into now I value would become what 3 mod 10 and what is this value I guess this one is 6 6 plus 7 e 7 is 13 13 mode or 10 is what 3 you go to the third place this is also not free now find out the next one next one would be here I'll calculate 7 plus 2 into now I value would become 4 mod 10 this one is 8 8 plus 7 is 15 15 plus 15 mod 10 is what 5 go to the fifth place this one is also note free now next 7 plus 2 into now I value would be 5 from 4 to 5 and more 10 now this one is 10 plus 7 17 17 more 10 is 7 7 is also not free okay next next would be what increase the value of I from fifth to 6 7 plus 2 into 6 mod 10 and what is this value 12 12 plus 7 is what 19:19 mod 10 is what 9 go to this 9th place this one is also not free way back to me this was 3 increase this value by 1 on 7 plus 2 into 6 2 now 7 more n now this value is what 14 14 plus 7 is 21 21 more 10 is what 1 go to this place this one is also not free now next is what 7 plus 2 into 8 mod 10 what is this value this one is 16 and 16 plus 7 is what I guess 23 23 mode 10 is what 3 go to third place this one is also not free now increase value from 8 to 9 that is 7 plus 2 into 9 mod 10 this would be 18 18 plus 7 is what I guess 25 25 mod 10 is what 5 go to the first place this is also not free now increase value of I by 1/9 saying value of 1 is what 10 but that is not possible because I bring from 0 to M minus 1 so here in this case from 0 to M minus 1 M is what 1002 9 only and we have already checked for all the possible value of i from 0 to 9 but we are not able to insert we are not able to find out the proper place to insert this 7 okay so that is the only that is also a case okay maybe you are not able to find out the free location no problem okay so we cannot insert this 7 also 13 cannot be inserted 7 is also we are not able to insert this 7 also because we have checked all the possible options from ranging i from 0 to 9 no problem fort well now what is value of this 1 2 into 12 plus 3 mod and what is this value this one is I guess 7 12 into 2 is 24 24 27 27 more 10 is what 7 go to the seventh place but we are not able to insert because this one is already filled so here collision comes now you have to calculate value of V for this to L what is value of V h2k mode MH 2 case this one value of e would be 3 into what is value of K 12 plus 1 and more 10 what is this value I guess this would be 7 22 3 is 36 37 37 mode this one is 7 value of V now put value if we add this please range i from 0 to 9 value of U is what 7 7 plus 7 into it starting in the beginning value Phi is 0 mod 10 this would be 7 go to seventh place we cannot insert increase value of Phi by 1 7 plus 7 into 1 mod n what is this value 7 plus this 1 cell 14 14 mod 10 is what for go to this place yeah this one is free Oh Staniel epic here we can insert this to n okay number of probes for this to L is what I guess one end to and what is value of V for this one is seven okay and number of probes first was seven that is not free next was four but this was free the number of probes are two thirteen and a two 7ko sorry we didn't calculate number of probes have calculate Carlina but we are not able to insert thirteen and four at this place okay so no need to calculate versus the number of probes for these because of in case you are not able to insert any keys then obviously we cannot tell how many number of probes are there for 13 and 7 okay now if you are asked the you know order of elements after inserting these elements you do the hash table then how we will write the order the order would be see first places free so first there would be free space and then you would write this 9 you will not written like this simply 9 11 then 12 and 6 2 & 3 no this is wrong how you write first is free then 9 then also free then 11 then 12 then 6 then 3 then 2 then three and then three this is the order of elements in the hash table after applying the double hashing technique so this is the all about double hashing technique okay two hash function would be there one is this one you will simply apply this hash function in case collision comes then you will use the double hashing method okay so I'll see in the next video till then bye bye take care

Channel: Jenny's lectures CS/IT NET&JRF

Views: 126,224

Rating: 4.9214683 out of 5

Keywords: coding, algorithms, function, data structure, binary search, hashing, collision resolution, heap sort, double hashing, ugc net computer science study material, GATE computer science preparation, coaching classes, engineering, hashing in data structure, youtube, youtube channel, hashing techniques, jennys lectures, jayanti khatri lamba, hash map, technical, c programming, code, NTA ugc net 2019 syllabus, ugc net, csir net, ugc net online, net syllabus, ugc net syllabus

Id: AYcsTOeFVas

Length: 26min 51sec (1611 seconds)

Published: Tue Feb 19 2019