Hello all and welcome back.
So in this video let us now continue our discussion on hash maps.
And now let's try to implement our hash map from scratch.
First we will be doing open addressing.
And then we will move to the closed hashing or the chaining approach okay.
So now let us start with open addressing.
To do open addressing we will be maintaining two lists or arrays internally.
So the first one is going to be keys.
And the second one will in no way be a copy of this.
But there we will be storing the values.
Okay.
So let me write down the names.
Keys.
It is also known as slots.
And values.
So the idea is that in the keys list I will be storing the keys which you will be giving me and the
corresponding value at the same position.
So.
They will be equally divided with the same size.
Right?
Along with that, I will ask my user for the capacity.
So initial capacity, which my user wants to give.
And let's say we will also assume just maintain a size that how many have been added.
Okay great.
So let us start then everyone.
We are going to create a class Hashmaps.
In this class I'm going to create a constructor.
Now the things which I want in my constructor, they are just the capacity, right?
So how long we want it initially to be if we remember like it was eight I guess in our dictionary by
default the one we saw on Stack Overflow.
Maybe for the recent version of Python, if something has changed, we might have to see that.
But yeah, it also takes up the capacity as eight initially.
Great.
Now first thing self dot keys.
So I'm going to make this because it's a constant size.
So something like this right.
Everyone capacity.
Let us first define the capacity.
Capacity is equals to capacity.
So what we are getting here that's the initial capacity.
Everyone.
Now similarly self dot values is equals to none.
So to make it like an array right.
That is how we used to do it.
None and capacity.
Then the last one is self dot size equals zero.
Great.
So we have now made our overall structure where we have these things.
Now let us first write the insert okay.
So insert is also known as put there.
Here we will be getting two things right.
So self will of course be there.
We will be getting a key and we will be getting a value.
Do not, uh, we can actually keep this slots or let us just continue with keys only.
Okay.
Let us make it slots actually so that we don't get confused in this key.
And this keys.
Okay great.
So I think I have added slash slots.
Yeah.
Great.
So just the reason is that to avoid any confusion.
Great.
Now once you get the key and the value to add okay.
So for example let's say I am adding I am sending that hey store Apple with the value of say ten.
So this becomes your key.
This becomes your value.
Great.
Now what we can do here everyone let us see that.
What exactly can we do once we get this particular thing right.
And let me make it values.
So yeah Once we get the keys and the values, the very first thing which we have to do is to calculate
the hash value.
Right?
So that is something which we need the index where we will be storing these things.
Now to do that either we can write our own function the way we discussed, or we can take a prime number
and have its power.
Just one thing is there for words or for let's say, tuple or anything tomorrow that can be a problem,
right?
For tuple I will have to write another logic.
If it is a string, then other logic.
If it is a integer, then another logic.
If it is a float, then another logic, we can define them.
That is not a problem, but lots of logic we will have to handle for the same.
We actually have a hash function in Python okay.
So if let's say we give it one two, three and if I print it's going to give me a value which is going
to be an integer.
Let us run this.
See it is giving one two, three.
So for integer it returns back the integer if I give it 1.23, it's going to give me a very big but
an integer value.
I can even give it a, b, c it's going to give me some value.
There is one problem that it's negative for that what I can do, I can take it absolute.
And now I'm sure that it will be positive as well.
Right everyone.
So it's going to give me a hash value when I run it.
It's converting the same into integer.
Great.
So that's the thing.
The next thing if you are asking for hash value of a list, you will see a very common or known error.
Uh, not in absolute my bad hash.
See the error on Hashable type list.
We used to get this error when.
Let's say I'm making a dictionary D123 Equals one.
So when I try to make when I try to make a dictionary with key as list, I used to get the same error
on Hashable type list.
Okay.
So we are going to use this hash function everywhere.
So let us use this to get the hash value.
Okay.
We are going to call hash function.
Okay.
Here we have to make sure to pass the key because just through key we can get our overall hash value.
So let me define another function hash function.
What it's going to do everyone.
So it's going to just calculate the value via the hash internal hash function.
Okay.
So I will be getting self and key here.
I just have to return absolute of hash of whatever key you are passing me.
Okay great.
Once you have the hash value and I'm assuming that we will also compress it here only.
So to compress it we will use capacity.
Right.
So we have used capacity and we have the hash value.
We can also write it as initial index.
So if you want just for overall better readability it can also be said as an initial index which we
choose.
Okay great.
Now let us see what happens when we have to insert something in a, uh, open addressing technique.
So initially we have this empty array where everything is null.
For the keys as well as for the values.
Okay.
So just a second.
Let me make it a little bit space and let us write insert functionalities.
Let's say if I'm asking you to insert Apple here.
First we converted it into a hash, then we compressed it and we got a hash value of the index right
hash value or the index.
Let's say this index is somewhere at this position.
So this index overall which we have to add it is coming out at this position.
Okay.
What we will have to do then if it is none then we can directly just add this particular thing to this
key and this value.
So what I'm saying is if okay self dot slots right.
Hash value if it is equal to is none Then though, I think my work is done right.
If it is done then I can directly just insert it here.
So self dot slots hash value equals key self dot values.
Hash values equal value.
Okay.
So what effectively I have done everyone I said that hey this seems to be free.
What you can do is save apple here and here save let's say ten.
If I enter ten.
Along with that, the problem happens.
Let's say now I try to add orange okay.
With the 20 here as well.
I get the index which again is pointing to this particular position.
Then this is where I have to make sure that I do linear probing right.
Or any open addressing technique in this implementation, we can just do the linear probing.
Then I will have to make sure to find a place for this orange.
It might happen that some places are some things are already kept here.
Okay, so maybe let's say banana is already kept here.
Okay then we have to see that.
Okay.
Where can we insert orange?
The whole idea of open addressing is I have to make sure to make the space for my overall element,
or the key and the value to be added.
So else if self dot slots.
Okay, so there is one more case everyone just to first discuss on that as well, which we have to make
sure when let's say you send not as orange but you send apple here only you said here only apple.
Then what you will do then we have to make sure that we are going.
We will go to this position only.
But this time we have to update, not insert.
Right.
So in your dictionary as well, if we used to write for a element which is already present, it didn't
use to insert it again.
We didn't use to say that hey this will become Apple now.
No, we used to make sure that we are updating the value.
Okay, so pay attention if self dot slots hash value.
If it is equals to key.
If the position which I have got the index which I have got.
If it is equal to key, then what do I do.
Everyone self dot values at this particular hash value will be equal to value.
So I've updated it.
Okay.
Let me write it down as well here.
Update if key already present.
Great.
If this is not the case then I have to make sure that I get the new hash value right.
So new hash value.
Or we can say it as new index position.
For this, I will have to make sure that I do open addressing.
Right.
So open addressing or we just normally see that as rehash.
Okay.
So rehash this is the function which is known as I am passing hash value here.
So let us create this rehash function.
Then everyone what is going to be def rehash okay.
I will be getting a self.
And along with that I will be getting the old hash.
Whatever was the old hash value.
What we have to return here because we are doing linear program or linear probing old hash value plus
one and the same will be percentage of self dot capacity.
Okay, I think we have made a error in the capacity spelling and we have copied it all along.
Let me try if it can be corrected from here.
Yeah.
Refractor.
One minute.
So we have to refractor it.
Okay.
One minute.
Let me just see how it happens in VS code.
Capacity.
Okay.
I don't see it getting checked, so no worries.
Let me just quickly copy it so that we are sure we are not making this problem.
Okay, great.
So yeah, I think now it's fine.
We will be getting the new value.
Everyone from this rehash overall.
Let me write here as well.
Linear probing.
Done to avoid.
Collision.
Okay.
Straightforward.
Great.
Let us move forward once we have gotten this particular thing.
Once we have get the new value, then what we will do Then we have to make sure.
So let's say this time I'm passing orange and 30 and we are saying that the index again is this only
index again is this great.
So if this is the index again I will have to do the linear programming linear probing and move forward.
So till I am able to find none okay.
When will we stop.
When let's say I find a none here.
Right.
So great.
Let us see that particular thing.
So I have to make sure that I keep on moving forward till I find none.
Right.
So while self dot slots new hash value is not equal, none.
Right.
Or I can write it as is not none.
What I have to do, I have to just keep on calculating this value.
Right everyone.
So we will keep on calculating this value right.
Let's say I found my value here.
So we are able to find our value here only.
Or let's say banana was kept here with 40 okay.
And I found that orange I can just include here okay.
So orange I include 30.
Great.
Now let's think.
Have we missed out on any case?
I think we have missed out on one case.
The case is that if let's say you send orange with 100 this time, what's going to happen?
You will go here.
Okay, let me try it with the laser pen.
You are going to go here again because orange will have the same overall hash value.
You will see that okay.
This is not none.
Let me move forward.
Let me move forward and let me move forward.
You will find none here.
And you are going to introduce include orange again.
Whereas what you should have done see while you were inserting it can happen right?
That you didn't find it at the position, the initial position.
So you did by adding it just like we did here.
But again, if the person wants to update the value, then we have to make sure that we stop either
when we find none or when we are able to find our key.
So key was orange in the initial.
So we have to make sure of both these things, right everyone.
So what does that mean I should stop just here or oh sorry.
And self dot slots new hash value is not equal to my key.
So what does it mean that hey, keep on going until this is not null and this is not equal to key okay.
So we have to make sure that we continue probing until an empty slot is found or a key is found.
Okay, so that's the case.
Now again, if it's an empty slot, if self dot slots new hash value, if it is none, then what I have
to do, I have to do the same thing.
Just make sure that I add both the keys and the values, right?
So that's what we have to do.
Everyone let me just add it.
Yeah, great.
But if that is not the case then we must have said that hey key already exists and if key already exists,
then what we have to do we will be self dot values.
New hash value equals value.
Okay great.
So yeah I think this is done.
Let me zoom out.
Yeah.
See these are all the cases, I think, which we might have to handle.
Everyone where we have inserted our overall key and the value in my hash map which I have created.
Okay, great.
Let us move forward and let us now write the get part as well.
Okay, so what I'm writing next, I am writing next.
Get.
In.
Get.
What can we do?
Self key.
Okay.
So before moving forward let me just first explain you properly that what exactly is going to happen.
Uh, we will be having two overall.
These kind of list or array.
Right.
What we will be doing here is that first I will check if you are trying to add if I have space here
or not.
Okay.
If the space is there, if the space is there then I will go and just directly add let's say Apple Then
if the space is not there, then I need to do linear probing in linear probing.
I just keep on moving forward.
Right?
Everyone say I get.
I have to now.
Next add orange.
Okay, so orange is also saying that hey I want to come here.
If the overall index there is no collision then it's fine.
You will just insert it orange.
You will insert here okay with let's say 20.
Similarly banana can be inserted here with 30 okay.
So till now I don't guess any problem should be there.
Now the next thing is that now let's say if I give you banana again okay, we will keep on going.
So what we will do is we will keep on going forward.
Either we see banana because that would mean that we when we first added banana we did linear probing
and we were able to just get it here or we will get a none because in linear programming, the thing
is that if you get none, okay, it is for sure that it will not be after that, because we would have
done linear probing, right?
So we would have just got by a single step while going forward.
So these are all the cases in which we have to handle one thing more.
So let me just help you visualize this as well.
It's a very good tool which I found.
So one minute let me just copy and explain you why this as well is going to be awesome.
So pay attention everyone.
I will share this tool.
The link overall okay.
This is one minute.
Yeah.
So this is the overall flow smashing here we have taken a hash map of 29 size okay.
So first let us introduce 30 and see where it go.
30.
It will go on one.
Why?
Because 30% is 29.
It's one right.
Okay.
Now let us see one more thing.
What is 59 percentage?
29.
It's 259.
It's one.
Right.
So let me now add 59 and see insert.
See what's going to happen.
It's one.
It will go here but it will move by one step right now 59 plus 2988.
Let us do 88.
See insert it is one.
It's going to go here then go here.
Then finally insert it here.
So you see how linear probing is happening.
Everyone I will just share this tool.
It's an awesome tool for visualizing everything.
Now let's say if I add normally 100 I don't know what it is 13 so it will directly get added.
Now let's say what I'm doing.
Now let us let me try doing 88 again.
I think it is not asking me for the value, but it will say that it is already present.
See, this time it will not add 88 again.
It will stop here.
Okay.
No it is.
Yeah.
Okay.
So here it is.
Just having the case where it is supporting this thing that we have with Habit strings.
Maybe something ABC.
Hashing.
ABC so it is doing some complex hashing technique, right?
And it is able to okay.
So lots of logic.
It is applying.
No worries.
Okay.
So finally it is getting something done.
Let us increase the speed.
So very complex logic it is applying.
Seems like.
So once it gets the value by 29 it is adding it here.
Okay so that's the way it is handling everything.
So if I insert by 30 okay it is doing the hash string.
It is doing that hashing by some different logic here.
Great.
So here it is allowing duplicate.
But in our case we don't have to allow the duplicates right.
So it is getting added here.
We saw for 59 as well.
It's going to get added here.
And again if I just change it to quadratic probing then see everyone what's going to happen.
30.
See?
It's added here.
59.
It will be one as well, so it will increase and get it here.
88.
Here.
This time it adds here.
So see four values right.
So that's what quadratic probing is.
Now I'm pretty sure that now everything will be clear right.
Just one thing is that it is supporting your overall duplicates.
We normally don't want to support that okay.
In our case it's checking here then here.
Then it will add it here.
So after nine elements basically we don't want to support duplicates.
In our case we are implementing it just like our dictionaries okay great.
All.
So let us now move forward and try to write the code for Get as well, so we can quickly check it before
we write for the delete function.
Okay, great.
So for the get what we will do again is we will first get the initial index right.
How can I get that self dot hash function and I can pass the key.
So I will get the initial index where I believe it should be.
So I say that hey, your orange should be here.
Okay, let's say you added orange.
It should be here.
If it is not here.
Okay so first I have to save this position.
Current position equals initial index.
Okay, great.
The reason I'm saving this position is to make sure that if I circle back down to this same position
after writing the loop, then I should have some overall flag, which tells me that, hey, you have
reached the same position.
That means it is not present, because if I, let's say, ask you for pineapple here, then you will
circle back to the whole array and still you are not going to find anything, right, everyone?
So that's the reason we are just doing it.
Now we have to just make sure that we are running the same loop.
So what is the loop while self dot Slot's.
Current position is not none.
Okay, while this is not none, we will be keeping on increasing this first case.
If we found that self dot slots.
Okay.
Current position equals to key, then I can just return whatever is present in my values here.
So I find that hey I found my key right.
Great.
Current position.
Yeah.
Values is going to return.
The reason I have taken it as not none here.
Okay.
So I will explain this as well.
That why this is not done.
See when you add via linear probing, it is for sure that if say I am adding a range here.
Okay, then either it will be here either here either here I will not get none.
If I get none like it will.
Not that it will skip some.
None here.
Okay.
The very similar thing if I explain you using that visualizer.
So pay attention everyone.
What will happen if we just refresh it?
See if I'm adding, let's say 30, then I, let's say add 58.
Or it was 59, right?
59.
And then I add 88.
It will never be the case that it is going to jump something.
So now if I want to find 88 pay attention.
If I want to find 88 it will go here.
Then to the next one, then to the next one.
And get me that.
If let's say I want to find some 89.
Okay.
Let us see that it's going to come here.
It's not fine and not fine here.
It should stop.
So when it's found the none, it is going to stop because we are doing linear probing.
So it is not that ever we are going to jump to any particular position.
Right.
So once this is done self dot values then I'm going to find or change my current position to self dot
rehash and current position.
Right everyone Then just one more condition is required.
This will handle the case if we are not finding it.
But if the full overall array is filled, then we will reach down to this initial index.
If full is filled, then we should return none or we can return.
Not found.
Gone.
Full or better language traversed.
Full array.
Great.
If we come outside of this, that means that we would have gotten a none.
If that is the case, then also we should return, not found.
Okay, everyone.
So I hope this is clear.
Now let us quickly check this out.
Let us create a H1 hash map.
And I'm creating it just with three.
Okay great.
H1 dot insert.
Apple and ten.
H1 dot.
Insert.
Orange.
20.
Okay, let us just get H1 dot get apple.
Let us make it same.
Exactly.
Because hash will be calculated.
And let me print this print okay.
See I'm able to get ten.
That means that my code for this particular hash map is running.
Let us try to find banana and let us run this.
So it's saying not found.
The reason it is not saying traverse full because we found none before.
Right?
So it would have happened.
We will print it as well in the next video to see that.
What how exactly they have been stored.
Okay.
But it would have found none before.
That's why it is not basically saying that hey, I found a none.
So it is giving not found.