Hello all and welcome back.
So in this video now let us move forward.
And now write our HashMap class using chaining which we will be using to implement.
Finally our HashMap which we can use as well.
Right.
So in the last video we were able to write the linked list modified linked list class where we have
the cell key and the value operations which I will be requiring.
Now the reason we have have all these operations here is that we are able to think in terms of linked
list, right, which is going to be the major node of each and every hash map element, which I will
create.
Right?
Just as we saw in the visualization.
Great.
Now let us move forward and write our hash map.
So first thing from linked list from chaining import node and linked list.
So what I wrote I am just importing here so I can use that great class hash map and let's say a map
using chaining.
Great.
One thing more everyone.
As of now, let us not focus on the overall complexity and stuff.
We will be having a very good discussion on that in the next video.
So right now let's just focus on the implementation that how exactly things are going to happen.
We will understand how the complexity we are able to achieve what we want and everything right now.
Let's just quickly try to implement it in a best and the easiest way possible.
Okay, great.
So based on our discussion we are going to create a constructor.
And in this constructor I will be giving the capacity how big I want my hash map to be.
So self dot capacity equals capacity.
We can create a self dot size as well.
Uh we created this in our open addressing as well.
But there we didn't add or subtract to it.
So you can make that change okay I think we forget to add one when we were able to insert an element
or delete when we were deleting our element.
Okay.
So something just we have to make sure of that.
So let us now go to board and understand one more thing.
Everyone see something which you had discussion in the last video as well.
Uh buckets array.
So the buckets list or array which I have to create this time it will be a overall continuous right
nodes of linked list.
So what I have to effectively do is each and every one of this should be a separate head of R New linked
list class.
Write new linked list which we have worked in the last video which contains key and the value.
Okay, great.
When we used to work for none okay.
We used to write something like this.
So this is how we used to define a fixed size list in the starting analogous to array.
Say capacity.
Great.
So let me create that as well.
Self dot buckets equals linked list.
Okay.
Let me just make the name capital just to make sure of the followed convention linked list into capacity.
Okay great.
I hope that seems fine to each and every one of you.
I honestly have a problem of this problem with this particular implementation.
Okay, let me explain that okay.
Let us take a take up this particular file and let us understand why this is wrong.
This is wrong as of now.
Okay.
I will tell you why this is wrong.
Let us understand this.
See, let's say I'm making a bucket.
Say, which is this?
Into three.
What effectively I have done is how?
Like this code gets run in the back end.
Again, these are some things which we should be very clear about, which we should have a very good
idea because they can ask in an interview as well.
I must have created an head.
Okay, which will be none initially.
Let me call that it is created on 0X1 hundred.
And I'm saying that hey, make three copy of this head something like this.
So my linked list or sorry, my bucket list is something of this sort where I'm pretty sure that you
will be able to see some problem.
Each and every head is just pointing to the same address, which I believe is very wrong.
Reason it is wrong is that if you make change into any of them, if you add an element here, it will
get added here as well.
It will get added here as well because they are pointing to the same thing.
It is just like saying that three people, they are no different.
They are just having the same name, everything same and they work on this like they are exactly the
same people.
You have just made the copies.
I wanted to made head of type linked list, but they should be different heads, right?
So let us see that in practice as well.
So pay attention everyone for each head in buckets print buckets.
Oh sorry.
Print each head.
Right.
Uh, let us run this now and let me show you.
See.
Okay.
It is not showing the address because it doesn't know how to print.
Let us see the reference of them.
Okay.
Identity of an object.
See, all are exactly the same.
So that's a very, very big problem if we make changes into any of them.
It's exactly the same as, let's say, if I add ten here, everyone will be having a ten.
So we can even see that.
For example, let's say this should be linked list object.
So the class let's say if I add a element okay at the zeroth of let's say add and what we have to do
key one and let's say value is hundred okay.
So what we have done here everyone let us see I want you all to understand these things in a lot depth
okay.
Because these are the basics for anything.
So for example what we have done I have created these three heads.
I am saying that they all are pointing to the same index.
If I add this key one and 100 here, ideally everything should be empty.
The other one should be empty, right?
We should not add anything here.
Let's say what exactly is going to happen here.
So I have added to the first one for each head in buckets.
Instead of going to the ID, we have to do each head dot reverse.
Okay, great.
Let us run this.
Okay.
Attributeerror load object has no attribute current.
Reverse code current.
Okay, so we have made an error.
Let us correct this.
Great.
Now let's run this.
See how we have key 100 in each and every one of them.
Right.
So in each and every one we have this particular index.
How can we correct that.
Let us see that.
Exactly.
How can we correct this particular if we make it as a list via list comprehension.
Right.
So all of you will remember what exactly a list comprehension is.
If I just run this okay three times now, every time we will get a different head and I can prove that
as well.
See?
Print.
Uh.
Each head.
So in list comprehension.
What's going to happen now, everyone?
This linked list, it will run three times because it's in a loop now.
So a new head will be created.
And if I make it now.
So let us create it and see.
Now just key one is having this particular 100 key one and 100 others are empty.
Okay.
So yeah pretty sure that you will be able to understand this everyone.
We have printed the nun and let us actually we could have just call it like this.
So we don't see this nun as well.
Great.
See?
So yeah.
Key one is this.
Okay then this is the next one, which is nun and the next one.
So a little bit thing to always make sure in Python.
Let us now go back to our HashMap here what we have to do.
Instead of doing this I will create a internal function let's say self and let me make it private,
only create buckets where I have to just pass the capacity.
Right everyone.
So def under underscore create buckets in this I will get capacity.
Could not have sent that as well.
But it's fine I guess.
And what we have to do buckets equals we can write it in a loop as well.
But I'm pretty sure that list comprehension you all have studied in the previous videos.
So for I in range capacity and I can return this bucket.
Great.
So now we have created our bucket as well everyone.
Now let us try to add.
Okay.
Now let us try to add or put anything into our HashMap.
Let us get rid of this.
Yeah.
Till now we have created our empty bucket array which is having each and everything as a separate head.
now.
Insert.
Okay, so I will be getting a self and I will be getting a key right along with that because it's insert
I will be getting a value as well.
Okay great.
So the very first thing what we have to do everyone pay attention.
If I have to insert anything into my linked list, right.
If you have to insert.
Then let's say you ask me to insert key one and 100 only okay.
Or Apple or 100.
This will have to pass through a hash function will have to pass through a hash function.
And it will tell me a index.
We call this index as let's say bucket index, which we will get after compressing this to the size
of my bucket.
Right.
Once I have this hash function, I will just be adding it into my bucket array.
Write something similar.
We did.
We saw in the visualization as well.
If I provided, let's say 101st, it will convert it into index.
So it is nine percentage 13 and it is adding nine here.
Great.
So first let us calculate the hash function everyone.
So bucket index okay.
Similar approach.
We have to follow self dot hash.
Let's say function okay where I will just be passing the key.
Now we can write this hash function easily def hash function I have a self I have a key okay.
We use the hash uh this particular hash function in the last one right.
So hash key we were able to write using this particular thing which I see, which I think is a pretty
good overall hash function.
We can again write our own as well.
Just then we will have to make sure that we handle different cases for string.
It will be having something different for.
Tuple it will be different list.
Of course we cannot support.
So here what we just have to return absolute of hash key.
Whatever is the absolute and percentage self dot capacity okay.
Same thing was happening here.
If I provide 110 uh the hash is 110 in this case okay.
So we are not calculating hash in some complex way.
I just percentage that by 13 which is my capacity.
So see it is six.
It will get added in six.
Okay great.
Once I have my hash in the bucket index then I have to get the particular bucket.
Each bucket is a linked list.
Head right so buckets and bucket index.
So now I found out that hey it has to be added on six.
It has to be added on six.
Great.
Before adding now I have to of course first made a first sorry search, okay, if that is already present
or not.
So bucket dot search.
Now this is the benefit of creating those functions right.
So see this is the search function it takes in from head and tell me and returns me that particular
node.
If it will be present okay I will get that node.
If it is not present then I will get none.
Now my logic in this hash map will become very easy.
See if node is none.
That means that I don't have this.
If you don't have this particular node, then we will have to add that.
How can we add again bucket dot add key value.
I don't have to take any problem of anything right?
For linked list logic.
I have actually written in my linked list which I am using for chaining, and that's the major benefit
which you will see while you write the code.
Now, many places, or even when I learned, I learned it in a way where every code was inside this
hash map using chaining class, which makes this a lot complex.
Okay.
But now it is a lot easier for you.
Self dot.
I think we have created size so that we can add by one.
Okay.
Not to miss it out in the open addressing.
Please correct that.
If it is not the case then in my node we have the overall node.
With that key I can just update the value.
See how easy it has become right?
Update existing key with new value.
All right everyone.
So this is done.
The insert is done.
Now let us write for search okay.
Self and key.
So I'm calling it get to not confuse it with the search here.
So we will be able to get insert and then finally delete.
Okay great.
Now let us see for get uh this particular search option what we have to do.
If you are asking me to check for anything.
Okay.
One minute.
Yeah.
So if you're asking me to check for anything, let us first create a new page.
Again, the idea is same.
You will ask me that.
Hey, search this particular value.
You will give me a key.
Let's say key two and say 200.
Or let's say 105.
I will first make this key go through my hash function.
Right.
Once I have the particular bucket I will go to that bucket.
And because I have very nicely handled the search in my linked list, I have the head.
The problem just reduces to searching in this linked list, right?
Searching in this linked list.
So a major benefit.
We actually have to do very less things here if you will pay attention.
What I have to do.
Everyone pay attention.
First, let me copy this thing because this we will have to do every time buckets and bucket index.
And we get that particular bucket.
Now what we have to do node is equals to bucket dot search with this particular key if I am able to
find it okay.
So if node is not none I can just return node dot value.
Else I can maybe return.
Hey key not found right.
Pretty simple now because of this particular handling.
And the best part was while writing this linked list code, we don't have to think of hash maps anyway.
Great.
Now let us write the code for delete similarly.
Okay, so def what have we used here?
it is.
Delete here.
So let us use remove here okay.
Remove it.
So again in remove I will be getting a key and only a key.
So let us understand on delete as well.
Everyone delete.
In delete what happens again.
Let's say you are asking me to delete key three okay now I don't need anything in search.
Also.
Actually we will not be having any value, right?
We just do the search by this particular key this time again.
Also I have to.
One minute.
Yeah.
So this time again I have my buckets array.
I have to just make sure that it goes through hash function.
It goes through this particular hash function.
We get to this particular array or we get this particular head.
Ideally this just changes into finding that key in my linked list okay.
And deleting it.
So pretty easy.
Again delete in my delete in linked list right there.
We are already handle handling if it is there or not.
So let's pay attention everyone.
See again it's going to become a lot easy.
So let us first get these buckets again.
So I get the bucket and the bucket index removed okay.
What I'm saying removed bucket dot delete.
Hey just go and delete my key okay.
How easy it has become right everyone if we say that hey if removed is not none.
So let us say see here what he does.
Pay attention if we find the key.
Okay, we are returning.
True.
Okay, so we are returning true and false.
Okay, great.
So when we are able to delete, we are returning.
True.
And I think one thing self dot head, we should return true here as well right.
If we find the key, then we should actually return true in both the cases after checking it.
So this true can be here.
Little bit correction.
So this true.
We will be doing or returning whenever we find the key.
If the previous is none that means I have the key in my head okay.
So let me explain you that as well.
Everyone uh let's say we are inserting few things.
So 23 insert then 23 plus 1336
3649.
49 and then let's say 62 as well.
Okay.
So I'm just adding 13 because all of them will be having the same key.
This is exactly the same thing which we are doing as well.
We are just keep on adding.
On my overall node when I search, let's say if I'm searching for 36, this is how I search.
It will go.
It went here.
Searching, searching 36.
It has found it will return me right.
Next thing when we have to delete, pay attention.
Let's say I want to delete 36.
It is going to search again.
And this time we are saying that.
Hey, if we have deleted them or not, so it is returning.
True.
That's when we have the previous here and we made this connection.
If I want to delete 62, which is at my head here, then connection which will be made is something
like this.
Okay everyone.
So I want all of you to properly visualize and imagine this in your brain.
This is the connection which we will create.
Now let us delete this and see if the is like this was going to happen.
And yes, this is what is happening.
Great everyone.
See, the thing is that if you are able to visualize properly, if you are able to think the operations
in your mind, then coding always becomes a lot easy because coding is just writing what's on your mind.
It's not something we have to remember.
Okay, Great.
So we are returning true here.
So if my removed if it is true, then we can just check like this.
If removed equals to true, then what we have to do.
Everyone.
First let's delete the size and let's print that.
Hey, I have removed okay, so let's say Qi and Qi is removed from hash maps or hash map.
But if this is not the case, then I should print that.
Hey, Qi is not there.
Can you please check?
So let's say Qi.
Qi not found.
Okay.
Something similar we can do here.
If I want to delete ten, see ten, it will go here.
So ten is there.
My bad.
Let us remove.
Now let's delete ten again okay.
It is saying element deleted.
Let us say ten again.
It will try to search.
It will not find.
So it will return false.
Once I get false, I have to just set the same thing a ten element not in a table, right?
So I have to just one key not found in HashMap.
Great.
So I think this also done my uh, delete as well.
Now, many of you might be not finding this a lot difficult.
The reason is that we have divided it very smartly into two things.
Right.
Let us write two more codes every one so def underscore length okay.
So this is what length function works on.
If we write the length function right.
So it is going to be everyone uh just return self dot size.
That's the reason we are maintaining the size and def print.
So these are the basic function from loops or the magic functions.
So for I in range.
So let us understand how print will do okay.
Pay attention everyone.
If I have to do print.
I have this buckets array.
Let's say it is something like this.
Okay.
So pay attention everyone.
What's going to happen?
Uh, each and every thing is a head here, right?
Whenever the head is not null, I have to just print each and every element.
How can we do that smartly?
I think the way we can do it smartly is we have the traverse function.
So we have written the traverse function right.
So we can call it we don't have to write any nested loop here because of the smart traverse function
we have written.
So self dot capacity I will go to each and every head right.
So if uh let me just do it.
That should be fine.
If buckets uh self dot buckets of I is not none, then what we have to do Self dot buckets.
Dot buckets of I dot traverse.
Okay.
So this will make sure of everything.
Let us just add it.
And yeah I think this works pretty fine because this expects that you will return a string.
We can just return it here.
So this traverse function is making sure that I am able to print everything.
We will get it as in terms of bucket.
But again we can handle that should be fine.
Okay, great.
I think using the smart technique of this linked list approach we are able to finally do this.
Okay.
Let us now try to test it out everyone.
I'm pretty sure that each and every thing is clear.
If you have any doubt, okay, just try to see that part.
Once again we have used the visualization.
We have tried to understand it, understand it pretty well as well.
So the major approach is that everything should be a lot clearer.
Right.
So see hash map let's say hash map.
So this is what is the name of our hash map using chaining.
So now this is my hash map everyone hash underscore map dot insert insert insert.
Is the function right.
Yes.
So let us insert Apple and say 100.
Uh, one thing I think which we missed out, let us take or send the capacity as 13.
By default I am taking it 13 because in our visualization we have 13 only.
Okay.
So or let me pass 13 here as well.
So it will get overall checked.
We can take it as a default argument.
I'm pretty sure all of you are comfortable with default argument.
So let me add Apple here.
Okay then let us see orange with 105 and then hash map Dot insert banana.
Okay.
Will.
Let's say.
200.
Great.
So let us first run this.
We are not getting anything, not even an error.
So let's hope that it is working fine.
Now print hash.
Map dot.
Get.
Okay.
Apple.
Orange and banana.
Make sure of one thing as well.
I can write it here as well.
Key should be case sensitive.
Why is that?
Uh, let us try to understand this quickly.
Print hash of orange.
Hash of orange.
Pretty sure they are going to be different.
Let's run this one.
I'll run this once Okay.
So 100 105 200.
So seems like this is working.
Let me just expand or like just extend it a little.
See it is completely different right.
So there should be case sensitive for short.
Now they are same.
Okay everyone.
So please make sure that you understand this as well.
It should be case sensitive okay.
Don't make this error once I have done this.
What can I do now?
Let's say I delete from my hash map.
Uh, it's not delete I think.
Remove.
Yeah.
So Apple and then let us try to get this again.
Along with that, let us try to get the length of our hash map after deleting.
And now run this.
See what it is happening.
We added three apple orange and banana.
Okay.
So they must have been added somewhere.
Key apple is found from hash map.
So.
Oh, sorry.
Key Apple is removed from hash map.
Key not found.
And two is the length.
Okay.
We can do one more thing as well.
Print hash map.
Okay.
So this is going to run our str function.
Okay.
So we are getting lots of none because we have called it on traverse on I okay.
But we are able to see that okay.
Orange and banana is here.
If this bucket is not none each and every bucket.
If it is not none.
So we might have to check that.
But I hope you're able to see.
So I think there should be 13in number right?
123456789 1011 1213.
So it is just printing everything.
We might have to check.
Exactly.
There are just one thing more I would like to explain and check.
Let's say we make a single overall a single length hash map.
Okay.
Now let us try to print this.
Everyone okay.
So pay attention.
I will be printing it after inserting as well.
See what happened.
Banana 200 is the first, uh, last one.
Orange 105.
Apple 100.
And then we have the nun.
Then 100.
105.
200.
100.
105.
200.
It is in order.
Apple, orange and banana.
Key.
Apple is removed.
Key.
Not found.
Size is two.
The length and the final hash map.
Okay.
It's not a linked list.
It's a hash map.
200.
Orange.
Now, what is happening here?
We just have a single overall node or sorry, single node.
A single node of head linked list.
Head in my hash map.
Well, if that is the case, we will keep on adding in each and every thing.
Now, many of you might have a doubt, which is that basically on the complexity, right?
That if you have a single node, then how can we say that it is O of one?
Before implementing everything which we learned about our dictionary and the hash map or hash table,
the major benefit was that we will be able to do everything in big O of one, right?
But here, if, let's say it is a single, uh, length hash map or normally in 13 size hash map, we
are adding, let's say 130 elements.
Then won't it be a problem right now?
In the next video, we are going to discuss each and everything regarding the complexity and also how
can we correct the same.
Okay, so in the next video we are going to do that everyone.
Few changes will be required in this structure.
Till then, I want each and every one of you to write this complete code from scratch.
Okay.
I honestly have made it a lot easy because if you will see this code, I don't think you will find it
this easy anywhere.
So please make sure that you write this code, the linked list code as well and this as well.
And also add that set item and get item.
So we saw the same in the open addressing right where we were able to add using hash map something like
this.
So I can say Pineapple equals 100.
It will fail right now.
Name.
Hash map.
See?
It will fail.
Hash map object does not support item assignment.
Right.
So how can we correct that?
I can just do it for this.
Set item.
And you have to do for get item then.
Okay.
So self key we will just be getting the key and the value.
And we have to just call self dot insert key and value.
See everything is fine now right.
So yeah pretty sure that you must have enjoyed this coding.
Uh from my end, I have tried to make it a lot easy because this is normally found to be lot complex,
like the most difficult code when even I was learning coding.
So on that note, just please try to just implement this once.
And in the next video, let us now talk about the complexity involved.