In this video we will discuss the quadratic probing method and how this method is used to resolve the collision in hashing. Now I have already discussed what is the chaining method and what is linear probing method. I'll give you the link of those videos in the description box. You can check out those videos because I'm going to take the same example as we have taken in the chaining method also and linear probing method.
Okay. So this is the example. Here we have these are the keys. supposed to use you are supposed to store these keys in the hash table and the size of hash table is 10 and the hash function which is given is 2k plus 3 and the question is you are supposed you are asked to use division method to store these elements plus to resolve the collision you have to use quadratic probing method okay to store the values now what is there in quadratic probing method see this is what we have to do insert ki Ki is the these keys I means 0 to this m minus 1 1 2 3 4 5 6 like that insert Ki at the first free location from u plus I square mod M and where I will range from 0 to m minus 1 you have to remember this 0 to m minus 1 not 1 to m 0 to m minus 1 okay in linear probing what was there it was u plus I mod M in linear probing we move linearly like this one step one step forward one step forward like that okay so the problem in linear probing was that clustering problem okay i'll discuss that problem in the last but in quadratic probing we will move forward using some quadratic polynomial until we find a free slot like suppose if we are here and this one is not free slot then maybe we will go we'll jump to here only then we'll go go jump to here only then maybe we can jump to here only by skipping two or three space okay but linear make up one by one you check the next place then next to the next and then next okay now check out first key is three find out the location location see the hair you is whatever the location will find out or you can say the hash value will find out after applying the hash function 2k 3 and division method you have to use then 2 k value is 3 2 into 3 plus 3 mod 10 fine and what is the value here we have 9, 9 more 10 that is 9. Okay. Now at the index number 9th you are supposed to store this 3. Check out this 9. This one is free you can store 3 at this place.
No problem. Now for key 2nd. you have yes you'll store see you can use you can find out this location using this method also okay for three check out now in case of collision we will use this one because here we don't have any collision so just proceed for two two into three plus three more than what is the value sorry it's 2 for 2 now here ok now next key is 2 find out this one 2k plus 3 2 into key value is 2 plus 3 Mode 10 and what is the value?
7. Because 7 mode 10 is 7. Go to the 7th place and this one is free. You can store 2 at this place only. Next is 9. For 9, 2 into 9 plus 3. mode 10 and the value would be 1. Okay. 18, 18 plus 3 is 21, 21 mode 10 is 1. Go to the 1 place.
This one is also free. You can store this 9. Now for 6, 2 into 6 plus 3, more 10, 12, 15, that is 5. 6 at 5th place, go to 5th place, yes this one is free, you can store 6 at this place. Now the problem comes. Find out the location for 11. How to find out this location? Using this formula see 2k plus 3. Now k value is 11. Put this value 2 into 11 plus 3 mod 10. And this is also 5. Because 11 into 22, 22 plus 3 is 25, 25 mod 10 is 5. Mod always give the remainder value that is 5. Now go to this place 5. but we cannot store 11 here because this is already filled now here collision comes fine if collision comes then use this formula in case of quadratic probing now what this formula says insert this ki ki is now 11 insert 11 at the first free location from this one now calculate for 11 we are calculating what should be the value u plus i square what is value of u for 11 u is this location you have calculated using this hash function now u is 5 5 plus i square i square first i would be 0 0 square is 0 mode 10 that would be 5 and fifth is already there so we cannot store here Find out the next place.
Now I will move from 0 to 1. 5 same U value is 5. In place of I will store what? 1 and 1 square is 1 only. That is mod 10 and what is the value that is?
6. Now find out 6. Yeah this one is free. So we can store 11 at this place. Number of probes.
Sometimes in question they will ask you what are the total number of probes or sometimes they ask average probes to solve this question. Fine. So, we write probes together. For 3, number of probe is probes means searching.
In simply English or if you say synonym, that is searching or you can say khoj karna, kuch dhoondna. Fine. For 3, 9. Go to the 9th place. We searched 9, where it is free or not. So one prob would be there.
For two also go to the seventh place. Yeah, this one is free. Finally stored.
So we searched for one prob only. We searched for one for nine. We searched for one for nine. We searched for one for sixth.
For eleven, how many probes would be there? Firstly, you would go to the fifth place. Fifth one.
But this one is not free. Okay, see. Your fifth came here too.
But this is not free. Next, where did we go? Sixth place.
Yeah, this one is. free so two probes are there one is for this fifth one one is for sixth one two probes are there okay now find out for this 13 2 into 13 plus 3 more 10 now this one would be i guess 9 13 into 2 is 26 26 plus 3 is 27 29 29 more 10 is 9 now go to the ninth place bus but 3 is also there so collision is there now use this formula to find out the proper place okay now this one is 9 1 probe up Cahoot sugar check out for 13 same method u plus I square mode M starting my I value is 0 and U value is 9 plus square of 0 mod 10 that would be 9 but 9 we cannot store. Increase value of i, i would be now 1. So u value is 9, u is our location, 9 we put here plus i value is 1, 1 square is 1 only mod 10 and that would be 9 plus 1, 10 mod 10 is 0. So 0th place is free, yes this one is free so we can store. store 13 at this place okay number of probes total number of probes for 13 days one is you have searched this nine but this was not free then again you searched this index or this location zero but this was free we stored it so two probes are there two times you searched for this fine now next is seven find out the value of u for seven two into seven plus three mod ten what is the value I think it's 7. 7. 14. 14 plus 3. 17. 17. Mode 10 is 7. Go to the 7th place. But this is not free.
Collision is there. Again use the same formula. For 7 calculate. U plus I square.
What will be your I value in starting? 0. Now what is value of U for 7? That is 7. 7 plus 0 square. Mode 10. What is value? 7. But 7. we can't store it on 7. Now next is 7 plus i value would be increased by 1. 7 plus 1 square is 1. More 10. That would be 7 plus.
7 plus 1 is 8. 8 more 10 is 8. Go to the 8th place. Yeah, this one is free. We can store 7 at this place.
Okay. Again for 7, 2 probes. Now, main difference would be in 12. Fine.
In case of linear probing, you can see in the video. And in case of poetic probing, we will see. Now, what is for this? what is the value of u for this?
calculate 2 into 12 plus 3 more 10 what is this value? this would be 7 again fine go to the seventh place but this is not free okay in linear probing we did next place search next then next then next and finally we got this free fine but now check out in case of quadratic problem sorry use this formula u plus i square mod m for 12 we are calculating we are finding the free slot to store this what is value of u 7 7 plus i value starting zero zero square is zero mode 10 that would be seven but seventh we cannot store now next is seven plus one square 7 plus i square i well palatine 0 then i would be 1. 1 square is 1. 7 plus 1 more 10 that is 8 but we cannot store at this place. Now i would be 2. Palatine 0 then 1 now i would be 2. What is value of u?
7. 7 plus 2. Here we have i square. 2 square. 2 square is what?
4 more. 10 7 plus 4 is 11 11 more 10 is 1 so directly search to this one but this is not free okay linear me humne kya kya tha 8th pe search kya then 9th ko search kya then 10 hum 0 pe gaye then hum 1 pe gaye the but quadratic me kya hua we have used some quadratic polynomial fine hum directly humne linear nahi kya hum directly 1 pe gaye but this is also not free so find out next place 7 plus now i value is what 3. here i value was 0 1 2 now 3. 3 square what is 3 square 9 mod 10 now what is this value 9 plus 7 is what 16 16 mod 10 is what 6 go to this place 6th 1 but this is not free we cannot store 12 here now next 7 plus now i value is what 4 fine 4 square is what 16 16 mode 10. now 16 plus the 7 is 23 fine 23 mode 10 is what 3 now go to this index 3 Yeah, this one is free. We can store 12 at this place. Now find out the number of props for 12. One prop is this 7. Starting me hume kya mila tha?
7. 7 was not free. Then 1. Then hum 8 pe gaye. Nai free nahi tha 2. Then 3. Then 4. And then finally 5. How many props are there? 5. But in linear probing, how many probes were required for storing this 12 is?
6. Okay. So, to resolve the collision in case of open addressing, this quadratic probing is better than linear probing. But it resolved the problem of clustering. Why was 6 in this?
Because we went to 7 in linear. Then we will go here, we will go here. Linearly we will move.
Fine. and linearly if data is filled and not slot free then in that case we have to probe again and again and time required would be more so total probing i guess this would be 15 now in this question if you are asked what are the order of elements after inserting these elements into the hash table sometimes in net exam they ask you what are the order of elements so order of elements would be what this This would be the order from 0th you will write 13 then next is 9 next you will not write this 12 next place is free then you will leave it like this dash free then 12 then dash this one is also free then 6 then 11 then 2 then 7 and then 3 but in linear probing this order of element was different you can check out in that video okay so this is all about quadratic probing in next video i'll discuss with you what is double hashing technique till then bye bye take care