Hello all and welcome back.
So in this video let us now move forward with our discussion on hash maps.
And now let's try to implement our own hash map using chaining.
So in the last video we were able to implement our hash map using the open addressing technique.
Now we did linear probing.
But I'm pretty sure that you can do the quadratic probing as well as just implementing another hash
function.
Right.
So different methods of probing you could easily do.
Now coming to implementation using chaining okay.
Many people find the code a lot difficult for this.
But honestly I like the code very much.
The reason is that it actually tests you on lots of skills.
So each and every thing will be a linked list.
So it tests on your understanding of linked list.
Along with that exactly how things are happening.
If you are able to just focus on a single operation and code it out, that enhances your coding skills
a lot.
Okay, so our approach here will be that one by one, we will try to understand each and every operation
and then try to write the method for it.
Okay, great.
So let us begin, everyone.
Now before we go to code, let me just first explain you the approach again.
Right.
Because if that will be clear, then it will be a lot easier for us to code.
So in chaining we will be taking one array or a list.
Right.
So let's say this is one list.
Now this list.
And let me make it a little smaller.
So.
Let's say this is the list.
This list is known as buckets.
This time we will not be taking two list one with keys or values.
Rather, we will be taking a single list, and each and every element of this list will be a linked
list head.
Okay, so understanding of linked list is very important if we want to implement the chaining, right?
Because each and every thing is a linked list here.
So effectively each and every thing here is a head of my linked list.
Right.
So something like this is actually happening right.
Initially there will be none.
But yes as we move forward.
So initially there will be none.
And as we move forward we will be adding elements just like we add in a chain.
Okay great.
So this is known as buckets.
Anytime you give me a key you will also be giving me the value right.
So when we learned about our linked list node we saw that how it can have a data and a next.
Now this basic node linked list node will change into something like this.
So pay attention everyone.
It's going to change into something like we will be saving.
So we will be saving.
Key value and the address of next.
Okay.
So this is how our overall node of a linked list will change.
So we will also have a key and a value.
So instead of data okay we will be storing key and value.
The approach is going to be the same.
I am going to find out that which bucket index where exactly my this element this entry wants to go
I will go there.
I will check if that is none.
If it is I'm going to enter it.
If not, I'm going to start my linked list next time.
If the element want to go to the same location.
Then, instead of doing or finding another place, I will be making sure that I add to it only.
Okay everyone, so let us see this in action as well because I want that here.
Each and every thing should be clear if, when, if we take a minute extra to implement, that is fine.
But you should have everything visualized properly so that you can explain tomorrow someone as well.
So pay attention everyone.
Uh, this is again a very good visualization, which I found.
I will be sharing the link of this as well, so pay attention.
See, this is one bucket for each and everything is none as of now, right?
Let's say it is having the size of 13.
Let's say I want to add ten.
So element ten will get added here.
See it started a link list.
This is none and a link list is started.
Now say I want to add 23 this time.
Also 23 wants to go to ten.
So instead of doing linear probing we add it to our head.
Right?
This particular visualization approach is not making any key or value distinction, but we want to make
sure that we are able to store key and value both.
Okay, great.
So let us start and do it step by step.
The very first thing which we will be working on is because the basic idea is the link list, right?
So we will be writing the link list operations first okay.
So will be very straightforward few of the operation we have to write.
Just so let us start with them everyone okay.
Great.
So let us actually create a file.
New file.
So it is let's say link list for chaining just to keep the code clean.
The very first thing okay is the node node of this link list class node.
Let me write ll node.
This time it is not having the data and the next it is having different things.
So self init key value.
Okay great.
First thing self dot key.
This is going to be key self dot value.
Going to be value self dot next.
Going to be none.
Okay we have take init here.
Okay.
So I messed it up.
My bad init.
And this is self.
Okay great.
So this is the node.
What.
Effectively this has done everyone.
It has created a node in the memory wherein we are having two things here.
So this is having the key.
It is having the value and the next which is none initially.
Right.
So this is how our node will be.
As we talked about.
We can have anything which we want to store in our linked list right.
We were earlier just saving the data.
but doesn't or doesn't matter.
We can say multiple things as well.
Great.
So this is done.
Now let us try to create a linked list class.
Okay a linked list class.
So this will be a little different because now I will be working on keys and value right.
So few changes will be there.
But I'm pretty sure that if you have written the code in the linked list module, you will face no problem
whatsoever in this particular understanding.
And the reason I am not copy pasting it is that I want you to understand that what exactly are the minor
minor changes which happens in different implementations?
Okay, because the real approach is just to implement, right?
We can anyway use the dictionary which is inbuilt in my Python.
But to implement, to understand and to explain we should be having a proper idea.
Great.
So very first thing is going to be just the constructor.
And I think I just need my head okay.
So initially as we take a linked list is going to be none.
Great.
Now let us see what are the different operations which we have to perform.
If I add 36 here it means and just focus on this particular node okay.
Forget all the other nodes.
As of now, I think that I am able to add to this particular linked list.
Right.
So there should be a function and let us make it add only if you provide me with a self.
A self will of course be there.
If you provide me with a key and a value.
Okay then in this linked list I should be able to add that.
So key value then new node dot next equals self dot head and self dot head equals new node.
This is the exact code which we write for adding to a head right.
So if you will see here so 36 plus 13 around 49.
If we add it is getting added to the head of complexity.
We have to do nothing.
Right.
Great.
We will come to our HashMap.
No problem.
But first we need to.
Make sure that how or what are the changes which this key or value is going to do.
Great.
So this is the add function.
Now let's talk about the next function which is going to be search I believe.
Okay.
So let's say if I want to search let's say I want to search for ten.
What will happen.
Key will be passed.
And then I have to search for ten in this particular linked list.
And I will be able to do that.
Once I am able to check or find my key, I will say that hey, I have found the same, so each and every
of my node will also have a search functionality where you will just give me the key.
Okay, great.
So add is done.
Now we are just doing the search functionality current self dot head.
So I will be starting from self dot head just like it happened here again.
Let us see that ten.
Fine.
See I went here then one, two three, four.
Unless it becomes none, right?
If I, let's say want to find for 49 plus 13 is 62.
So it will go here.
Not found, not found, not found, not found.
And it has become none.
So now we can say that it is not found right again.
Something which we have done while current is not none.
We will keep on increasing this current.
So current equals current dot.
Next.
Right.
This is what we will do everyone.
But if I am able to find the key, if current dot key is is equals to key, then we should just return
the node.
Okay.
So pretty sure that this is a clear a lot clearer.
And if you are not able to find anything, then we should return none.
Or we can return not found like none is as good as good to handle it as we want.
Great.
So this is just one more operation, everyone.
And we want to make sure that we are able to do these operations in my linked list only, so that the
code for my hash map becomes a lot clean.
And I think this is a very great strategy as well.
The reason for that is if we have these things separate, then I know here I just have to think for
the linked list when I will write my hash map code, I just have to think for my hash map.
Great.
So now let us write the next overall code.
So let's say I want to now delete.
Then the understanding again is very easy.
You just have to search for ten in a way okay.
And we have to delete it.
Okay.
So see it will going to search for this And it will delete it.
See?
Simple work.
Right?
If I say delete 11, then it's a problem.
The reason it will go here it is none.
So it will not do anything.
Element is not in the table.
Great.
So let us now see how delete will happen.
Everyone.
Delete.
Okay.
So self and you will give me the key.
So each and every thing is happening with respect to key.
Just that value is something which I am storing along with my key in the visualization which we saw
again.
We are just dealing with key.
It doesn't care with the value as well.
Right.
Great.
So now let us write the code for this.
What exactly do we need to do.
Let us understand that first.
Okay great.
So there can be multiple cases right.
Let us see that I think insert and search is pretty clear.
Let us see for delete.
Okay.
Delete.
We have multiple cases which we have handled in our linked list as well.
First, if node is head, that is pretty easy.
If the node found is head, then we can easily say that hey, just delete, right?
Not a problem.
We will just directly say that hey help head, please focus on the next one where you are focusing.
Great.
Second, when let's say we have a structure something like this.
So let me draw this linked list.
Great.
So let's say I want to delete this node.
What I effectively do okay are two things.
Either I should be on this node and say that hey, I have found the node I am focusing on now, this
node or what we can do, we can take a previous and a current as well.
So we can have this kind of a two pointer approach as well where.
Once I get that, hey, my current is this particular thing, then I can just ask my previous to.
Focus on this instead.
Right.
Something again which we have seen already.
Everyone.
These are the two approaches.
Now if you remember in questions also, you must have.
Used this approach so we can write on any approach.
I am going to use the previous and current one so that you are also aware of this particular approach
as well.
Okay, we will keep on going until we reach none because once we have reached none, then I can comfortably
say that that particular node is not present.
Okay, great.
So let us see that everyone what I have to do first current will be equal to self dot head and I am
taking previous as well.
Previous okay.
It's none.
Why am I doing it this way?
Pay attention.
Let's say I want to delete 36.
Okay.
See how it will delete it.
It will go here.
Then next, then next.
And now it will delete it.
Okay.
So we are following the same approach.
What we see.
That's the major reason we are not deleting it when we are on the previous overall node.
So while my current is not none while I'm saying the current is not none.
Now if see if current dot key okay.
If the key is equals to key which I'm looking for.
So I have given you a key here as well.
Right everyone.
If you find the key then we can delete.
But there are two cases.
First one if previous is none, what does that means?
If previous is none, that means that the current is head only.
So that means that we are removing the head.
Okay.
What does that affect?
Transforms to self.
Dot head.
His head.
Can you please focus on the next one?
Now it can be none I don't care.
It can be none as well.
Okay, let us see that.
Also 49.
49.
Go here and delete it.
So head, please focus on the next one.
That is what it has done, right.
Great.
So this is the one case.
Next case is when previous is not null.
If that is the case I just have to ask my previous dot next to focus on current dot.
Next right.
So when let's say my current.
This is the node which I have to delete.
I am on previous.
I am just asking hey previous, please focus on where current is pointing and this will be out of my
linked list.
So this is just what I have to do.
And if we have deleted it then we can return true.
We are taking a single case.
Only if this is not the case, then what I have to do.
I have to say that.
Hey, previous.
You become current and current.
You become the next one.
This is just the approach which we have to follow everyone and if we are able to delete, we will return
true, else we can just return false.
Pretty straightforward work.
Okay, pretty sure that if you have understood link linked list pretty nicely, we will be able to understand
all these codes right?
Will suggest to see the linked list module again if you have any doubts, but I'm pretty sure that I
have explained it again.
Right.
So not copy that so that each and every one of you are comfortable.
Great.
Let us write one more overall code because, uh, we have a good visualization here.
The same might not be present in our code.
So for that we need a traverse function as well.
Okay.
So traverse I will just be getting the head Current I will say is overall self dot head.
So my linked list head okay while current is not none okay.
What I have to do print.
I can just print the value and the key.
So current dot key using the formatting everyone so we can enter it here.
Current key.
Current value okay.
And we can just join it like this.
We have the end like this.
Great.
So this is what my traverses do.
And I should just keep on moving to current dot next.
And once this is done I can just print none in the end so that it is in line with my linked linked list
structure.
So once we create, we are going to see how that happens.
Great.
So now we have worked upon each and every element of my linked list.
Right, everyone?
Now, if all this I have written pretty nicely, which I believe we have, we should be very easily
now be able to implement our hash map.
Okay.
Please make sure that you understand each and every line in this code.
This is something which we have already done.
If you are able to understand this, then now hash map code will be a lot easy.
I have intentionally made sure that I am dividing it in such a way that it is very easy to understand
for anyone.
Okay, so great everyone!
Now in the next video we are going to start with our hash map using chaining code.
But honestly, I think we are done with 50% of the or even 70% of the work, because now we just have
to use this methods by checking that where my overall which overall index I have to work on.
Okay, so great everyone, let's meet in the next video and then just complete our hash map code.