Hi, everyone.
So in this video, we will talk about rehashing so as discussed in the last video, we will calculate
our load factor and when the Lord will become greater than zero point seven, what we will do, we will
do reaction now when we calculate our load factor.
So we will calculate load factor inside the insert function.
So we have written the code search insert function that will insert the key and the value.
So after inserting the key and the value at last, what we will do, we will calculate our load factor.
And if the load factor came out bigger than zero point seven, then what we will do, we will do rehashing.
Now, how we will do reaction, so initially our budget that we have created our budget area of size
five to this is our budgetary size five now 40, but we have to do we have to create an array of double
size.
So I will create an area of size 10 because initially our area was a size five.
So now our area is also Austin.
So after creating the area, what we will do, we will put everywhere because it is containing the garbage
address.
So I will put everywhere.
Now, what I will do, I will take a temporary variable so this temp will point towards this area and
my budget will now point towards this new budget, very simple.
Now, after doing this, what we have to do, we will traverse on temporary, we will traverse on temporary.
And at each index, I have a linked list.
So I will also traverse on the long list.
So I am traversing on that temporary area and at each index linked list.
So I will also travel on the list and I will rehash every key value before I will insert every key value
inside this new bucket.
Simple.
Now one obvious question that might come to your mind.
So if this is next to let's say this is index three.
So these three nodes, let's say these are the next three.
So in the new area, so this is a new area of station.
So is all the key nodes will represented in this tree in the new area or not?
I'm repeating my question.
So one obvious doubt that might come into your mind is at the next three.
So this is extreme.
So suppose this is the next three and next to suppose there are three nodes.
Now, when you will rehash, basically when you will insert these Nold, these guadaloupe inside this
new area of southeastern, so will all these three nodes will come in next to you or not?
So my answer is no, it won't, because let's say let's consider two things here.
So this is ABC, Gey, ABC, and this is the ETF.
So let us discuss about this temporary now this GBC, let us try to find out, it's called a high school
is basically independent of budget size.
So high school they came out to be it.
Now, let us also calculate the score for the ETF and let's say its high school came out with 13.
And then what we have to do for finding out the index, we will we will take percentage, five percent.
This Birgitta's to the index came out to be three.
And similarly, the index came out to be three.
So that's why ABC and the if they are present at the next three.
Simple.
Now if you will push ABC and the ETF at the next three here.
So suppose you push ABC.
And the F at the next three, you just blindly copied all the linked list.
At an extreme, you just blindly copied this only linked list at the next tree in the new area.
Now, when the new area I want to search, so for example, I want to search the guilty.
If so, what will happen?
So for searching the key, first of all, I will try to find out.
Attash also called came out with Hardeen because his code is independent of the pocket size.
Then what I will do, I will write more down to Morton came out to be three, so I will go to the next
tree and then I will search this linked list.
Yes, the is present, so I will retain its value.
So little value was do so I will return the value to simple.
Now let us take the case for ABC.
So you have ABC.
Now, again, we will calculate the harsh cold, so harsh cold came out to be it, because it is independent
of the.
Because then I will do more then, so it came out to eat, so what I will do, I will go to index it.
So suppose this is index eight, I will go to index it.
And this will also have a link list.
And now what I will do, I will traverse over this link list.
And ABC is not present there.
So what I will do, I will return that.
ABC is not present and I will return a garbage value zero.
Obviously this is wrong because ABC is presented the next three, so that means you cannot blindly copy.
So that means you cannot blindly copy the linked list which was presented the next three.
To the new area at the next.
So what we have to do, this is my temporary I will agree to my temporary.
And at each index, at each market index, what I will do so I will call insert function on this note,
I will call insert function on this note and these notes will be inserted in.
This budgetary, you just cannot blindly copy the whole list and based it here, you cannot do that
because this problem will appear.
Because of the different sizes, different sizes, so the approach is very simple for rehashing, we
will traverse over the time period and for each index we will traverse the link list and for each node
I will call the insert function and insert will insert the key value pair and this new bucket, very
simple.
I'll get the letters, write the call so that you can understand it better.
So where is insert function?
So this is my insert function now after doing countless plays, what we will do will calculate our load
factor.
So the billboard factor.
So what is load, factor and baby and is the total number of entries, so total number of entries is
actually gone?
So I will do count divided by number.
It's.
So is this right or wrong?
So this is actually wrong, right?
This is wrong because it is integer integer division.
So Integer Integer is actually in BGN.
So if you will divide so let's say the count is four and number it is five.
So ideally you should get zero point eight.
But this is in integer division, so you will get zero.
So I want zero point eight.
So what I will do, I will write like this one point zero, multiply, count and then hold divided by
number it's.
So 1.0 then multiplied count.
So now it is float by.
Integer, so the output will be a double value of float value and then you can check.
So if.
The load factor is greater than zero point seven, then they have to do you have to do rehashing.
So the code of creation is going to be very, very large.
So what I will do, I will create a separate function and let us call it function research.
So if the load factor is good, then zero point seven I will call a function rehash.
Now let's write the code for the hash so it is obvious that the hash function will be a private function.
So the return type will be void.
It will not return anything.
The name of the function is Rieche.
So what does Rieche function will do?
So I told you we will create a temp.
So this is my map Naude.
This stamp will point towards the bucket.
And now what we have to do so this budget, it will point towards the new every.
Of double size.
Societies will be double two times of no decades.
Through times of no goods, then what do you have to do?
So initially this containing the garbage address, so we have to initialize it with null so you can
see what they have to do.
So initially our bucket was of size.
So this was an initial area five.
Now this is my new budgetary.
So initially, Buckett was pointing towards this, but what we did, we created a temporary tempest
pointing towards this Alduin and Buckett is pointing towards this new one initially discontinued garbagey
address.
So garbagey, this is dangerous.
So we will initialize it with null.
So I am initializing it with also the sizes two times of no good.
Now, after Initializing Bednall, but we have to do.
We have to initialize all of their properties.
So what do I mean by all of the properties?
So for this new Beckert sofa, this new Buckethead, the counter zero, because it is not containing
any element.
And similarly, I have to upgrade the size.
So I have a very old no kids, but I have to do so.
No kids multiply equals two.
And since we had a building the size like this store, the original size.
So let's do that.
So what I'm doing right now scared a very well oiled but good size.
So it is all about could say, so this is going to be no kids.
No, it's.
Now, what we have to do, so I will update.
So this will get multiplied by two.
And what is the value of count?
So initially in my bucket said there are zero elements, so this is my new book, etc. So zero elements
are there.
So that's why I have to initialize count again.
Simple now as discussed.
But we have to do we have to do rehashing so far, rehashing what I have to do.
I will iterate over the temporary and for each bucket what I will do, I will add it over the linked
list and I will call insert function simple.
So I have to add it all the time, Betty, so in order to hydrate, so I equals zero, I then.
So what is the size?
So this is the size of the bucket size.
I placeless.
Now, let's try to find out the head.
So what is head head is actually a temp of a.
Simple and then what we have to do, so we have to operate over the list.
So while it is not a questionable.
So I have to iterate over the long list, so we had equals.
Next offered.
Now, what we have to do, so let us try to find out the key and the value.
So what is key so stinky is.
Haruki.
And what is value so we value?
It is.
Hadero value.
Simple, then what do you have to do?
You have to call the insert function, insert function will take and it will take value.
So if you'll see carefully the insert function.
So inside function and started, the key will appear in the gallery, so you can see with the obligatory
so see it is inserting in the buckets.
So what will happen?
These new nodes will get inserted inside the Buckets said.
So.
These new nodes will get inserted inside this Bucklebury, which was containing initially zero elements,
so this count will increase automatically because we have written the logic inside the insert function.
Simple.
Now, what we have done till now.
So basically, you have this temporary.
The size was five and you have decided then you have this area of size and this is buckets.
So the system, Betty.
And this has the linked list, so now what we have done.
We are trading on the time period and then we are trading on the long list and then all the key value-based
are pushed inside this budgetary all the way, little bit inserted inside this bucket area.
Now, we do not need this at animal.
We do not need this idea anymore.
So it will look we will treat all the temporary area again.
First, we will delete the linked list.
Then we will delete the.
So first we will delete all the linked list.
And then we will delete the term very simple, because we do not need it anymore.
So it's time to delete the temporize or for deleting the temporary, we relied it because first we have
to delete the linked list so all of it says.
Let's copy this one.
I placeless.
So for the leading the list, what you can do, we can right delete them.
BofI because Tambov is containing the head and this is a recursive function.
So compiling a list will be destroyed.
And then after deleting the list.
We can delete the temporary.
So now they can dilute the temperature so our rehabs function is done.
Hopefully our rehab function should work fine.
So now let us write the code for testing our map.
So let us create my map.
The keys are sitting and the values, let's say, are integers and led to the name of map is MAP.
Let's name it our map.
So now let us push them into this, so let's push.
So I want to push 10 entries so I list and then I placeless.
Now, let's try to find out the key and the value, so character, see, so character, see what it
will contain.
Let's say it is zero.
Plus a.
And then let us create a GUI so stinky.
Let's say this is ABC.
And then.
Giclas.
Gabler's See the character, see?
I will explain what I am doing, so let me do it first, then what do you want?
So let's see, our value is.
I plus one.
And then let's see, let's call the function, insert our map dot.
Insert it will take and it will take value.
And now let us print the size.
So our map Ghazi's.
OK, so what I'm doing here now, I'm explaining to you.
So first time creating our map that gives our strength and the values that integer, so I am pushing
the data of this type exito, this is the key and value is one second key is ABC one and values two.
So it will go on.
So my last key will be ABC nine and the value is ten.
So what I'm doing.
So this is character zero.
So this is correct, zero then plus I saw zero zero, so it will become character zero, so zero plus
one, so it will become character one.
And then this is Mike EBC.
Then I am appending the character.
See, so that's why ABC zero, ABC one, ABC nine and my values lesson.
So starting from one to ten because the value of AI is from zero to nine.
And then I'm calling the insert function, I'm giving the key and the value, so this will be my key
value pair.
And then I am bringing out the.
So how many elements are there, certain elements are there?
So output should be 10.
So let's turn our program.
So this will be Capital V..
So the size of the map is bent because there are 10 entries.
Now, let us also write a function.
So actually, let us write a function that does the public function get load factor so that we can see
what is the load factor.
So get.
Lord Victor.
So what this function will do?
It will simply witness what is the current load factor, so return one point zero, multiply count.
Divided, no, it's.
And when you're inserting so after inserting it as well to try to find out, let us also try to print.
Load factors, work out our map, not get the load factor so that it says get load factor.
So they're destroying our program and let's see what the output.
So this is the load factor.
Now let's try to analyze.
So initially, our bucket size was five.
So when you're pushing the first element, so the load factor will become one by five, so which is
zero point two.
Then you push the second elements to effectively become a two by five, so this is zero point four.
It is still less than zero point seven.
So nobody saying zero point less than zero point seven.
So no reaction yet, pushing the third element, three by five, which is zero point six.
So zero point six is less than zero point seven.
No reaction.
Now, look at this one fourth character.
So this is four by five.
You are pushing the fourth element.
So four by five is actually zero point eight and zero point.
It is actually greater than zero point seven.
So what will happen?
Rehashing will take place.
So when reaction will take place, my bigotry will become of substance.
So this will become for Biden and what is four by 10, zero point four.
So 10 is the new bucket size and forward is basically the total number of entries.
So that's why zero point four.
OK.
Similarly, it will be five by 10.
Five by ten, six by ten, seven by ten, then look at this, eight by ten, so it by then, so eight
by ten is basically zero point eight and zero point.
It is a good zero point seven.
So what will happen rehashing will again take place.
So two times the recession is taking place, so this is the first time we did recession.
Now we are doing rehashing the second time.
So what will happen?
My editors, my budget say will become 20 and will my lord will become eight by 20.
So what is it by.
So this is.
Two by five and two by five, zero point four, so that's why zero point four came here, then nine
by five, so nine by five is actually zero point four five.
So that is sorry, this is nine by 20.
So Nightmare 20 came out of zero point four.
Five is the load factor.
So we are doing rehashing two times.
So this is the first time and this is the second time we are doing leashing and my bucket size is 20.
So now let us try to get all the values.
So we are pushing the values now, let us try to find out all the values.
So what they are doing here, let us remove this one.
So let us find out all the values.
So this is key, and instead of calling on insert function.
We will get value function.
And I will give guys input.
So let us print Soucy out.
S.A.G..
And then.
Let us try to get value from this function.
So what I'm doing here, the court is exactly the same, I am deleting the key, I am generating the
value.
So there is no need to generate the value.
We will get value using great value function.
So I am deleting the key, then I am printing the key and finding out the value.
I'm calling to get value function and I'm giving key, simple.
So let's test our program.
OK, so this will be Smolkin.
So, see, we are getting our values so our get value function.
So these are the keys, ABC, ABC zero, ABC and ABC.
And these are the values.
One, two, three, four, DILTON.
So I will get value.
Function is working.
Correct.
Now we have to test one more function Bériot function.
So remove function.
OK, so let us test remove function.
Our map does not remove.
Now, which value we should remove, so let's say I want to remove a key one and.
Let us remove one more key so our map not remove.
And later this time, I want to remove the key six.
So what I'm doing, I am removing two guys.
So what is the value?
So if you can see, I will not be able to find out the game because the key is not present anymore.
So the default value that we are returning is zero.
You can see with the remove function, so see, this is the remove function.
So the default value that I'm returning is zero.
So for KBC even and for ABC six, the default value, the value I will get is zero simple.
And now let's also print the size.
So size should decrease by two.
So output should be it so here, this should be done, then I am deleting the two keys so the get value
for ABC1 and ABC six, they should be zero and the size should be eight.
So let's destroy our program.
So you can see for ABC when the value came out to be zero because we deleted the key ABC one, and similarly
for the ABC six, the value is coming out to be zero because we deleted the key ABC six and initially
outside of Austin, then our site.
Is it because we deleted Loki's Simple.
So our hash map is working fine.
I highly recommend you to read this computer, call yourself, because writing this computer code yourself
makes your concept much, much stronger and also your coding skills will improve a lot.
So whenever integration, we want to use Hashmat.
So what we will use, we will use in hash map.
We will never use the implementation, OK, we will never implementation by ourself in every caution.
We will use the inbuilt hash map.
So if you have any doubt, you can definitely ask me, I will see you in the next one.
Bye bye.