Hello all and welcome back.
So in this video let us now continue our discussion on hash maps.
And before learning the how, let us learn the why of hash maps.
Okay, so in this video I'm going to tell you that why exactly hashing is required.
Okay great.
So let us try to understand this with an example.
Let's say you are given a string.
So we are given a particular string.
Let us say the string is something like this.
Hash maps.
Are pretty.
Awesome okay.
And the question which you have to answer is that how many.
Characters.
Of each type.
Or let me make it easy, let us make it in this way.
So which is the.
Highest occurring.
Alphabet.
Okay.
So simple question.
We want to just tell that which overall character is coming.
Which alphabet is the highest occurring.
Right everyone.
So again we can just see that okay.
How many times A is coming.
How many times B is coming.
Just like that.
We can do it and we can let's say tomorrow taking capitals in that as well.
And we even try to introduce the symbols.
Right now there are multiple ways of doing this particular particular thing.
The first can be the very first can be which anyone can think is let us sort it okay.
So let us sort the string We will get each and every, let's say all the A's will come in the starting.
So we have seen how lexicographical sorting happens, right?
Let us sort this and count the number of occurrences of character which are consecutive.
If all A's are in the starting, we will count them, then all B's, then all C's.
It's going to take you o of n log n right.
Because we know the best overall sorting algorithm which is merge sort.
We understood the same thing in our time complexity lecture that it performs the sorting in n log n
time.
Right.
So that's the very first approach.
Okay.
Here we will be getting this sorted.
And what we are going to do at each step.
We will just see that okay.
What exactly or how exactly characters are happening.
Let's say A is here.
Let's say B is here.
Let's say C is here.
Okay.
There is one more very smart way of doing this.
Okay.
That is, we are going to let's say create a count.
Array or list.
Right.
And it will be it will be having 26 as a size.
So what I am saying I will just make it like this.
So zero in all 26 right.
Now what I will do, I will go to each and every of my element, let's say here, if I go to a I will
increase this count the list which I am creating.
I will increase the position of a by one.
Now what can be the position of a?
What can I do is.
So I have an idea that A is the first character, right?
B is the second character.
And like this Z is the 26 character.
There is one more thing which is very, very important to understand.
list can just have integer as key.
Integer as keys.
Right.
So what effectively list?
You can write that.
Hey, tell me L of zero.
So tomorrow you can write this code as count of zero is going to give you how many A's are there.
Okay.
So we will subtract minus one from as well to fit it into a list.
So if a is one I will say that hey go to the position zero.
But you cannot say that.
Hey give me the count of let's say a this is wrong.
This thing is wrong because list is not supporting any indexes or the keys in a non integer manner,
right?
So a very smart way of doing this particular question is that you can just change this particular program
in a way that we will be storing the each alphabet as its position.
Okay.
Now if tomorrow, the same problem is let's say change where I have to now tell for symbols or even
have capital letters, I know that they will be finite number.
Right?
So normally we say that 256 characters are there.
Okay.
So I will make this count list or array of 256 okay.
So all that can be easily done.
Now let us change the question.
Now the question becomes how many words are there.
Are there okay.
How many words are there in a sentence.
In the sentence okay.
And it can be a long sentence.
It can be the full website full Wikipedia article.
Now you have to tell which is the highest occurring word okay.
So instead of not how many words are highest occurring word.
So this time I am interested in knowing the highest occurring word, not the character.
The whole logic which I developed in the past is now kind of useless to me, right?
Because what will happen?
You cannot define these keys.
So here the benefit was that I was changing these into some integer keys, and I knew that they are
finite.
Right.
So one more benefit was there, which was it was finite.
Okay everyone using this approach I was able to get an o n solution.
Now the problem here is that words are infinite.
So you can say that hey, let's say a is one okay.
Then let's say you are saying a a is two.
Let's say a bee or something is three.
You are making some this kind of a overall symbol that this is how we are going to transform.
But the problem is that it is not finite and we cannot make infinite keys.
Right?
Like how big of a count, array or list you are going to define?
Infinite combination of letters are possible, so infinite words are possible.
And we cannot have a infinite sized array.
That is a very big problem, right?
Second thing I cannot write like this.
Let's say I cannot say that.
Hey count, give me the overall let's say this.
This is again wrong.
Or let's say if I ask it that how many times in game, then that's a problem.
It is wrong.
Okay, so in array or a list we can only have an integer that is fixed.
We cannot change that.
But my idea or my aim is that we want to In array or list, only integers are allowed.
As keys.
Right.
So only integers are allowed as keys.
But we want to.
Okay.
We want to decide the key itself.
So that tomorrow I can say that.
Hey, for this particular key, let's say count, I am giving you the key and I am giving you the value.
So that's the basic idea.
Both I want to control both control both.
Okay everyone.
So that's the very basic idea.
And this is where hash maps now comes in.
So I hope with this you are able to understand that how?
What exactly is the problem, right?
What exactly is the problem which I am able to solve using hash maps?
So we want to make sure that we can pass any key okay.
So it can be any format.
It is not that now they are just limited to integers or anything right.
In list in Python of course a list is homogeneous.
So multiple things are allowed.
We can have an integer.
We can have a string.
But in other languages even the array, the basic array is also having a overall type.
So they are also a problem arises.
Now I want to make sure that I can control both of them.
That's my basic idea.
Okay everyone.
So that's how I will be trying to do things.
Now let us see that.
What are the different overall options which I have.
So pay attention everyone.
Now very first thing is some operations which I want to do.
So operations.
I of course want to add.
Okay.
I should be able to search or get again.
I should be able to delete any key, add or update I'm taking together.
These are the basic operations where in get value or in get or search I will be just giving the key
in add or update.
I will be giving the key or value and in delete I will be just giving the key again.
Right.
So that is the basic idea or data structure which I'm thinking based on this problem.
It should have these functionalities.
I can add the key and the value okay.
Whatever we need I can get that value which I have stored.
So if I have stored that in comes five times I can get from that, in that it comes five times.
And I can let's say delete delete the same as well.
Okay.
So that is the basic idea everyone.
Now let us see how can we implement them using some data structures we know.
Okay, so let me add a page and see if we can implement them as of the knowledge we have.
So I think the very first which most of you will be thinking is something which is linked list now.
Linked list help us to implement stack linked list.
Linked list help us to implement queue.
How is the structure?
They are just an element one after the another connected to each other.
Right now if you focus what we can do, yes, we can do the same via linked list.
We can have a key and value.
So we were just storing the data.
We can now have two things here key and the value.
And we can have a next variable which is storing the next one.
Right.
Great.
So now let us think about what time is each operation going to take.
So we know that we have to insert or update.
So insertion will take o of n time again.
The reason is that we cannot just insert at head the way we did in stack.
The problem is that if it is already present, let's say the in I have stored already, we have to search
first, right?
We have to make sure that we search first.
And for searching I will have to traverse the whole linked list.
Right.
So this is O of n second.
Again search is also often because I will have to go to each and every element.
And third delete.
It's also going to be o of N.
And these are the basic operation which we will be doing.
Again.
It can have other operation as well, but these are the basic ones which I definitely want.
So each operation is O of N, which though seems fine.
It's not the best solution out there, right?
Something which I would not like to use.
Now let's move forward, everyone.
Okay, so I hope you understood that.
Why insert is also O of N?
Because we have to make sure that it is not present before.
If it is present before then we have to update.
Okay.
So let's now see the second one second, which I'm pretty sure all of you will be thinking is the BST
right we saw in the last module how BST are awesome, a well balanced BST, and let's say we even assume
that height is okay.
Height is.
Or let us assume not on the height that it is balanced.
Okay.
And let's say we are able to come up with some logic, or let's say we are talking about words.
We are able to come up with some logic of sorting our words, saying that, hey, this should go in
the left side because it is smaller.
It can be lexicographical comparison.
Maybe we are comparing their overall references or ID okay, so something we are able to work upon through
which what I am saying is this is my overall tree I will be able to store into this.
Now we know in a perfectly well balanced BST all the all the operations, right?
They can be very well done in a o log n approach, which is a huge improvement over your linked list,
right?
So we already know that how insert.
Delete and search something we have done.
Like we have written these functions from scratch right.
So how all of them can actually be done from in an O log n approach, if you're not aware of that will
highly suggest to see the last module where we have implemented Bsts from scratch.
Well, this actually is a very good approach overall and honestly many languages, right?
They use BST in the backend for implementing a hash table, right?
Or sorry for implementing this kind of a structure where I'm able to get the values, store the values
as well as search the values.
So in C plus plus if I remember right, map I think is something which is using BSD in the backend.
Okay, now comes the third one which we are talking and which is hash table or hash maps.
Hash maps okay.
This is something which we have to study, and it actually will help me to achieve the same thing in
O of one.
We will see exactly what all it is.
But first I want you to make sure that you have a holistic view on what all we know till now.
And can they be used to solve some problem?
I think these were the major contenders for our making a structure like this, which helped me to get
this thing.
So for the word problem, again, we can have a word which is in a linked list, the value as well.
We can have the same thing in a BST for o login, but I am saying that to improve it even further.
Okay, in O of one the constant complexity, we will make sure that we are able to understand the same
on how that is implemented.
Just one thing.
Here we will be following the same approach which we did in BST.
First, we will see if we have some inbuilt way of doing some questions.
Okay.
And then we will try to understand that how exactly that is done.
Okay everyone.
So I'm pretty sure now the idea is clear.
Now you are understood that why we need this kind of a structure, why a normal list or an array won't
do okay.
And other data structures which we have also studied how they are also helping us in maintaining, in
implementing this kind of a structure.
Okay.
How BST is still a legit candidate.
We are using it in many languages, but there is one more awesome approach which is hash maps.
Something which this whole module is going to be about where we will deep dive and implement each function.
Okay, so great everyone.
Now let's meet in the next video.