8.1 Hashing techniques to resolve collision| Separate chaining and Linear Probing | Data structure

welcome back today's topic is type of types of hashing okay so let me tell you something about hashing hashing is basically what it is a searching technique okay and in searching of some data if you use it this hashing technique then the time taken is that is a constant time but you can say order of one time taken is order of one see for storing some data obviously some data structure would be used may be array may be linked list may be tree okay and the main thing is in data processing is the main or the common paradigm is to store the data and after that to retrieve that data okay a post or we can now rock or a tree with a knife or some processing okay so for searching some date our for retrieving the data two types of searching technique I guess a possible path other one is linear search and one is binary search in linear search time taken is in the worst case the time taken is order of and and is that number of keys stored in that array or some data structure and in binary search if you use then order of log n time taken is order of log n so this time depends on the value of n means how many keys or how many you know a number of data you are supposed to you have inserted and you're supposed to retrieve from that data structure okay but we want some technique where the searching is you know searching takes takes constant time it does not depend on this number of keys and that technique is hashing technique okay the main concept is in this hashing technique we use some hash table and hash function using some hash function for storing some data we will calculate some hash value or you can say that address and that address we can store that key okay or that data in that hash table okay fine now suppose some policing occurs collision means if you see let us take an example we have six and twenty six these two keys we have and have their table of sorry the size of hash table is 10 we can store 10 values in that hash table and the hash function you are given is this you are supposed to use that division method three methods are there to calculate the hash function hash function that is division method one is folding method and one is mid square method and also another one is that modulo multiplication method also there okay so you are asked to use that division method division method McKevitt aapke hash function will be like this key whatever the key mode mm is size of hash table okay whether it is eight whether it is ten or eleven or fifteen whatever it is here in this example i am taking the size of hash table is ten now if you calculate the address to store this key value six using the hash function okay then what should be the value C K value is now six then six mod M value is in this example am value I am taking and it is just an example then the value would be six you can store the six where at six location or you can say the index should be six like this here we will have one hash table and from zero to nine because the size of hash table is what n so at some point we will have this index X and we can store this X at this place but suppose we have 26 another case 26 and the using the same method you are supposed to calculate the hash function or you can say the address for this 26 now this address for 26 would be 26 mode mm value is 10 and this is also 6 okay but at sixth place we cannot store this 26 because already 6 is there so this is known as policing when you know when you calculate some hash function or the location or you can say address for 2 keys and using that same hash from that hash function will give you the same result same index but we cannot store two values at this place like 6 and 26 this is the collision so to resolve these collision we have some techniques today I am going to discuss with you those techniques see and you can see types of hashing one is open hashing and one is closed hashing open hashing is also known as closed addressing and this closed hashing is also known as open addressing okay so in this method in first one this open hashing the method to resolve these type of collision okay is what that is chaining method but you can see separate chaining okay in this case the method would be to resolve the collision that is chaining method fine and in closed hashing three methods are there to resolve the collision see you cannot remove the collision you can only minimize the collision okay so three techniques are one is linear probing one is quadratic probing and the third one is double hashing technique right I'll discuss all these techniques with the help of example so in this video I am going to discuss with you this chaining method how to use this chaining method to resolve the collision okay through let us take one example now let us take one question suppose you are given these key values this one is suppose any and these key values are there three two nine six eleven thirteen seven twelve and you are supposed to store these key values and put into the hash table the size of hash table is given is N and the hash function vs. which is given is h case 2 k plus 3 in this question and you are asked to use division method and closed addressing technique to store these values now before you know solving these this question you must have the idea what is this division method and what is closed addressing do is in method we have already discussed how this method is to be used how the hash function hash values would be calculated the key and mod of a mode of size of hash table and what is closed addressing this is also known as open hashing and in this case what method is used to resolve the collision that is chaining method okay okay now let us we have one hash table this hash table and this hash table is of size 10 zero two one two three four five six seven eight nine okay this is up to zero to nine okay this is our hash table of size and hash function is 2k plus three and you are supposed to use this division method now calculate the location proper position or you can say the address for these key values here we'll write down the location first key value is three find out the proper place to store this three in this hash table and how you will calculate that using hash function and hash function is given plus a which method you will use the division method or folding mat method or mid square method you are asked to use division method okay now calculate H for a method obviously you know ko5 mode M this is the method okay but here function has from a hash function is given to k plus 3 so we cannot directly calculate that three more 10 and the value is 3 no we cannot directly put if this is not given to you then you can directly use this one okay if you are asked to use division method but here you are given this HK value 2 k plus 3 then how will calculate this value this would be like this 2 into the what is value of K here we have 3 okay plus 3 and then mod 10 fine now here that a K is this one because hash function is given to k plus 3 now what is the value 6 plus 3 is 9 9 mod 10 years 9 only because the result would be the remainder only so the location is 9 at 9th index you can store this 3 okay now find out the position for value to 2 into 2 plus 3 and now mod 10 4 plus 3 7 & 7 more 10 is 7 only the where you can store this too at 7th place here we can store this too now find out this 1 4 9 have you'll find out the same method 2 into 9 plus 3 and then mode then what is the value 9 18 18 plus 3 is 21 21 more 10 is 1 here at one position at one index you can store this 9 now for 6 say method 2 into 6 plus 3 more 10 what is the value 12 plus 3 is 15 15 more 10 is 5 at fifth place you can store this value given you six now for 11 2 into 11 plus 3 mod 10 see for this one is 11 to 22 22 plus 3 is 25 25 mod 10 is 5 now check what is the position for to store this 11 is 5 go to 5 but here we have already the 6 this is the case of keynesian now in question you are given use closed addressing technique and enclosed addressing what is the technique you will use chaining method separate chaining method in chaining method what is there go to the fifth place already 6 is there then a linked list will be used like this fine and here 11 would be stored a chain would be created like this okay this is you can say linked list would be used to store the values in case of collision okay now for 13 what is the value two into 13 plus 3 mod n 13 into 2 is 26 26 plus 3 is 27 28 29 29 mode 10 is 9 now here also we have one collision go to the ninth place but we have already three at the space you cannot store 13 what method you use chaining method and chaining method making of the separate linked list would be used and here we will store what 30 now next is 7 2 into 7 plus 3 mode and what is the value 1414 plus 3 is 17 17 mode 10 is 7 he rolls will happily then go to the seventh place but here we have already what is stored that is 2 we cannot store the 7 what is the method chaining method the chaining method making our separate link list will be created and the 7 would be stored at this place this is linked list link lachemann basically 1 node is having two part one is that information part and one is that address part that this link will or this pointer will contain the address of next node ok you can denote like this only now next is 12 2 into 12 plus 3 mod 10 and what does this value 12 into 2 is 24 24 plus 3 is 27 27 mod 10 is again 7 now go to seventh place find out this is not free you cannot store here go to the linked list part here also you cannot store we have 1 linked list now again 1 linked list or one node would be created fine and 12 would be stored at this place and this this you know this one this link or this pointer will contain the address of this node and this pointer would contain now this is also not this is not also not fine so this is the chaining method how the staining method can be used to resolve the collision the next video I'm going to discuss with you what does that how the linear probing method will be used to resolve the or to minimize the collision okay now let's kiss the linear probing method with the help of same question the same question is there these are the keys same hash function is there to k plus 3 same you have to use division method only the changes you're supposed to use open addressing fine to store these elements okay and size of hash table is 10 now whenever you are asked to use open addressing then by default you will use linear probing to resolve the or to minimize the collision okay then that is the tool if you are because this the open addressing few techniques are there linear probing quadratic probing and double hashing but by default you will use linear probing in case of say Putrajaya use quadratic probing in that case when you lose that one in case you're asked to use double hashing then you will use double hashing but by default you will use what linear probing okay now check the only changes the hair is we have open addressing same question is there okay for this three you have calculated the value that is nine okay I'm just going to write these values at ninth place we will use will store this three now what is the place for this key second this key value two here is seventh here you can store this to nine co-op can store Ikaruga here at one occasion here you can store nine six Co you can store at index fifth or fifth location here you can store six now problem comes in the case of eleven same hash hash value is being generated using this hash function okay that is five when you go to five but it is already there six is already there so collision is there now use linear probing what is C probing means what in simple English term probing means you know a synonymous searching or a coach karna so it will search the free place now where you can it can store the value okay now at fifth place we cannot store because already six is their Pelini linear probing linearly hamaji building it at the next place this is a simple technique okay next place check out this is free yes this is free throw you can store 11 at this place fine and sometime in question you are asked if we at last to store these elements using open addressing total props of kupatana how many total probes was there okay so such SATA maybe discuss contain four key to store this key three how many props are there obviously one probe is there now ix big they have omni search here ninth who searched or Nikki Anaya bar then one probe is there for two also one probe for nine also one province for six also one prom but to store this 11 how many probes you required one probe is encase them up to five Milla search five but this is already filled one probe is already there now again search the next location this is free yes this is free fine so two probes are there one is for this fifth one original one and next is for the next one so here two props for 13 go to 9th but this is already filled then what you will do find out linearly the next place and next place would be this one zero okay because we have already say the size of this hash table is 0 to 9 then go backward and this one is 0 now where you can store this 13 here we can store this 13 next is how many prompts for 32 probes 1 9 p ji apne search here 9 who then happening next place search here 13 then two proms are there for storing the seven go to the seventh place but this is already filled then the next place yes this is free we can store seven at this place and total number of probes are due for storing this 12 go to the seventh place this one is already filled we cannot store go to the next place this is already filled we cannot store go to the next place this is already filled we cannot cannot store the next place is this 1 0 0 this location but this was already filled the next go to the next place that isn't one that index 1 that is already filled we cannot store go to the next yes say linearly we are we are searching the free place linearly one by one we are not jumping like this I got a free Nieto will jump towards three locations no linearly up Azam canal that is why it is known as linear probing here we can store this to L okay now how many props for this - L 1 is we go to 7 7 company search here one probe one is for this one - one is for this 3 4 5 and finally 6 6 problems now total Pro for this - LS 6 pro now total Pro bhai hope calculate cursor go in case if you are asked to total prop give me way sometimes in net exam they are also asked he just find out just tell the order of the elements in the hash table after inserting all the elements what is the order of elements you are supposed to give the for multiple you know that choices the order of element is this this this or this this this now in this case what is the order of element in the hash table if you are asked then the order of element would be you has applicant start over from 0 zero - please 13 then 9 then 12 then you will not write the sex directly one in two places are free one and two these are blank then six then 11 then two then seven and then three this is the order of element okay so in linear this was a shortcut yup just look out the hash table and finally next by next by search for Karenia if you write the proper you know definition of that linear probing then what is that that one is this is what happens in linear problem throbbing properly if you'll write insert ki like k1 k2 k3 these are keys at the first free location from you plus I both mode M where I will range from 0 to M minus 1 now here is a path I bogan 0 to M minus 1 M question media Haga that is 10 then that I would be 0 to 9 what is this you you is what this address so you can say this location whatever whatever you have calculated this 9 7 1 using this hash function that would be the you now check out see if directly a poisoning knife you use this method or this definition and then check out for 11 will check out okay 11 Kelly in case of collision you will use this one insert kind of a pokey I acquired the very at the first free location from this one fine for 11 what is the value of U u plus I more 10 what is value of U for 11 what is value of u whatever what you have calculated that is 5 then 5 plus I I will range from 0 to M minus 1 of starting my Q value is 0 0 fine more mm value is ten and this would be five more ten that is five but this is not free place okay now increase value of Phi I is now 1 then 5 plus 1 mod n 6 more and that is 6 find out sixth place how many insert copy our key copy ksi 6 3 because sixth was free so here we have inserted this 11 so this is the same definition insert key I add the first free location from this one first free location yeha say the very first free location was this one sixth okay in case of this 12 check out sea fort well what is when you of you the value of you is 7 calculate 7 plus in starting value of I is 0 mod n 7 would 10 is 7 7 this one is not free ok now 7 plus 1 mod 10 8 plus 8 more tennis 8 more pen that is 8 this one is also not free because 7 is already there now 7 plus increase IQ value 0 to M minus 1 that is 0 to 9 7 plus 2 mode and that is nine nine more 10 is 9 this is also not free 7 then now I Q value is 3 7 plus 3 mode 10 that is 10 more 10 10 more 10 is 0 remainder would be 0 go to the zeroth place but this one is also not free because 13 is also there again check out the next location 7 plus 4 more 10 11 more 10 that is 1 but 1 is also note free now 7 plus 5 more 10 that is 12 mode n is 2 now go to the index - this one was free okay and here we have we can insert this 12 okay so using this formula formula also you can calculate these indexes or well you are same linear probing me up cohosh deviled egg nyan simply just look over the next place is free and free then insert it other nail top next Nick Nick Nick said y'all grab circle together so this is the basic idea of linear probing and next video I'll discuss how to use quadratic probing to find out that or you can see the to dissolve the collision till then bye bye take care

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

Views: 354,100

Rating: 4.8870554 out of 5

Keywords: Hashing methods, types of hashing, hashing techniques, hashing in data structure, linear probing method, collision resolving techniques, chaining technique in hashing, how to resolve collision in hashing, data structures, algorithms, hash table, hash function, hash value, quadratic probing, double hashing, jenny lamba, jayanti khatri, jenny's lectures, dsa, chaining method, ugc net, gate, computer science, syllabus, engineering, data structures and algorithms, ds, ds notes

Id: zeMa9sg-VJM

Length: 25min 51sec (1551 seconds)

Published: Thu Feb 14 2019