Hello all and welcome back.
So in this video let us now continue our discussion.
And now let us try to implement the rehashing.
So we discussed in the last video about the complexity involved in our hash map function, where we
understood about the load factor and the rehashing mechanism.
Right.
So the idea is same, that once our load factor become greater than, say, 0.75, then is when I will
be doing the rehashing.
Okay, we understood the whole concept, but let me reiterate that we will be making another buckets
array which will be twice the size.
Okay, so here it is not twice the size but should be fine.
Let me make this one smaller.
So somewhat like let's say this one okay.
So once our original bucket array gets filled and the load factor become greater than 0.75, we are
going to do rehashing Hashing majorly.
The change will be in insert code, but let us see if any other function will require changes or everything
is going to work fine.
Okay, so let us start with that everyone.
Pretty sure that you have understood the concept that why we need to do that for each and every key,
right.
So everything in this particular node of my linked list will have to go through the rehashing process.
We cannot just directly copy this head.
The reason is the key a final bucket index will change because of my this particular capacity change,
right?
So let me write that down as well here.
So I think we have discussed the same.
Let me write it in green here.
The final bucket index.
Will change.
Due to capacity Right.
So something like this is very, very important to understand everyone.
And let's just have a star on this.
So you never forget this.
Okay.
Great.
So now let us implement that everyone.
It's going to be pretty easy only.
But I will make sure that each and every thing is explained to you.
Great.
So let us go back into our code.
When we are inserting before returning we should now calculate a load factor.
Okay, I guess it is a lambda in like books or somewhere.
Okay, so I read it about in a book as well.
So it was used as a lambda there, but we are just writing the load factor.
Okay.
So what will be the load factor exactly.
Initially.
What is going to be the load factor?
I feel that it should be the overall size.
That is the number of things which we have added.
Right.
So self dot size which we are maintaining by self dot capacity.
Okay.
Once this load factor is greater than 0.75, we can make it as a constant as well outside depending
on the use cases, but we are taking 0.75.
We have to do something.
Okay.
Let us call this one function which we are going to make.
We have to do lots of stuff here, so maybe we can do the same here as well.
But it's always better to just create it as a function.
Okay.
Let us create.
Def rehash.
And we just have to send the self.
Everything is there.
Okay great.
So before moving forward everyone let us just try to understand a few things.
Let us just try to print this as well.
Okay.
Print load factor.
So it's going to be load factor like this.
Great.
So yeah let us try to add some elements.
We are adding the elements.
Let me take it as two.
We can add more element as well.
Let's say banana two.
Banana three.
And for the time being, let us just comment this out.
Okay.
So pretty sure that you must have done the get item as well.
Set item we did.
Create.
And I can just get the length.
Now if we run this everyone see.
Load factor 0.51.0 because we have taken it two.
Let us take it maybe somewhere around five.
So point two.
.4.6.8.
This is where my load factor is greater than 0.75 here I believe.
Hashing should happen to make sure that everything happens in a constant type, like all my operations
are constant time operation.
Okay, so let us now try to implement the hashing code.
Everyone load factor.
Great.
So this is where I have to now write the hashing code.
Let me just zoom in, get rid of the output window.
Cool.
So now let us discuss what exactly do we have to do in hashing.
Okay.
What are the steps.
So let me go to the whiteboard and let us see what exactly are the steps which we will have to perform
in my hashing.
Okay.
First is that we should save this old buckets, right?
We cannot directly say that.
Hey, my new bucket is twice the size.
So we have to save this old buckets.
Everyone let me write it by above so we can refer to the diagram as well.
First thing, save old buckets in some variable.
So I will say that hey old buckets you just point here the buckets array.
Right.
rewrite the normal buckets array which was pointing here initially.
I will say that hey, cross this and please point to this new one.
Okay, that's the very first.
That's the two steps which we have to do everyone.
So second is going to double capacity.
Doubling capacity is very very important.
We cannot just make the array.
The reason is that it will be used in hash function going forward everywhere.
Then we have to create a new buckets or ask the bucket array to basically point there.
Okay.
There is one more very very important thing.
See we are creating everything from scratch now right.
So we have to make sure that size we are also making zero because internally we will be calling the
insert function.
This will be clear when I do the same in coding.
And yes then we have to just for every entry For every entry, just insert.
So these are the steps everyone.
Okay.
So just writing them so that you are comfortable in understanding what are the steps involved.
First save the old bucket array.
You cannot directly say that hey this is my new buckets.
You will lose the access to the last one.
Second double the capacity.
Then we will create from that function which we wrote right.
Create bucket function.
We must have written the private one to create a new buckets.
We have to also make sure that the size is zero.
This I will touch upon in implementation as well.
Once this all is done, then we just have to go to each and every linked list.
Make sure that we are traversing the linked list till we get none, and keep on adding each and every
element.
Okay, so let us now implement this everyone.
Great.
So in the rehash first let us print that we are rehashing so that we get an idea that yes, rehashing
is actually happening.
It is not something which did not happen.
Great.
Now first thing old buckets equals self dot buckets.
Right.
Self dot capacity equals self dot capacity into two.
All I'm doing here is just doubling my capacity.
Something which we have done in dynamic array as well.
Right.
So that is how dynamic array is also overall implemented.
Then self dot buckets.
Now I can reinitialize it because I have saved the old reference equals self dot.
I think it was underscore create buckets.
This time I have to just pass the capacity here.
So that was the reason everyone I was passing the capacity initially as well.
Like in the last video, I didn't uh Us like told that ideally, if we just needed this capacity, we
could have gotten it using self dot capacity as well, right?
But we have to make sure that we are passing it so that we have this overall differentiation that yes,
this is now what I want.
So I am passing in my rehash function.
Yeah.
In my rehash function I'm specifically passing it.
So we know that okay.
In rehash it's going to happen.
Great.
We will get the same result if we don't do it.
But I believe that it is better because this is something which we have to control properly.
If by any chance this capacity change doesn't get into this create bucket, that's going to be a problem.
Now self dot size equals zero okay.
Why do we need to do that.
So pay attention.
Let's say till now we have added five elements.
Size will be five.
Pay attention.
What I'm going to do next.
For each linked list head in all buckets right.
Current equals each linked list dot head.
Okay, so I will explain what is happening here.
I am going let's say I'm on ten.
I just extract this out.
I am making the head as 49.
Now I will keep on going and inserting till I am able to find none, because each and every element
here need to be inserted.
So what we have to do here is even while my current is not none, okay, we have to make sure that we
move it forward.
So current is going to be current dot next.
Okay that is fine.
But along with that what we have to do self dot insert current dot key.
Current dot value.
Great.
So we will go back to insert.
Insert is going to find out this hash function.
In this hash function I'm doing this self dot capacity which is a changed variable now.
Okay.
So I will just explain what is going to happen when we insert it again.
Okay.
It is going to go to insert function which is here we are going to calculate the bucket index.
It's going to the hash function.
Hash function internally uses this capacity something which I have doubled here.
So that problem which we talked about okay.
After rehashing the hash index that will get handled here because everything is going to now go to the
right index.
Now once this is done we can actually return.
That is fine.
Just one thing more why size is required to be zero.
Pay attention when we are saying that insert here, it's going to increase my size.
It was five initially.
I am reinserting those five elements okay.
So I will be inserting these elements.
Pay attention.
Let me zoom out here.
Apple.
Orange.
Banana.
Banana two.
Banana three.
If I am reinserting them, don't you think that it will also increase the size again?
So for that particular reason, the small things we have to handle and the size we have to make zero.
Okay, reset size before reinserting elements.
So I made sure that these comments are also there for the specific things where we can make the mistake.
Okay.
So great.
Let us test this out everyone.
How can we test this out?
There are few ways we can test this out okay.
Let me showcase that for each LL head in HashMap.
Okay, print each LL head.
So it's going to show me five heads initially, right?
We are pretty sure that here the load factor will become 0.8.
It's five.
We are adding this particular fourth element At point eight.
Rehashing should happen.
So let me just print the heads here as well.
Okay, great.
So let us run this everyone.
What is saying object is not iterable.
Where exactly?
99.
Okay.
For each head in HashMap.
Okay, I will have to.
This HashMap is not iterable.
So range of length.
Okay.
No worries.
We have actually done this in traverse.
So when we print our length right we can check it from here.
Great.
So let us check that using length everyone should be fine.
So now let me run this.
See zero initially load factor .2.4.6 it.
When it became 0.8 what would have happened.
Pay attention.
So we would have started with a One minute.
Yeah, we would have started with the array of five once we entered these four elements.
These four.
We noticed that the load factor on my hash map is increasing, so I should have made it double ten.
Now I start to re enter these four elements.
Right.
If I enter the first one it is completely empty.
I enter the first one.
N is one bucket, P is ten one by 10.1, two by ten, three by ten, four by ten.
And finally, when I insert this last one after rehashing, this is where point five is.
Okay everyone.
So I hope this is the this thing is clear.
Just to showcase you that here rehashing has been completed.
What can we do.
So when we do rehashing at insert.
Yeah.
Let us do this and print the hashing.
Done, not done done.
Let us go back, everyone, and just match these drawings here.
See if I run this again.
It is saying after this for that rehashing has been done and the fifth one is now added into this new
overall 10th.
Okay.
The length is actually five because length gives us the size, not the capacity.
What we can do though is we can see this hash map and see this hash map.
Let me run this now.
So pay attention everyone.
Initially it was none.
None.
All were none.
Okay.
After that one minute we have it confused.
So we have this.
We can just comment this load factor for the time being.
So where we are printing this load factor.
Right.
See rehashing okay it did rehashing.
Now we are not printing anything and rehashing is done.
We started with a five sized hash map, but now see one,
123456789
ten.
I think we have missed.
We have to expand it.
Okay.
So this is one only right?
Now you will be able to see it clearly.
123456789 ten.
It has increased in length with ten.
And this is the exact each and every head.
So there is a overall two elements in this one index.
But you are able to see that more or less they are not uniformly distributed.
Right.
Again, if you will try to increase lots of elements then this will also get rehashed and we will have
more spaces overall.
So that's the overall benefit or idea.
They are not all going to the same I would say this thing same linked list, right?
If I run this again, maybe all of them will be separate as well.
See.
So now also two are going to same.
Now also two are going to same okay.
Seems like something gets same.
Only this Lisa.
Should be fine.
Yeah.
Now, three women going into the same.
So we're gonna need a lot of time.
But yes, normally we I see that.
Okay, now, see, we have run this and everyone has went on to a different one.
And now you can imagine that.
See, calculating that the hash function is pretty straightforward.
Once you get the hash function then you just have to go to that index.
It doesn't matter what the length of this is okay.
And that's the whole idea behind hash map that us in an awesome way.
We get a overall good time complexity.
Okay everyone.
So I hope the rehashing concept is clear.
Now you can remove these things.
I'm just commenting them for the time being so that this is not how like our end user should not have
any idea, right?
Internally, the dictionary will also be doing some rehashing, but we never get to know about that.
So just let us check the other function as well.
Everyone, let us now comment this thing or comment out on this thing.
Let us not print the hash maps Okay.
And let us just first let us check the Get function.
I don't think any change should be there.
It is working absolutely the way it should.
And I'm able to get all the values.
Okay.
So we have seen rehashing is happening.
We have seen insert is working fine.
Now.
Search is also working fine.
Get okay.
Now let us check for this as well.
And great.
So yeah seems like delete or remove is also working fine.
If you will just go through the code you will understand that actually no changes are required there.
Apple is removed from HashMap.
Key is not found now size has become four.
If you want you can see the HashMap.
After this it will be again a ten size only and key not found after four.
There are ten elements.
Okay, everything is I think.
Yeah.
So there is A12 element which are at the same place.
But after that everything is more or less uniformly distributed.
If you just have the size as S3.
Then I think three by three and finally five by six.
So two time rehashing will happen.
And finally we will have a nine size hash map.
So see here it will look.
It would have become one by three in this, then two by three, then three by three okay.
So at three by three rehashing would have happened.
This would have become two six.
Then at five by six okay.
At five by six it is 0.8333, which is greater than 0.75.
So six would have become 12 I guess.
Right.
So it should be 12 123456789 ten 1112.
Everything is separate and there are 12 linked list.
List or 12 is the head bucket length in my hash map now.
Okay everyone.
So pretty sure this is clear.
Now, what I would expect you to do is write this code once at your end.
Again, properly, just write the rehashing code.
Believe me, I have tried to keep it a lot easy so that each and every one of you are able to understand.
And tomorrow explain it to anyone in any interview.
Once this is clear, we have to still use dictionary, only the inbuilt one.
But I hope now you are able to appreciate that.
What exactly goes behind dictionary, right?
That is the whole idea behind learning this DSA algorithm and data structures because it explain.
It helps you to answer that why things are happening the way they are happening.
And now you are equipped with the knowledge through which you can actually use that and implement some
good complexity data structures or functions.
Right.
So in the questions you will still be using this dictionary only.
But this is asked a lot as well as used a lot.
The idea behind this.
So please make sure that you do practice that.
Now you will also have many assignments which you have to do using a simple dictionary, but I am pretty
sure that now your overall idea, your overall mindset will be a lot clearer.
Okay, so great everyone!
I hope that is clear.
Now let's meet in the next video.
Thank you.