Hi, everyone.
So in the last period, we implemented our own hash map, we implemented insert function, lead function
and search function now in this video.
Let us try to find out the time, complexity of our hash map.
And then we will also discuss the topic rehashing.
So first, let us discuss about the insert function, let us try to find out the time complexity about
the insert function.
Now, the insert function, it will take years and put.
Then the key will pass through a hash function, so it will give me the bucket index and then I will
go to the bucket index, so for inserting what we have to do.
So first of all, we have to traverse this link list to check whether a given key already exists or
not.
For example, you want to insert the key ABC.
So first you have to check whether the key ABC exist in the linked list or not.
So basically you have to traverse this link list.
So what are the time complexities?
So first of all, this hash function, this is not going to work.
It will take some time.
And similarly, you are trading over this link list, so there will be some time.
So first, let us define some parameters.
So what is and we will try to find out the complexity in terms of in so and is actually the total number
of entities present in the hash map.
So and is the total number of entries and it will be of 10 to the power five entries.
And what is l so for example.
This string ABC, so this hash function, it will not take on a certain time you have a string ABC.
Then why do you have to do so?
We're finding out the high school you are traversing this string, so EL is actually so this is the
length of the word, length of the word.
So in our case, we are digging string as key.
So what would be the time taken by the other hash function?
So the time taken by hash function is because of EL?
Simple now will be very, very small, so you do not have to worry about l l will be small, let's say
four or five or 10 20.
So L will be small as compared to total number of entries.
So it will be OK, let's say, for 10, 20 in this minute, but it will be very, very small as compared
to an.
Now, what we are doing so our main problem is basically this one, we are traversing this list.
So this is our main problem.
So in the worst case.
In the worst case, what will be the length of this linked list?
So in the worst case, this length of the list will be big often basically the length of the linked
list will be in.
In the worst case, what will happen so all the entries want to be present at this index, only you
got a hash function is very, very bad.
Fetch that all dentist wants to be present at this index only.
So in that case, the length of our linked list will be in.
And the time complexity will become big often and end is of the order to power five two, if you will
add the time complexity of hash function and this time complexities of this big off.
And then so the total time complexity in the insert function.
So this is big often for editing on the list and bigger of L for finding out the hash code.
Now see, PN is actually much, much bigger than.
So what we can do, we can assume that our hash code is constant.
So instead of big awful what we can do so we can assume that our hash function is taking constant time.
Big off one time.
So it is taking Constantine.
Now, volunteers are in the worst case, in the worst case, the total time complexity will be big often
when all dentist wants to be present at the same index.
But a lot of research has been done in finding out a good hash function.
So this case will never happen.
This case will never be there.
So I'm repeating myself.
A lot of research work has been done in finding out a good hedge function and this case will never happen.
So which case that all the entries are present at one index only.
So this case will never happen.
So that means this will never happen to time.
Complexity will never be big often so on an average, but we can assume so on an average.
So end is actually the total number of entries in the hash map and BS, basically the total number of
boxes available to us.
Basically this is Buckett says.
So in this case, in our case, I took the brigade size, I think, five so beastly packages, so on
an average we can assume that each box will contain and by the entries.
So on an average, Madugalle, assume that each box.
Will have and by Ventris.
So we can assume on an average.
Simple.
So now what will be our time complexity so on an average each while traversing the list, so the linked
list is actually of the size and maybe it has and baby entries.
So on an average, our time complexity will be and baby.
So this is on an average time complexity.
So we call this number and by B. So this number has a name and we call this number Lord Vector.
So Imbibes actually called load factor, and now it will do.
So what we'll do, we will always ensure that end by be is less than zero point seven.
So this thing, we will always ensure we will always ensure that, and maybe so this this racial overlord
factor is always less than zero point seven.
So that means if there are 100 entries in a map, so the number of boxes will be around 120.
So this number is not fixed, it can be zero point six five, it can be zero point it something something.
So basically, if you look at these numbers, if you look at the load factor, what we can see so we
can see that on an average.
On an average, each box will have less than one entry, each box will have less than one entry.
So this and Bybee's basically less than one, and it is less than zero point seven.
So obviously it is less than one.
So over time, complexity was and.
So basically our time complexities less than one.
So on an average, our time complexities we can see, say, big of often.
I repeating myself, on an average, each bucket will have less than one entry.
So every box will have a constant number of entries, so let's say every box will have gone through
a number of entries.
Let's say one box is having two entries.
The other one can have only one entry.
The next one can have three entries.
So basically the entries will be like the order one or two or three.
So basically the size of the linked list.
So let's say this is a long list.
So basically the size mailing list will be constant.
So on an average day will be less than what it is with the help of Lord Factor.
This thing will always ensure.
So on an average, each box will have less than one entry.
They are basically constant number of entries, so it might be less than one because this thing we will
always ensure.
So this number is called load factor and we can say our time complexities.
Big one.
So how we will ensure that our load factor is less than zero point seven.
So what I want to say is, how are we going to ensure how we can always ensure that and baby is always
less than zero point seven, so how can we ensure this thing?
So what is happening here?
Let's say the size of your budget, that is 20 now you're inserted 17 elements, then you inserted it
in elements, then you inserting 19 elements.
Basically, you are increasing the number of elements.
So obviously, what will happen, the value of N is increasing, but the value of Besim.
You are inserting the developer inside the backstory, so the value of and is increasing and the value
of B is remaining seem so how can we ensure this figure?
How can we ensure this relation?
So what we have to do, the only way with us is basically we will increase.
B, we will increase B, so what will happen?
B was want to hear what we will do.
We will double the size.
So we will double the size now, the areas of size 40.
So what happened becomes twice so big, become straight, so the denominator increased by twice.
So basically our ratio will become half because the numerator, because the denominator becomes twice.
So this ratio will drop.
So when the value of end is increasing and if it becomes so solvent and by becomes a zero point seven,
what we will do so we will.
So we will increase the number of buckets by two and then this figure will become half suddenly.
So basically and baby will become less than zero point three five.
And again, what will happen again will push the entries inside this, so what will happen, the value
of N will again increase the value of B remains the same.
So, again, as soon as the value of N by B becomes greater than zero point seven, what it will do,
you will increase be by two times.
So this time the B will become for 80.
So it was 40.
Now the value of B will become 80.
So again, this value will suddenly become half.
OK, so and by B will become less than zero point thirty five and this will go on.
Now, one more thing.
So initially you say the area was 20, so when you are making the size of the area 40 to when you increase
the size, but you have to do so, you have to rehash all the values.
You have to rehash all the key value-based.
You have to rehash all the loopier and this is what we call rehashing.
So if you will look at the hash function, so hash function comprises of two things.
First, one is the hash called So which is which will give me a fixed number.
And the second one is basically compressing function.
So earlier we were taking Mordente in this case.
Now, when we will rehash all these values, what we will do, our compression function will be more
40.
So it is possible that when 17, 18, 19, they were present in the same linked list, now in the new
linked list, the bucket index will be different because this time we are taking more 40.
So obviously this rehashing will take some time.
Rehashing will also take some time, but we will have to do rehashing after login payloads.
OK, we have to do reaction after very large intervals, so the frequency of rehashing will be very,
very small.
OK, so finally, what is the time complexity for the insert function?
So finally, the time complexities question, because the hash function, it will take big off time
and on an average each bucket will have only one or two entries.
So basically, we can assume this constant amount of work so big, awful.
We can also assume it is constant.
So on an average, the insert function takes constant time over time.
So if the insert function is taking constant time, then search and delete, there also seem so they
will also take constant time and this is the required time complexity.
So it also takes Konstantine now in the next to be doing what we will do.
We will implement this rehashing.
In the next video, we will implement rehashing with the help of Lord Fekter, we will check the load
factor and we will do reaction.
So I will see you in the next one.
Bye.