Hi, everyone.
So now we will start implementing our own hash map using separate chinning.
So what will do, we will create a class map.
Now, inside this glass map, I was told I will have variables, key and value, I will have gained
value now in built hash map.
This is actually a template.
So key can be anything integer, flawed, double string student, etc. and similarly in map values,
also a template.
So value can be anything in the character, anything student, anything basically.
But.
In our implementation, we will take as a string and we will take value as a template in our Hashmat
implementation.
So I am taking Gey as a string.
So they the reason behind it, because, for example, Yorkeys, a student, if you will take me as
a student, then how you will be able to find out the high school.
So that's why I am taking key as a string.
So if you want to write a general code, if you want to write a generic code, basically if you want
your kid to be a template, then basically you have to define a way for finding out the code for each
type.
But here for our ease of implementation, I am thinking to be a string and value will be a template.
So I'm repeating myself, what do we have?
So this is my bucket, daddy.
Let's see, the size is 20.
And each bucket will represent the head of a long list.
Simple now inside one node.
So this is a node not of a long list now of so I'm going to take a string for key.
My value will be template.
So we value and obviously we will have next pointer.
So our next point, North Star, next.
So I am taking it as a string via string because we know how to find the hash code for a string.
If you want to write a genetic code, basically, if you want your key to be a template, then you have
to define the hash code for each type, for student, for integer, for double for characters.
But here for the ease of implementation, I am taking key as a string.
Simple now after this.
So what is the entry of entry.
So my entry will look like this.
Node V start.
So basically each entry is a is representing is containing the head of a link list.
So that's why this is so this is at entry.
OK, now I want to create an eddy, so I will write star and letter.
The name of that is it's.
So this is my area, so I'm repeating myself, so this is one entry, so how one day will look like
so this will be a..
And since it is a pointer to the head of the linked list.
So this will be NovaStar and I want to create an array.
So that's why against that and the name of that.
But it's simple.
So apart from this area, apart from this backstory, what else we need?
So we need a variable count.
So discount will store how many entries are present in my map.
OK, Nemirovsky value beer.
And similarly, we will also need a variable number kids.
So what is no good?
So all you can say, Buckett says.
So, for example, the bucket size is 20 here.
So we need these three variables.
And similarly, a normal store as I value V, a template value and a next pointer simple.
So now let's start writing our regular.
So first, I'm writing the code for this one, for creating a. so I have a Class A..
So class, let's say, nor is Map A..
And obviously so we need three variables, let's make them public, so the first one is actually string
string.
We need a value, our template value and similarly, we need a next pointer.
So map not start next.
Now, since this class is using template, so I have to write.
Template type name be.
OK, so DV is used here.
Now, let us also create a constructor.
So I have to episode so this constructive will take the values and put.
Stringy and value.
So this Rakowski and.
Similarly.
This added value.
His value.
And my next point, there will be none.
Simple, now let us also create our districted.
So I have this distractor.
And this destructive will destroy.
Next point, Denso.
It will destroy next winter, so I will write the next.
Now, when you are writing the next.
So basically, this is your budgetary.
I want to delete this whole link list.
I want to delete this whole link list, so what I will write, I will write to delete next.
So by writing the next, what will happen?
So this whole list will be destroyed because this is recursive.
OK, so this whole list will be destroyed because it is recursive.
Now, let us also create this glass glass map.
So this glass will have Buckett then count and similarly, no kids, so this bucket is using a value.
So our template value.
So I have to write template type NIMBY.
So this map glass.
Is actually using template.
So let's say the name of the class is Minyip.
So this class will use a template, so let's include.
So template.
No public, so what do we want to so first of all.
We need buckets to map.
Value is V..
So this is map old.
A.B., so this is one entry, this is one in three of the three, and I want to create an array.
So WINSTAR And then buckets, let's say the name of the Adès buckets.
Simple, now we need a variable count to store how many entries are present and let us also take a variable
number.
What is the size of the area?
Simple.
So let's make all these properties as private, let's write private here.
And now we will ride public.
So let us write the contract for this class, so my map initially the county zero.
So the count is zero and let's say the size of the.
At initially, let's say it is five.
And then let us create already so buckets is new.
Map A. We start and no gets.
So what is happening here?
So now we have created this number, Cotati.
So we have this Buckethead.
But each and every.
So each entry is containing a garbage address.
Each entries containing a garbage address and know garbage addresses are very dangerous, so what we
will do, we will iterate over this barcode said, and we will put.
In each entry.
Now, one more thing, so here I have taken all these things, so all these three variables are actually
public.
So what should I do?
I should make them private.
Why I made them public, because all these three variables are will be used in this class.
So all these three variables are going to be used in this class, so that's why I made them public.
But I believe what we should do, we should make this very private.
And then with the help of friends classes, what I will do, I will make this class a friend of this
class.
So that's how this class will be able to access the private properties.
But since we are not learning the concept of the classes.
So that's why I made these things public.
Simple.
OK, so now let's do this thing instead of garbage address.
Let's put.
So, again, ideally, these three variables should be private, but these three variables are going
to be used in my class, so that's why I made them public.
But if you want, you can write private here and then you can make this class, my friend of Mechanoid
Class.
So that should work.
But since we are not learning French classes, so that's why I made them public.
Now, what we have to do so garbagey this is are very dangerous, so we will make them null.
So buckets of a.
Mesnil.
Now, let us also create their districted.
So this is glass distractor, my distracter, so what, it will destruct.
So what?
It will destroy.
So it will destroy this BUGALDIE OK, we have to destroy the Bacardi.
So what do we have?
I want to destroy this Bacardi.
So if you didley destroyed the Bacardi, it will simply write delete buckets, then what will happen?
So you will not be able to delete this link list.
You will not be able to delete these link list.
So what we will do first, we will trade over liberatory and we will delete all the link list.
We will limit this oil link list.
And finally, after deleting all the link list, we will delete the obligatory I'm repeating myself,
but we will do so.
Basically, each entry is a long list.
Each day is a long list.
Now, what I want to do, I want to delete this whole.
So what I have to do, I will go through each and every element and I will destroy the list first after
destroying the list, and then I will destroy the book.
Teddy, if you will destroy the bacteria first, then there is no way for us to delete this link list.
So let's delete link list first.
So that means we have to wait it over, the Bucket said.
So delete.
Buckets of far.
So this is a recursive function, so our whole linked list will get deleted.
Now after destroying the linked list, I can destroy the adding.
So delete delete bucket.
Simple.
So now what we have to do, so that is right, some function.
So, for example, size.
So this is what it will return, it will return me how many elements are present inside my map.
So basically I have to return.
Count, so I will return this count, OK?
I have to return the site, that means how many elements, how many loopier I present inside my map
so I will return count.
Now, what other functions we need in our map, so there should be a function, get value, so there
should be a function, get value and it will take as input and it will return the value.
So I need this function get value.
It will return the value.
We will retain value of retape.
Now, similarly, what else we need?
So we need insert function now this insert function, what it will take.
So it will take key and value so stinky and we value.
So that we can insert values into our map now, we have great value, we have installed we have sites
function, so we need one more function, remove.
So the return will be void.
Well, remove and what it will take, it will take years input and it will remove that entry.
So instead of returning type void, what do you return, pipis?
So this remote function, we remove the entry and it will also return the value, it will return the
value corresponding to the Gilinsky symbol.
So let's start with the insert function, let's start implementing insert function, so how can we insert?
So basically.
Quite insulting, I will have a key and I have a value, so this guy will actually pass through a hash
function.
This key will pass through a hash function, and that hash function will give me Buckett index, the
index at which I have to insert my entry.
So basically, first of all, we have to write this hash function, I want to insert I want to write
this function insert function.
So first of all, I need to find out the value of Bookit index for finding out the value of market index.
We should have hash function.
So let us first rate the hash function.
So what do I want to do, something like this, so Buchardt index.
So what I will do, I will write a function, get a good index.
And I will pass key, so now let us write this function, get Buchard Index, so obviously this function
has to be private.
So get market index, what it will return, so it will return any integer.
And what it will take so it will take.
Stringy.
So how can we complete this function?
So basically there are two parts of this function get market index.
So there are two parts.
So our hash function, so this and get market index, it does nothing.
It is just the hash function.
So this house function has two parts.
The first one is finding out the hash code and then applying decompression function.
So applying the compression function is very, very simple.
We will just take percentage but size.
In our case, our bucket size is actually represented by a variable number.
It's.
Now, how can we find the high school, so if you remember in our last lesson we discussed, so you
have a string ABC and we will represent this string ABC as no no with BCB.
No, with BSP, so this ABC, it is nothing, it is just the value of a multiply Bisquick.
Similarly, the asset value of B multiply B and similarly the asset value of C, multiply Butel, the
power of zero and B the prime number.
So let's say in our case we are taking B 37.
You can take any prime number.
So generally, the large number is better.
So I'm taking 37 now, how can we find this value?
So basically, what do we do?
We will start our trading of the string from the end.
It will take the string in this manner from end to this start, and we will calculate our record.
So let's calculate our high school.
So what do we have here?
So initially our hash code is zero, so let's take a variable hash called.
So initially, our high school is zero and what we have to do so at the end.
What we have to do then we have to apply the compression function, so I will return high school, then
I'm applying the compression function.
So this is no good.
Simple.
This one, no, so I'm a blinding oppression function.
Now let's try to find out our high school.
So what we have to do, we have to start out from the end.
So let's do it from the end.
So ECLSS Guitard.
Sighs Minus one, and I didn't get close to zero, I minus minus.
So hash called.
Plus equals two, so what we have to do, so this guy, the character will be multiplied with.
A base value, so initially this base value is one.
Initially, the base value is one and our prime number B is actually, let's say 37, our prime number
is 27 and bases when so initially for the first time, it will get multiplied with base.
And then what we will do so base equals base multiply B BS our premium, but.
Now, what is happening here?
So suppose you have this string ABC.
And what I want to calculate the value of a multiply be squared, similarly, the asset value of B multiply
bruited about one and the value of C multiply P to zero.
So this period about zero, it is one.
I'm calling it as BS.
So this is base basis one then.
So this is part of the Power-One.
So what will happen based will get multiplied with B, so base will become B here and here for A what
will happen based will again get multiplied would be so p multiply P so base will become P squared simple
and GFI is basically the current character.
Simple.
Now what is the problem with this whole.
The problem is very simple.
Our integer, our values will become out of range.
So these variables, so base is getting multiplied with 37 and similarly, the hash code is increasing
at a very fast rate.
So hash code and base.
They are increasing at a very fast rate.
So what will happen, they will become out of range of the interior very, very fast.
So how can we avoid this?
So what we will do?
So there is a property of more or less operator by operator.
So, for example, you have three numbers, let's say N1.
And to an entry.
And you have to find you will multiply all the numbers and then you have to take percentage are so there
there's a formula for this and the formula is you do like this and when Morde are.
Then you multiply it with N2 Marda, then you multiply it with entry big Mordred and then take Morde
R for the complete one.
So let's take an example to suppose you want to find out.
So this is for any number of men, for any number of men, not just three, it can be four, five,
six to seven, nine, 10, anything.
So let's take the number.
Let's say I want to find out for multiply seven and more three.
Let's say I want to find out this answer, so it will be so this will be 28 more three.
So it is one.
And now let us apply this formula.
So according to this formula, it will get converted into four more three, then multiply with seven.
More three.
And then take more three for all.
So it it will become when then it will get multiplied.
So this is also one.
But multiply one and then I have this more three.
So what is one more three, so this is one.
And you can see our answer, you see?
Now, in our caution, in our problem, what we have to do, so we are returning percentage, no buckets,
so what do we do?
We will apply the number of bullets at every step.
We will use this formula.
So it will take.
So what I am doing, I'm calculating my high school.
And then at the time of returning my household, I am applying decompression function, so take decompression
friction, so take the compression function inside, so apply the compression friction at each point
so that your number becomes smaller.
It will not get out of range.
OK.
So what is happening here, base is increasing at a very frustrated has is also increasing at a very
frustrated and we want to store them in India, we want to store them and individual variables.
So what we will do?
We will apply percentage no buckets at each step, so what we will do?
So harsh is.
Hash called percentage number, it's.
And similarly, base is also increasing at a very fast rate.
So basically, this base percentage.
No, it's.
So why we are doing this percentage so that the things are smaller, so that we can keep our things
smaller, and while this is correct, this is correct because of the property of more or less operator.
OK, so these are the properties of the more or less operator.
And we are doing this because we want to make our things.
We want to keep our things smaller.
So I will get back to the index function is ready.
So now let us complete our insert function.
So gutbucket index, I will give guys input and it will return me the bucket index.
Simple.
So after doing this, what is the scenario?
So I have in the inside function, what do we have?
So basically, I have this Buckett index.
I am able to find out the Buckeridge index.
So we will pass through the hash function and hash function is returning the budget index.
So now for the insert function, I know at which index I want to insert.
Now, how do we insert?
So at this point, what do we have?
So I have a list at this point.
So what they can do, we can insert our key will appear at different.
So how can we insert I will make a node.
So this node will point towards the original head and this bucket will point towards this one, but
is this correct?
So this is not correct.
We will insert that front.
So there is no problem with this.
This is correct.
But directly inserting a different this is wrong.
Why this is wrong?
Because we know the keys.
The keys are unique in the hash map.
For example, you want to insert ABC?
The ABC and the values to and suppose ABC's already present.
Suppose ABC is already present then, but they have to do so.
Our first step is basically when you reach the head of the list, so you will traverse this link list.
We will have to traverse this link list so that we can check whether the given already exists or not.
So, for example, initially you have this value ABC and you have ABC and the Values one.
So he inserted ABC Common.
OK, you inserted a bicycle motion.
Now you want to insert a comma, too, so the values get that values getting updated.
So what you will do, you will traverse this long list and then you will find, yes, ABC is already
there.
You will Maggi.
So ABC is already there.
Then what you will do, you will update the schedule so the value will become to OK, value will become
to.
Now, if you get something like this, the F and then three.
So basically what will happen?
You will I did this long list and you will not be able to find the key beef in this linked list since
you are not able to find this guy.
So that means this guy is unique.
This guy is coming for the first time.
So in that case, we will do this approach, will create a new node and we will insert the node at different.
So let's write the code.
So after finding out the background index, now let us find out the head pointer.
OK, so what is the point out?
The is actually.
So this is my head, but it's very.
And I will pass this index, but good index.
OK, so this is the head of the list now.
We have to do first, we have to traverse the head of the linked list.
We have to traverse the complete list so that we can check whether the given case already present or
not.
So let us trade over the long list.
So what will do?
Vieillard is not acquisitional.
We will do Heracles next offered.
OK, so we are traversing the list and we have to check, so we have to check.
So is there a..
Is there a. whose value is basically close to the given key value and if are able to find that node,
then you have to do.
You do not have to insert anything.
You just have to appreciate the value.
So.
That Norvelle will get updated to Disvalue.
So this has value and then you don't have to insert you can back later than simple.
Now, what is happening here?
So what I'm doing.
So this guy is actually passing through a hash function and it is returning me a bucket index.
So this is Buckeridge Index.
Now, what I am doing so this is my book.
So let's say this is the budget index.
And then we have a linked list here.
So where does this head?
So this head is pointing towards the head of the linked list.
And now all we have to do so I suppose first you inserted ABC.
Cameron, so ABC Cameron is already present now the query is you want to insert ABC Clamato so you can
not directly insert the key because in MAP the keys are unique.
So what you'll do, you will insert you will basically traverse this link list.
So I am traversing the link list, Bilitis in order to move ahead.
And basically, you will check, you will check.
So whether this is already present.
Yes, this guy is already present.
So hedgie is equal to the given key.
OK, so if they had the key is equal to the given key.
So that means you do not have to insert anything.
You just have to update the value.
So initially the value was one.
Now the value is two.
So here ABC cameraman was present.
Now instead of when you will write to.
So you will update the value and then you can return nothing else.
But if I will reach this line.
Basically, line number seventy five, so that means.
I teach needlepoint, so this is null pointer, so if I am reaching the null pointer, so that means
so this is null point if I am reaching the null pointer.
So that means this gurantee ABC's not present, for example, for the key, the ECF.
Now for the the ITF, if you will, little bit over the kid, the effort is not present, so finally
you will reach the null pointer and then what we have to do.
So first of all, we will create a..
DCF and let's face value is three, so I will create an audio commentary, then this D.F. commentary
will point towards the first node, will point towards the head, it will point towards the head.
And then what I will do, I will update the herd.
So this budget, budgetary, this budget, and they will point towards this newly created node and we
will delete this link.
So Steps is a very simple first step, is basically creating this new node, then inserting at the head
and then basically this.
We will update the head and we will unlink the original.
So at this point, what you have to do.
We have to insert a different and we already know how to insert a different.
So basically we have to create.
A new first.
So let's say its name is Naude.
So this is new Map Naude.
And if you can see, I already have the constructor, so with the constructor, so this is the constructor,
so I have to Paskey and I have to pass value.
So we already have constructor, so I have to parseghian value key and value.
OK, so this one, this one and this one value, so I'm thinking in value.
And then what we have to do.
So I will do Naude next.
So not I don't think it is actually this one.
Had so I have to find her again.
So let's copy this one and let's be attrited and then what we have to do, so we have to update this
value, we have to update our head so.
This is actually my nolde.
So what I'm doing here.
So this is actually.
The linked list, and I want to insert a different salvo in starting a different I created a new node.
So this is node then?
This is the first step.
And the second step is basically a link.
This node and this node will point to this node.
So I'm doing just the same.
I'm creating this new node.
Then node next is pointing towards the first node and then I'm updating my head.
So one more thing.
If you remember, we have a variable count, so I have to do count plus.
Plus I have to do countless lists.
So this very well will store how many developers are present inside the map.
Now, one thing I am not doing countless bets here.
I'm not doing countless puzzle here because here we are just updating the value.
We are not inserting a new developer here.
I'm starting a new developer.
So that's why I did countless press here only.
So what we will do so in the next video, we will write the code for get value and we will write the
code for any more function.
I will see in the next one by.