Hi everyone.
So in today's lecture we are going to study this topic hash map the name of hash map is basically hash
table.
So there is very little difference between these two terms and these two terms are basically used interchangeably.
So we will study.
We will also study the difference between these two them.
So first let us discuss hash map so hash map are basically very very useful for us whenever you will
be working on our website whenever you will be doing web development Android app development.
So a hash map will be used at every place hash map is really really very powerful and it is very very
useful.
You will always use hash map in your day to day life and you will start coding.
So first of all let us discuss why do we need a hash map.
What is the need of the map so for understanding the need.
Let us first take the help of equation.
So given a string so you are provided with the string and what you have to do you have to find out the
highest auctioning connected industries.
So by these high used all getting connected what we have to do we have to find the connecting the string
which has the maximum frequency the connector which is appearing maximum number of times so how can
we solve this question.
So the first way of solving this question is basically brute force.
So what do a little bit every character and find the current of this character.
Now pick the second character find the current of this character.
So basically picking every character and finding the count of that character.
So what do the time complexity.
So time complexity will be inscribed picking every character and then finding out its count.
And finally you will take it will find out the maximum count and you will return the corresponding character.
Simple.
Now some people can say we can use starting yes we can definitely use sorting.
So what will happen if you will use sorting.
So after sorting all the characters all the same characters will come together for example all that
is will come together all the B's will come together all the seats will come together and so on.
So basically let's say this is my string.
So what will happen all the A's will come together.
I will find out how many e's are together then all the B's will come together.
I will find out how many B's are there.
I will find out how many C's out there and so on and what will do we will take a variable maximum and
we will try to find out we will find out the maximum count.
We will compare the count and we will find out the maximum count and then we will return the corrected
corresponding to the maximum count.
Simple.
Now what do the time complexity.
So first we will start.
DNA So we will start the string so that time complexity will be in Logan.
And then for men then for finding out the character we will irate or this string.
So this will be an order often.
Often so and log and lesson.
So finally it will be n Logan.
No I want to solve this question in or in time b golf or in time.
So how can we solve this question and B girlfriend time.
So what we can do.
We can take we can apply our Hec.
So let us discuss what tank we can apply.
So how many characters are present.
So there are total 256 characters if you will see the keyboard.
There are total of 256 different organic best yet you have now you will irate over the string.
So this is you a string whatever looses.
There are two of the six different character.
I will make a character.
I will make an Eddie so I will construct entity and the size of the array will be 256 the size of the
area will be 256 and I will initialize this it with zeros Okay I will construct an area of 256 and I
will initialize the array with zeros.
Simple.
Now if you are trading all the string.
If you encounter a correctly.
So what is that ask value.
S ask I may lose basically 97.
So what you will do you will go to the 97 to index you will go to the 97 index and you will put one
here similarly fair and counter but be.
I ask I will lose nine here.
So what you will do you will go to ninety eight corrected 98 index and you will put one head and so
on.
So basically you are Eddy your frequency array.
So this is our frequency array sound frequency array will be ready.
Let me take an example.
So consider the string A B and let it be.
So this is my string so it will do.
We will construct an array of size 256 because there are total 256 different connectors.
Now we will add data with the string so e.
So what do we look.
We will go to 97 to index.
I will put one B.
So I will go to ninety eight to index.
I will put one then again.
So what I will do I will make it two again B I will make it two then I have again.
So I will make it three so I will make it three.
So finally at ninety seventh location you have three and the ninety eighth location you have to then
for finding out the maximum character what do we look.
You will read all of this 256 to size.
You will see three is basically good then two.
So I restored the index.
What I will do I was told the index I will take a variable maximum this maximum will contain what is
the maximum number so to use the maximum but an average stored the corresponding the index so that I
will store 97 and I know corresponding to 97 the correct posy.
So that's how I will be able to find out correctly.
So what will be the time complexity.
So first I have two I tripped over this string to prepare this to have precise two basic size ready.
Then I will.
I or this frequency two of the six I's that end I will be able to find my answer.
So first I are trading on this.
This is an.
And then I am trading on this.
So and plus 256.
So this is basically big often.
So that's how I will be able to solve this quotient in big often.
Okay so overtly by accord.
So my code will look something like this.
First of all I will create an area of size 256.
I will initialize the edit with zeroes.
Then what I will do so I will.
Trade or the string.
So I will use a loop to white rate or this thing I equals zero i.e. less than string dot size and I
plus plus then what I will do.
So inside the loop I will write one simple statement of string off.
So this is basically String s so eof SFI and I will loop plus plus.
So what will happen.
This a string of I it is containing characters and this will be converted into in pages with the help
of dice game value.
And this integer will work as basically index of the 80.
Okay so after this loop my frequency I will be ready.
Then what I have to do I have to iterate over this frequency array starting from zero.
Let them do six eight plus plus I will find out which index is basically having the maximum count and
then I will return the connector corresponding to that index.
Simple.
So our time complexity is basically our of and this is our draft 256.
Or we can see constant pain this is question time.
So basically we are able to solve this caution and bingo often simple via variable to solve this question
variable to solve this question because there are fixed number of correct best available to us.
There are only 256 different characters available to us so we can create a fix to size any if the different
number of correctness of the different number of correct that's available to us are basically infinite.
Then obviously I cannot create in finite sized Eddie so I will not be able to use this approach this
approach.
I am calling this approach as heck we are able to use this approach because because there are only two
of the six different characters.
That's why this approach will work.
No let us discuss the second question.
No given a string you will be provided with a string and what do you have to do this time you have to
find out the highest all word.
I am not talking about the character I am talking about the word.
You have to find out the highest all getting word now.
There are basically in finite number of words available to us.
I am not talking about English language but if you will combine any combination of characters will basically
give me a word.
For example ABC is a word so any combination of character will result in to avoid information.
So basically we have in finite words because there are no limit on the length.
Also land can be anything.
So basically we have infinite number of words.
So that means above approach will not work in the above.
Heck approach will not work.
You cannot create an infinite sized Eddy so above approach is not going to work so in these type of
problems.
I need a hash map and we will see how the hash map can help us.
So basically in the above heck approach what I am doing so I am writing something like this off correctly
a and then something something.
So basically this is converted into a task I value 97 and basically 97 is working as index for the eddy.
97 is working as an index for the array.
What I want in this problem I want I can store something like this.
So EOF.
ABC.
ABC is a word I can do something like this.
I want this but edit can only do this.
So why Eric can do this because it is very easy to convert a character into an integer and that integer
can book as an index.
But here ABC cannot be converted into I budget.
So how can we solve this.
How can we achieve this so we can achieve this with the help of a hash map.
So basically what hash map sees the hash map is very simple.
It says it is a key value here.
So Aoki is basically value.
This is value now First let us talk about Eddie.
So in that is what is the situation.
So you can create Eddie often do just so value can be in digit.
You can create an Eddie of a double.
So value will be double.
You can create an Eddie of this.
So the value will be connected.
But in case of Eddie the keys are always in danger.
In case of Eddie.
The key is always in danger.
And that can be done.
We call it index.
So this is a situation key in case of and it is always an integer and a hash map.
What punishments is hash Pepsis.
These can be anything.
It can be beaten.
It can be double.
It can be corrected.
It can be string.
It can be anything.
So basically hash maps is
hash maps is your key can be anything and your value can be anything.
So these two can be anything.
It can be in beta double floored.
Anything.
I mean everything myself and so what is the limitation with that is what is the problem with that is.
So the problem with that is is basically this key this key is can only be integer and value can be anything.
It can be integer flawed double exact travel so value can be anything but key will always be in danger.
So this is the limitation of error.
This is the limitations of any that Key will only be integer and what the map says.
Maps is your key can be anything your key can be anything.
So basically in MAP what we lose so map is basically it will.
It is a key value pair so map is basically a key value pair as the name suggests it will map keys to
value.
Simple.
So what we will do we can write something like this with the help of Mark if ABC is one we can write
something like this with the help of map because this is a string this is key.
This is key and key is basically a string and maps is key can be anything.
So with the help of map we will be able to do this or you can also say this is not it is not necessary
to use a square because you can also insert like you can use insert functions so insert into map.
This is key.
So the keys ABC and the values 1 so insert the key value pair inside the map.
So we are using insert function.
Okay.
So I hope you understood the logic.
So finally in every game will only be integer and value can be anything value can be anything in a hash
map key can be anything.
It is not necessary to be an integer.
It can be anything.
And again value can be anything.
So basically hash map solves our problem okay.
So this was the limitation that key will always be in danger for the area but hash Pepsi's key can be
anything.
So you can definitely write like this a of ABC ABC the string is basically let's say 25.
You can do anything.
Can we look and see anything.
Now let's see.
But at the functions that we want in hash map so functions that we want hash map should have.
So first.
It should have insert function insert function.
So in the insert function I will give the key and I will give the value.
So this is the key value here.
So Insert key and value.
So insert function should be the.
Now the second function that I want it should be get value.
I will give you key and you give me the corresponding value.
So this is the second function.
I will give you the key and tell me what is the value corresponding to that key now that targeting my
do we want we want.
This should be a function delete key I will give you the key and you will delete that key.
Now one thing just like an eddy.
So in Eddy the index is basically what we call ASCII so indexes are basically unique all indexes all
keys are unique in hash map also keys will be unique so keys will be unique.
OK so a unique keys you cannot have like this so if your ABC is 2 and if you are doing a of ABC again
a..
So what will happen.
This cannot exist together.
So keys will be unique Keys has to be unique.
Okay so for example if you use the insert function and you did something like this if ABC is let's say
when you are inserting so you are inserting the value when corresponding to key ABC and in the next
line if you will do something like this if ABC equals to insert the value to corresponding to the given
key.
So what will happen to insert this line to insert this key way loop here.
This value will be this give a loop it will be removed it will be removed.
Okay.
So as soon as you write this line as soon as you write this line it will remove the all the key value
beer.
OK so key has to be unique just like in Eddy the index is not unique in a hash map.
Keys are unique.
Simple.
Now let's say how can we implement hash map.
So how can we implement hash map so let's discuss the first way to implement hash map so the first way
is basically we will take the help off linked list.
So this is a very simple linked list so these are nodes of dealing list and how linked list can help
us.
So basically if you remember in the linked list we used to store only one thing.
Basically the data and the next pointer.
So instead of storing one thing that is the data what do we look we will store two things.
We will store key value here.
We will stop key and we will store the corresponding value really restore key and the corresponding
value.
So how can we insert that does this the insert function you have to insert the key way loop here.
So what you can do you can insert the key way loop here at different simple.
Now if you want to delete a given key so delete the given key so how can it lead the given keys so what
do you have to do.
You will hydrate over the link list and then you will.
And then you will match the given key with the key present at the node.
So if they are the same.
That means you have to delete this one.
So I will delete like this.
Okay so we are able to delete what is our time complexity.
So first we have to iterate over the linked list to find the node that we have to delete.
And basically we will match the key which gives you have to delete so since we have to either know the
linked list.
So time complexity will be big often.
Now what you have to do is you have to search.
Let's say you want to search given key check whether the given key is basically present inside the map
or not.
So again they have to do you will trade over the linked list and you will compare the node key value
with the given key value.
If they assume you are able to find it.
So again that time complexity in case of search is also big off in now what is that time complexity
of insert function.
So I told you the insert function murder can do we can insert at different so you might think that our
time complexity is big often but this is wrong time complexity is basically big off and because first
what we have to do you will address it or the linked list and you will check whether the key exists
or not whether the key already exists in the linked list or not because I told you that Keys has to
be unique key has to be unique.
So for example if the given key so I told you to insert a given key so first you will check whether
this given key is already present inside the linked list or not.
So basically you will have to iterate over the linked list and then you will check yes the given key
is already present.
So basically you will update its value.
You will update its values or insert function will take two things key and devalue.
So basically you will insert the value okay.
So again this insert function is also be golfing because you have to identify the linked list to ensure
that keys are unique if you will use linked list to implement hash map then insert delete and such.
All three operations are big often and this is very very bad.
We definitely want something better big orphan is really really bad.
Now let's see the second approach for implementing the hash map.
Now the second approach for implementing the hash it hash map is basically balanced BSG balanced binary
search tree so for balanced BSG the height is basically always low often and is the total number of
nodes.
So Foster does discuss insert function.
So it is our thing we know for inserting a node in a BSD the time complexity is basically proportional
to the height and height is basically low often so insert function will take logging time.
Okay so the unbalanced BSD there will be some ordering of keys so how can we order keys.
For example you want to insert the strings so I can say ABC basically less than the we can use the ordering
like like so graphically we can compare the strings we can order with the help of like looks or graphical
ordering so this character is basically less than D or a B is less than the.
So somehow there will always be ordering exist so ordering will always exist somehow so we can use ordering
and we will put the corresponding give a loop here added squatters.
Edit the right position we can push the key value pair inside the BSG adults right equation so and we
know inserting an ordinary BSD log often so deletion in balance BSG again so deletion is proportional
to height and height is basically log often.
Similarly if you want to search for a node so in BSD you can.
Searching is also proportional to height.
So this is also low often either you will go left or ideally it will go right so if you will use the
balanced BSD for implementing the hash map insert delete and search all three operations are taking
log often.
Okay so this is better than linked list implementation so actually this hash map.
So this kind of balanced BSD already implemented in C++.
So this is in bold.
We already have this implemented in C++ and we will use.
We will definitely use it.
Now there is one more TV.
There is Tavi and it is called with the help of hash tables we can implement hash map with the help
of hash table.
So in this case the insert function that the lit function better delete function and the search function.
All three operations are basically big golf one.
Yes constant time we get in the starting question time.
We can deleting constant Constantine because searching clustering came with the help of hash tables
so we will see we will study it thoroughly.
But now first let us discuss in the next video how can we use this inbuilt hash map.
So in the next we do we will see the inbuilt hash map and we will definitely discuss the hash table
but later in the lessons I will meet you in the next one.
My.