Hello all and welcome back.
So in this video let us now continue our discussion on hash maps.
And now let us discuss about the complexity analysis of our hash map.
So when we started with hash map, the main idea was that we should be able to do operations in a constant
over time.
Right now, as of now, we have very fabulously implemented our hash map in different techniques, which
we discussed.
Pretty sure that you have understood each and every one of them.
I have made sure that the code for that actually had been made a lot easy.
Okay, so do try to implement them as well from your side.
Now let's discuss the complexity analysis that in the end are we actually able to achieve what we want.
Okay.
So starting with complexity analysis let us discuss the overall uh insert function okay.
So the that's the very first function which we do that is inserting in my hash map, let's say n is
the number of entries.
Okay, so n is the number of entries which you are inserting in your HashMap and B is the size.
Okay.
So B can be the overall bucket size.
Great.
Now let's actually see what all are different things which are there for my HashMap.
When we do insertion.
I will be getting a key.
So let's say you give me.
Hey, add this key one with a value of 100 okay.
This key it goes back goes through a hash function.
Right.
Then gives me a bucket index.
This bucket index I.
Finally use to add to my bucket array.
So that is the overall process, which we do, right everyone?
Now let us see what are the different things which are involved in this when I'm inserting okay, in
the worst case scenario, first let us discuss about a few operations.
So first is finding the hash.
Finding the hash value.
Let's say it takes some O of uh maybe we can take length time okay.
Where the length is length of the key okay.
Now second is inserting in linked list.
So I know that I maintain a linked list here.
Right everyone.
So I am one minute.
Yeah.
So I am in a linked list here, something like this.
In the worst case, what's going to happen?
Each and every thing is going to come to this only.
Right.
So let's say you have added 20 elements in a five sized hash map.
All 20 have just come to this particular bucket index.
That's the very worst case which can happen.
Okay.
Let us try to even add more elements.
Let's say you are adding 10,000 20,000 elements into your hash map.
So everything is coming to a single position in a single bucket index, right?
That's the problem.
So two things.
First, uh, in worst case.
In worst case.
All can come to a.
Same bucket index.
Right and after inserting then I will have to get.
So search will become O of n will become o of n.
One thing more.
If, let's say our n is very high, let's say I'm talking in terms of millions, then I feel that this
particular finding the hash value.
Right.
This will become irrelevant in front of that.
Okay.
So you are taking for search.
You are taking o of n time.
N is let's say millions, billions.
Okay.
Something like that.
We can take we know in the time complexity then this particular big O of length operation that's going
to become irrelevant.
Like we are first finding that.
So that's the second observation.
First is this okay.
Then let's say the second second is n will be a lot lot larger than length.
So this hashing can be taken as O of one okay.
So this we have seen that it can be O of awkward.
So all I'm saying is hash computation is okay.
Constant is constant.
Great.
So these are the two observations.
Now this is when we are talking about the worst case when I will have to go to each and every of my
element, the one which I have added into my linked list for searching or deleting.
Right.
So we will be getting that.
That's a major aim.
If I'm storing anything, we have made sure that insert is a constant length operation.
Okay, because we are inserting at head, but search will show we have to still make sure that we are
able to get rather in insert as well.
We have to first check if that is present or not.
Then we used to update the value right everyone.
So if you remember in the insert implementation it's here.
Yeah.
So we used to first search right.
Then we used to insert it.
So it's also big O of N only we are not inserting without any check.
Right.
So it's also big O of n right.
Now what happened?
Right?
In real sense.
We don't have this worst of a scenario.
So what we take is that this hash function calculation.
Right.
So enough research, enough work has been done in this that what finally happened is that we can say
that they are going to get distributed normally.
Okay.
Like due to good hash code, which has been find out by research and everything, we are able to get
a pretty good overall, uh, uniform distribution due to which it doesn't happen that everything is
going to the same overall linkedlist head.
Right?
That is something which we have seen again, the hash where it is calculated.
This is what we make sure of.
Okay.
So normally.
Due to good.
Hash codes.
We don't Get this bad of a scenario.
And get a uniform distribution.
Okay.
So we get kind of a uniform distribution everyone.
What does that mean effectively is that now instead of o of n my complexity.
Okay.
So it was coming out to be o of n before.
It will be of the order O of n divided by b because b is the number of buckets.
Right?
So this is something which have been proven by research.
We have seen a lot of time that normally it doesn't happen.
But then also there is a problem.
Even if I am saying that hey uh it is n by b okay.
So yes, everything is going to get, uh, uniformly distributed.
What if tomorrow I am adding n?
Let's say I am adding ten to the power five.
in five buckets.
Then also it's a problem, right, everyone?
If you are adding a one lakh elements or 1 million elements in five buckets, then it's going to become
a problem.
Okay, so we have to somehow make sure that this n by b, this n by b remains in limit.
This n by b is something which is known as load factor, load factor.
And majorly we try to keep the value of this load factor close to 0.75.
Okay.
Let us try.
Let me show you that as well.
Again, these are a lot research based things.
So let me open Google.
And what is the good load factor value for a HashMap.
Or as a general rule default load factor 0.75 offers a good trade off between time and space cost in
Stack Overflow.
As a general rule.
So same thing is written right?
Again, it depends on how many places you might see that as a two.
Okay.
But let me first help you visualize that.
What do we mean by this .75?
What we are effectively saying is that for 100, right.
If the N is 100, then I will get my number of bucket as something.
This 133.
So one 3140 buckets we will be taking.
Okay, great.
Now this load factor, we have to make sure that we keep it around 0.75.
Or I can say less than 0.75.
How can we do that if you are increasing n this load factor is going to increase, right?
If let's say you are adding 150 elements and I started with 101, 50 by 100 will become 1.5.
So the way for that is I have to increase B okay.
So we have to again very important we have to increase.
B the bucket size the buckets array to keep.
Load factor in check.
Right everyone.
Pretty sure you will be able to follow through the conversation.
So the whole idea is that any time I found that hey, you are adding more elements then I can store
or I can not store, I can handle in a proper good complexity, that's a problem.
Okay?
Because even if the bucket size is low and if you add lots of element, then it's a problem.
So if the load factor increases then it's going to be problematic.
And if I'm able to maintain this then this kind of transforms.
If I'm able to maintain this, then the time kind of transforms to big O of one.
Right.
So this is what exactly happens everyone.
So I will explain you the overall way.
Load factor is proportional to n and inversely proportional to b.
We increase the bucket size.
So what happens is that now you will, uh, we maintain, uh, let me explain you here as well.
Uh, we have this bucket.
Okay.
We have this bucket array.
I know the number of, uh, basically the capacity here, how much we can store.
If you remember, we were also maintaining a size here, right?
The second I find that size by capacity, that is greater than 0.75, if it becomes greater than 0.75,
I do rehashing.
Okay.
So I will be making this of a size which is double.
So let's say if this was capacity then this becomes two into capacity.
So I have increased the size.
Once I have increased the size okay.
Then all we have is some element in a linked list here.
Right.
So each and every thing we know is a linked list.
So something like this will be there.
Then we have a linked list.
Now what I have to do effectively is initially everything is done here right?
Everything is done here.
Initially I will be focusing that each and every element I will pick up and I will just calculate the
hash again.
I will change my capacity and I will make sure that I am able to add them properly in this new overall
buckets array.
So this is going to become my new bucket array.
Okay.
And this is my old.
So I will make sure that I refer it to as old one.
Go to each and every linked list, each and every things which we have stored in that do the rehashing
and then finally able to add it again.
Now, many of you might have the question that Why are we doing the rehashing?
Can't we just insert it like this?
So let's say this is the head.
We are just saying that, hey, you become the full head or there is a problem in that.
Let me explain that as well.
So very important, pay attention everyone.
Let's say I add key one okay.
For this key one I get let's say 105 as my index.
Similarly for key two I get my sorry hash value as 115.
Let's assume initially the size of old one is old B is ten.
So it's going to be percentage ten.
Percentage ten it's five, it's five.
I will go to this fifth index.
Wherever this fifth index linked list is I will have one key one here okay I will have the key two here.
Right everyone.
So this is how we can find it if you ask me that.
Hey, can you give me key one?
I will calculate the hash.
Hash always is going to be constant.
So this will be always 105 and 115.
I will find out this to be five.
I will go here and say that.
Hey.
Yes I found your key five.
Key one.
Great.
So let me make it five.
But when my newbie becomes 20.
And if I just repeat the full process.
Key 1105 percentage 20 equals five.
You asked me that.
Hey, get me the key one.
I have copied the whole key one here.
So I am saying that the five is coming out to be exactly the same.
Okay.
So that is what we assumed.
Everyone Q one and Q two.
Okay.
Key one.
Key two.
Great.
I'm saying that.
Okay.
You want the key one?
Let me go.
Uh, 20% 105 percentage 25.
Let's go to the fifth index in this new bucket and I'm able to find it.
But for key two.
It's 110.
Percentage 20 or sorry not 110.
It's 115.
Percentage 20 coming out to be 15.
I will go to my 15 here.
Let's say 15 will be somewhere here.
And I will say that hey it doesn't seem to be here.
Okay.
Again very important concept should be properly understood tomorrow.
It can be a very good interview question as well.
And these are the kind of questions and the level of questions which are asked in an interview of a
good Fang or tier one level companies properly inside the understanding of everything which is going
inside, because tomorrow their expectation is that you should be able to write these complex things
yourself, right?
If you are able to understand this, I'm pretty sure you must be, because I have taken a very good
example.
Always remember this because you might have to explain this some day to your interviewer.
This is not something in ChatGPT or any AI can even explain this properly.
Always remember this example because this is how we.
This is the reason we do the rehashing.
In the rehashing, what we will do is to keep the load factor low.
Let me explain that in a new page every one one minute let us add a page so we will be doing rehashing.
Okay.
In my rehashing what I have to do to keep load factor okay low, which is n by b, all entries are hashed
or inserted to a new bucket array.
Right everyone.
So this is what I am doing Just I am entering, just doing everything, each and every thing to my new
bucket array.
Okay, all entry are hash into a new bucket array.
Why do I do it?
So time complexity.
Okay.
Remains.
Big-O of one okay.
Which is big O of n by b.
So now you know why is this will be the case again?
This is going to be the same for insertion, for deletion and for finding.
Right.
So everything is we are getting big O of one.
And this is the reason if you will see in the code which I have written, we are maintaining this size.
We are sending this capacity in a create bucket.
So now all we have to do is we have to make sure that we can handle this rehashing.
Okay everyone.
So pretty sure, uh, the overall idea about the complexity is clear in a hash map.
Again, it's not an easy topic.
It's not something which is very intuitive to get, but this is the exact reason due to which we are
able to get everything in big O of one.
Okay, basic idea let's keep the load factor in check load factor the load which my hash map is having.
Let's keep this in.
Check.
If the load will be checked, we will be able to get a good overall complexity.
Okay everyone.
So in the next video now we are going to make sure that we just write the code for load factor as well.
Now.
Oh sorry rehashing as well.
No.
So we will calculate this particular load factor every time we insert.
Once this is over 0.75 or we will see 1.5 or 0.75.
Any value which we want, we will do the rehashing.
So just that is left.
Now once we write that down, our hash map is going to be very good in terms of complexity and everything.
Okay so cool everyone.
Now let's meet in the next video where we will write the code for rehashing.