Hello all and welcome back.
So in this video let us continue our discussion on hash maps.
And now we are going to try and implement our own hash map okay.
So the overall process is quite long and there are many terminologies and operations involved.
So we are going to break it down.
Just one request.
Please make sure that you are seeing the full video and make sure that you are completing this in one
sitting, because that will be helpful in understanding each and everything and how they are connected.
Okay, great.
So now let us start everyone.
Till now we have understood what hash maps are.
Why are they required?
Okay.
And what are the different ways in which we could have implemented our hash map?
We saw how using linked list they can be done.
That's the first way.
Second was using a BST.
Again.
We have done each and every operation of BST, so that is something which you can also try on.
And the last one was using hash map or hash tables or something, which we have to now see that how
in one approach we are able to do the same thing, right?
Great.
So let us start now.
Let us first thing that which is the value which we know, which can help us to get anything in a,
AO1 time.
Right.
For example we have array or list, right.
Which we know something in which we can access anything in O.
One time we had this discussion when we were studying about linked list as well.
If I know that let's say this is where my list start list or array okay.
Going to use them interchangeably and I want to access say fifth element, then I can easily write a
of five.
And this is independent of.
Length right.
So it doesn't matter if it's a ten size or ten length array, 20,001 million if you say that.
Hey, you want to access the element at position five, then I can easily get you that.
Right.
Doesn't depend on length.
So this means that it's an O of one operation.
So that's the very basic idea that we are aware that in a link, in a list or an array.
Okay, we are able to do this thing via indexing in an O one time.
Now hash maps are going to be.
A derived data structure.
So we have implemented like we have talked about how they can be implemented by linked list and BST
for a good o one complexity, we are going to implement them by using a list.
Okay great.
So let us move forward everyone.
Now let us talk in terms of list exactly how this thing can be done.
Right.
Great.
So now take an example.
Say we have some five positions.
Okay.
So we have these five positions with us.
These are the five positions we have say zero one or let me say I it will work should be fine zero,
one, two, three and four.
I ask you to store these values such that tomorrow, if I want them, I should easily be able to access
them.
Okay, so let's say tomorrow, if I ask you that.
Hey, I want three, then you should not have to travel the whole array, okay?
You should be able to store them in this particular array or a list, whatever you want to imagine in
such a way that it gives me one overall retrieval.
Okay, so how to store for zero one retrieval.
For this?
Pretty sure that all of you will be able to think that it's pretty easy, right?
We just have to store each element.
At index equal to element.
I hope that makes a lot of sense.
Right.
Equal to element.
So each and every of this element.
Okay.
What can I do.
I can store zero here one here two here three here four here.
I can say that these are my indexes.
And now you should be able to give me them.
Right.
So if I say tomorrow that hey I want three.
You can say that go to index three or go to your index three.
And you can get the value there.
Right.
In a way what we have done is we have applied.
So this is known as hash function.
Right.
What we have applied okay.
When we said that okay these are the values.
And I want to get corresponding keys for them through which I can store them in my area.
They are actually known as.
This process is something known as hashing, where we have applied the hash function where n is equals
to n, right.
So this is some way which we have done.
Now let's talk about another example.
Okay.
So let's say now what we are given is we have been given an array again okay.
This time I am given 012.
And let's say.
1234.
But I add one more element which is 255873 okay.
And I make it six as well.
So I have just done two things I have added another space seems fine and I have added one more element.
Now the logic which we applied in the last overall problem that would fail here, right.
Because ideally, what you can do, you can still say that, hey, I want a very big array or a list
where this many elements are there, but I hope you understand this again then that it's going to be
a lot of memory wastage.
Right.
So a lot of.
Memory wastage.
If we take a big array or list right.
Yes.
We can still say that.
Hey give me A255874 sized array.
You can store it in the last.
If I ask you tomorrow you can see that hey go to this index okay.
Whatever is the element, that is the index.
I can do that.
But what about those middle space which is getting wasted, right?
Something which we cannot now afford.
Right?
Great.
So we are seeing that how it is inefficient, right?
It will just lead to lots of memory wastage.
Let me write that as well.
Inefficient.
Okay.
Waste of memory.
Great.
Now let us take one more example here, everyone.
Right.
In our dictionaries we saw that how I was able to save each and every thing, be it a tuple, be it
a string, be it any number, anything.
So if I am tomorrow giving you, let's say, keys like this.
Key one.
Key two.
Key three.
Then what should happen?
How are we going to save them?
Again the same problem indexing.
We saw that it's a constant time operation.
That thing was very good.
Okay.
So we should write it down as well somewhere.
I think we have not written.
We should write it down.
So access via indexing.
Is oh one operation.
So we see that how efficient it is right.
It's a constant time operation.
All is good.
But I hope you understand the problem.
Now what if we are not able to map the thing which I want to store into indexes?
And in dictionary we saw that how all these items.
Right.
How all these K1, k2 and k3, they are also we are able to solve as a we are able to store okay in
a dictionary as keys.
So that means one more thing which is that key can be anything as well right.
Key can be anything.
And I believe that our aim and our aim should be.
To somehow.
Change the given key.
Into an integer.
Right into an integer.
And this is what hashing help you to do.
Okay, so this is where we will use hashing.
So what exactly hashing is.
Let us see that everyone hashing.
Say that hashing is actually just a function okay.
So we saw that in the first example as well.
There is a hash function okay which I'm going to apply.
It will be taking in key okay.
It will be taking in the key and it will be giving me out the integer for that.
Right.
So let's say a very good hash function for this problem, which we did earlier.
It can be something like this.
So for example, it can just say that hey, get the last element and hash function can be anything like
it's totally a random function.
It's on you.
You can take anything.
Okay.
So I can just say that hey give me a hash function I'm applying on this keys.
It is just I'm getting the s of minus one.
So in this way I will get one, two and three.
And I will store them here.
One here, two here, three here.
It's a perfectly valid hash function.
So I will just repeat what hashing is or hash function is.
Hashing is this process of changing anything which you are given into your overall integer hash function
is the way you do it.
So hash function is helping you to do it.
You have to make some.
Overall I would say logic based on which this will be converted, right?
That's the whole idea.
So once you have converted, once you have gotten the index, then we can save that in my array.
Right?
Great.
On that note, there is just one more terminology which I forget.
So this array or list which we create.
This is something which is known as a bucket array right.
So this is known as bucket array.
So we say that we have buckets here where we can store things right.
So I will repeat what all we have to do.
We will be given some keys.
We have to define a hash function.
That hash function is going to give me a integer.
Once I get an integer then what I have to do, I have to just make sure that using that integer, I
treat that as an index, and I am able to store my elements or the values in the bucket array.
That's the basic idea, right?
If I am able to do that, then I will be able to get them tomorrow because this hash function remains
the same.
Like it is not that while storing you are changing it, while getting you are changing it.
No, it will always remain the same.
It is okay so it doesn't changes.
It will always give you the same value.
If it gives different value then you have messed up your hash function.
It is dependent on something it should not be.
So no matter if I ask you, hey, what is the hash value for 5000?
Or let's say for this key one, it should always give the same thing.
That's the basic idea.
Everyone.
Okay, great.
Now many of you might be thinking that all is right, but what if tomorrow I have something as, say,
key 100 here?
Won't we get into the same problem again then?
Uh, key 100.
I will get, let's say, 100 out of it, not zero.
I'm saying that let's get the integer.
Uh, my bucket array is of just size four.
How I'm going to save it.
Or let's say tomorrow we create a hash function where you gave me key one, key two, something like
this.
And I'm generating some number.
Right.
It has some number let's say key One.
2345.
Key 1558.
I'm getting the integer.
Okay.
And they are having the size which is greater than my overall size of the bucket array.
So perfectly valid things which can happen everyone.
So let us see a little bit more about this hash function.
This hash function okay.
We say I have two two things to do.
So hash function.
The first thing it does it gives me a hash code.
What's a hash code.
Key converted to integer.
So if I give it let's say key 11345 it will give me 11345 or anything based on the logic.
Second thing it does is it compresses that key.
Okay.
The completion is required because let's say if you have just a five size array okay, five capacity
array key compressed.
To have an index.
Present in bucket array okay.
So pretty logical thing to do a very good compression function.
Something which is used a lot is percentage like even I can write it down as well modulo operator.
Because we know that let's say for percentage n okay it values always is from zero to n minus one.
And for my list or array as well, if it is having size n then it goes from zero to n minus one.
So I will be sure that whatever value I am getting after compression that will be present in my index.
Right.
So I'm just I can just use the modulo operator.
That's an awesome compressing, uh, mechanism or something which we can compress.
Okay, great.
So now it seems that we actually have been able to compress.
Compression seems fine.
Now let us talk more about the hash function or how we will get this hash code right.
See, hash code can actually be anything okay.
So we can have.
Any hash code okay.
Which converts.
Key to integer.
Right.
So that means that I can have even identity as a hash code.
So you are sending me let's say zero I will give you back zero.
Okay.
So I'm saying that identity is the one, the something which we used in the first overall problem,
right?
Okay, that is fine as well.
It will work, but it will work just for integer.
Let's see how we can handle for strings.
Okay, so for string this will work.
But what we will do for our strings like let's say if I'm giving you now ABC.
Again we cannot take identity here.
Right.
So that's the same problem we got in keys.
Great.
Here what will happen?
We can maybe we can use the sky values.
So we know that internally each and every string is having some sky values.
Right.
So ABC can have 97 a is 97 plus 98 plus 99.
So 97 plus 98 plus 99 okay great.
There is one problem in this as well.
So first I will talk about what is a good hash code, right?
What is a good hash code?
I believe a good hash code is something which makes sure that overall output is uniformly distributed.
Okay.
We can have even a hash code that always gives you, let's say one.
Right.
It's an identity, not identity.
It is just some constant hash code.
But that will be a lot bad, right?
Anything which I am sending.
You are saying that.
Hey, store it at one.
How am I using it then?
My whole aim of hash code is that I am able to better utilize this particular bucket's array, right?
The better I will be able to utilize it.
So my whole aim is to make sure that uniform distribution is there.
Okay.
So that is pretty self-explanatory.
Uniform distribution is there.
Now in the above where we were adding the sky code.
This though seem to work fine.
There are a few problems.
Let us talk about them.
What happened is that, uh, let's say in the last question, in the last video, we talked about anagrams,
right?
So A, b, c and c a b are anagrams, and thus they will have the same hash code again.
Okay.
So it kind of will give you pretty bad, uh, results.
One more thing is that many of these words right.
So let's say a b c a b, they will be very near to each other.
Like let's say if tomorrow a, b, d is there, they will just be a difference of one between the hash
value of A, B, D and ABC.
A good hash code is one which actually makes sure that all the values which you finally get, the integers,
which you are finally getting, that is a lot spread across.
Okay, they are not concentrated.
Okay.
So I can write that as well.
Not concentrated.
Great.
So let's say B tomorrow something is getting us a ten.
Then the next thing I'm getting 20, then 30.
I take the modulo let's say by 11 I am getting everywhere the same value.
That's a problem, right?
Sorry, I'm taking the modular, let's say by ten.
So I want them.
They should be a lot spread out.
Okay, great.
Now one more thing which we do is we try to add okay them as a power of five number.
So I will tell why exactly that is done.
A lot of research has actually been done in this.
So I have read a lot about uh different hash codes and everything.
What happened is that prime number have a very good distribution.
Prime number have very good distribution.
And we try to be little far off from power of 2 or 10.
The reason is that they are very common in nature okay.
So we try to be pretty far off from them.
Prime number have good distribution overall.
So what we use here is again this is just some things which have been researched upon by scientists
okay.
And we then make sure that we are able to see that.
So the whole idea is the same that you will be getting some, uh, A key from a key will be getting
some integer via the hash code.
Write a hash function.
So what happens here is.
Pay attention everyone.
Let's say my 321.
Okay.
This I can write as three into ten to the power.
3 or 10 to the power.
Two plus two into ten to the power.
One plus one into ten to the power zero.
Now, what I do is I take this as a prime number instead.
They are just written as powers.
Right?
So tomorrow what can I do is if I'm getting ABC, I can just say that, eh, whatever.
I'm getting the value of a that into some p cube plus B that again into some p square.
Something like this I can do.
The idea is that because prime numbers gives good distribution, we will make sure of two things.
They will be a lot spread across.
So I will get two benefits.
First is spread across.
Second, they will be actually having very high values like it will not that they are concentrated somewhere.
Okay, so along with spreading, it is like for example in the above 190, 90, 90, it is around 272,
let's say somewhere in the space of 1000, right.
That is where my all the keys will all the integer values of keys will lie.
Okay.
Because I know that A is 97, B is 98, C is 99.
For all the three letter words, they will be very close to each other.
Here I have spread them across okay and very large values.
I am getting very large values.
So which is again not an issue because I am going to take a modulo very large values.
Great.
Now the next question is tomorrow it might happen that I am asking you to store.
As I said, keys can be anything right?
Provided they are not mutable like they cannot change.
List cannot be a key.
Tomorrow if I, let's say, ask you to store a node.
Okay, so we created nodes for our linked list and for our trees.
What if you have to store a node.
What if a node has to be stored.
As a key.
Then again see the idea is that we can get.
Let's say we are using the overall what we say the address or the reference for this particular thing.
Okay.
So we can store it as key.
Maybe you can use even the current time and get some hash code.
Okay.
But that will be a problem because again we will not be able to reproduce that.
So again we cannot use that.
The idea is that they should be always same and unique.
Two keys cannot have the different keys cannot have the same hash code.
Your hash code should not change with time.
So if I'm asking to insert with the hash code or insert a particular key tomorrow to get, you will
need the same hash code, right?
So maybe you can use the address because that's going to be the same for an element.
Maybe we can check for some values that okay what data is it storing.
Okay.
Let me make a hash code based on that.
Okay.
So yeah all that thing can be done uh, to make sure that you are able to overall find your hash code.
So that is the basic discussion about hash code where through which we can convert our key into my integer.
So key into.
We have the hash code here.
We will get this as an integer.
And then we will just save it into a bucket array.
Right.
So that's the whole idea everyone I hope the discussion is clear that how will we be able to do it using.
Uh, using an array or a list.
Right.
Great.
Now again, many of you might have one more question, or you might be thinking one thing.
Let's say tomorrow.
I ask you that.
Hey, I have these ten nodes, okay?
Ten nodes.
Ten words, ten numbers.
Okay.
Which I want to store in a bucket array of size five.
So let's say I have this bucket array of size five.
And I'm asking you to store say ten numbers in this.
Like I'm asking you to store ten numbers here.
Then what we will do okay.
Let me write numbers nicely.
It's a little bit dust here.
Should be fine numbers.
Well the problem here is that yes, there will be some collision.
Okay.
So let's say you written a very good hash code.
Okay.
What exactly it is doing is it is giving you say 100025.
Okay.
And then here second.
Yeah we are getting 1000
Five and we can maybe change it as well.
Okay, so there are a lot far off.
There are a lot far off.
Let's say you just take the hash code as a last digit.
Okay.
Or maybe taking percentage by some something.
Let's say by ten you are taking the percentage.
The modulo operation.
Okay.
Even if you take it by five, which is the size, you will get the both of them as zero.
Okay.
So let us take this percentage five only.
We will get both of them as zero.
Now the problem arises that how exactly are we going to handle this case?
This is something which is known as collision.
Okay.
And for this we have some ways we handle the collision.
The problem is that two things.
First, if you want to store many elements or more elements than the bucket array size, then of course
you will have collision.
That's the first thing.
Second is, even if that is not the case, let's say even if you are taking a five sized array and you
get the same hash code, and so you get the same hash value after doing the calculating the hash code
and compressing them.
Okay.
Then what are the different things which we can do?
So that's the basic idea because that is something which is known as collision okay.
And that is something which we are going to now see in the next video.
Everyone okay.
So I can write above is known as.
Collision handling.
And don't worry I will be teaching writing the code helping you visualize everything.
Okay, so I'm making sure that each and every one of you just get this, figure out that how they are
implemented.
Because I see many students struggling with the overall implementation of hash maps.
Okay, so great everyone.
We will continue this discussion in the next video now, but I'm pretty sure that you would have got
a very good idea that why and how things are happening.
The start of the things in a hash map.
Okay, great.
So let's meet in the next video.