Hi, everyone.
So in today's lecture, we are going to study this topic, Hashmat.
The name of Hashmat is basically stable, 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.
So first, let us discuss hash map.
So hash map are basically very, very useful for us.
Whenever you will be working on a website, wherever 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 calling.
So first of all, let us discuss why do we need the need of the.
So for understanding the need, let us first take the help of caution, so given a string, so you are
provided with the string and what we have to do, you have to find out the highest auguring character
in the string.
So by the highest auguring character, what we have to do, we have to find the correct in the string,
which has the maximum frequency, the character which is appearing maximum number of times.
So how can resolve this question?
So the first way of solving this question is basically brute force.
So what do we do?
Every character and find the kind of this character.
Now, the second character, find the character of this character.
So basically picking every character and finding the account of that character so that all the time,
complexity, so time, complexity will be square, picking every character and then finding out its
count.
And finally, you will take.
We will find out the maximum count and you will return the corresponding character simple.
Now, some people can say we can use sorting.
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
there is will come together.
All the bees will come together, all the seeds will come together and so on.
So basically, let's say this is my string, so it will happen.
All that is will come together.
I will find out how many pieces are together.
Then all the bees will come together.
I will find out how many bees are there.
I will find out how many pieces are 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 character
corresponding to the maximum count, simple.
Now, what do the time complexities?
So first we will start the.
So we will start this thing.
So the time complexity will be in Logan and then for then for finding out the character.
We will iterate over this string.
So this will be an order of big, often so long and.
So finally it will be in Logan.
Now, I want to solve this question in one time, big golf or in.
So how can we solve this question in big oftentime?
So what we can do, we can take we can apply our heck.
So let's discuss what we can apply.
So how many characters are present, so there are total 256 characters, if you will see the keyboard,
they are a total of 256 different characters that you have now.
You will iterate over the string.
So this is your string.
What I will do, since there are 256 different character, I will make a character, I will make an.
So I will construct Tonetti and the size of the array will be 256.
The size of the area will be 256 and I will initialize this individual's.
OK, I will construct a narrative and I will initialize the area with zeroes simple.
Now, if you are creating all the if you encounter a character, so what is the asset value to ascribe
values?
Basically 97.
So what you will do, you will go to the 97 index.
You will go to the dentist index and you will put one here.
Similarly, contract can be.
It's about values and ideals.
What he will do, you will go to 98 character 98 index and they will put one here and so on.
So basically you are at your frequency.
So this is our frequency at a lower frequency array will be ready.
Let me take an example.
Also, consider the string eBay and let it be.
So this is my string.
So it will do.
We will construct an array of size 256 because they are total 256 different characters.
Now we will attach to the string.
So e so what we do, we will go to 97 to index.
I will put one B so I will go to ninety eight index.
I will put one then again.
So what I will do I will make it to again.
B I will make it two.
Then I have again.
So I will make it three.
So finally at 9:00, the seventh location, you have three and the 90 year location, you have to then
for finding out the maximum character, what you will you will iterate over this.
256 to Cesari, you will see three is basically good then two, so I went to the index, what I will
do, I restore the index, I will take a variable maximum.
This maximum will contain what is the maximum number of trees, the maximum and I was told the corresponding
the index.
So I will told 97 and I know corresponding to 97 the correct.
So that's how I will be able to find out the correctly.
So what would be the time complexity.
So first I have to iterate over this string to prepare this to have precise accessory.
Then I will iterate over this frequency to have the successor and I will be able to find my answer.
So first, trading on this.
This is NP and then I am Armatrading on this, so and plus 256.
So this is basically big often.
So that's how I will be able to solve this question in big often.
OK, so what, you buy gold, so my gold will look something like this.
First of all, I will create an area of size 256, I will initialize the area with zeros, then what
I will do so I will iterate all the string so I will use a loop to get rid of the string equals zero
Ellerston string dot size and I placeless.
Then what I will do so inside the loop I will write one simple statement of string of.
So this is basically string.
So aof sfi and I will do placeless.
So what will happen.
This string of it is containing characters and this will be converted into integers with the help of
Disko value and this integer will work as basically index of the area.
OK, so after this loop my frequency, I will be ready.
Then what I have to do, I have to hydrate over this frequency starting from zero less than two C++.
I will find out which index is basically having the maximum count and then I will return the character
corresponding to that index sample.
So our time complexity is basically outdraw and.
This is our draft to discuss what we can say, Constantine.
This is Question Time.
So basically we are able to solve this question big often.
Simple, why we are able to solve the situation, we are able to solve this question because there are
fixed number of characters available to us, they are only two of the six different characters available
to us so we can create a fix to society if the different number of characters, if the different number
of characters available to us are basically infinite, then obviously I cannot create infinite sized
Eddie, so I will not be able to use this approach.
This approach I'm calling this approach as heck, we are able to use this approach because there are
only two of the six different characters that tried this approach will work.
Now, let us discuss the second question now, given a string.
You will be provided with a string and what you have to do this time, you have to find out the highest
orcharding word.
I'm not talking about the character.
I'm talking about the word.
You have to find out the highest orcharding word.
Now, there are basically infinite number of words available to us.
I'm not talking about English language, but if you will combine any combination of characters will
basically give me a word.
For example, ABC's The World.
So any combination of character will result in a wide formation.
So basically, we have finite world because there are no limit on the length.
Also, Lent can be anything.
So basically we have infinite number of words.
So that means above approach will not work.
The above hack approach will not work.
You cannot create an infinite sized any.
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 approach, what I'm doing.
So I am writing something like this aof character A.
And then something, something.
So basically this is converted into sars-cov-2 97 and basically 97 is working as index for the 80,
97 is working as an index for the area.
What I want in this problem, I want I can store something like this.
So aof ABC, ABC's The World, I can do something like this.
I want this, but I can only do this.
So why can do this, because it is very easy to convert a character into an integer and that integer
can work as an index, but here ABC cannot be converted into an integer.
So how can we solve this?
How can we achieve this so we can achieve this with the help of Hashmat?
So basically, what passes for Hashmat is very simple, it says.
It is Akiva loopier, so Aoki is basically value.
This is value.
Now, first, let's talk about Eddie, so inadequate is a situation so you can create an array of integers
so value can be integer, you can create an array of double so valuable variable, you can create an
array of characters.
So the value will be corrected.
But in case of Eddie, that guy is always engaged.
In case of Eddie, the Keys is always in danger and that can be done.
We call it index.
So this is a situation in case of error is always an integer.
And Hashmat, what assurances have Schmitz's keys can be anything, it can be, it can be, it can be
corrected.
It can be strong.
It can be anything.
So basically, Hashmat Schmitz's.
Hashmat Schmitz's.
Your key can be anything and your value can be anything.
So these two can be anything.
It can be in the battlefield, anything.
I am repeating myself.
So what is the limitation with that is what is the problem with that is so the problem with that is,
is basically this guy this guy is can only be in BIJA and well, you can be anything.
It can be integer, flawed double.
And so value can be anything, but gey will always be integer.
So this is the limitation of error.
This is the limitations of adding that GUI will only be integer.
And what the map says, maps is your key can be anything, your key can be anything.
So basically map, but will also map is basically it will it is a given loopier.
So MAP is basically a given loopier, 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 map aof.
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 strength 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 or insert into map.
This is key.
So the Keys, ABC and the values run.
So insert the key loopier inside the map.
So we are using insert function.
OK, so I hope you understood the logic.
So finally in a guy will only be integer and value can be anything, value can be anything in Hashmat
G 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 solve our problem.
OK, so this was a limitation that will always be in danger for the day, but this guy can be anything,
so you can definitely write like this aof ABC Abkhasia string is basically, let's say 25.
You can do anything Ghinwa.
You can be anything.
Now let's see what other functions that we want in Hashmat.
So functions that we want Hashmat should have.
So first, it should have been function.
Insert functions in the insert function, I will give the key and I will give the value.
So this is a key value bill, so insert key and value.
So insert function should be there.
Now, the second function that I want, it should be get value, I will give you a 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 they're targeting.
Why do we want we want there should be a function, the Liedtke.
I will give you the key and you will delete that key.
Now one thing, just like an.
So in the indexes, basically what we call Leskie.
So indexes are basically unique.
All indexes, all guys are unique in Hashmat.
Also, keys will be unique.
So this will be unique.
OK, so unique is.
You cannot have like this, so if you had ABC is to and if you are doing a of ABC again entry, so what
will happen?
This cannot exist together.
So this will be unique.
This has to be unique.
OK, 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 one corresponding to ABC and in the next line,
if you will do something like this, aof ABC equals to insert the value to corresponding to the given.
So what will happen to insert this line, to insert this given loopier.
This value will be this given loopier will be removed, it will be removed.
OK, so as soon as you write this line, as soon as you write this line, it will remove the old key
value pair.
OK, so key has to be unique, just like in adding the indexes are unique in.
These are unique.
Simple.
Now, let's see, how can we implement map?
So how can we implement Hashmat, so let us discuss the first way to implement Hashmat.
So the first rule is basically we will take the help of legalist.
So this is a very simple list.
So these are notes of the long list and how long list can help us.
So basically, if you'll remember in the long 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 we will do, we will store two things.
We will store key value pair, we will Stokey and we will store the corresponding value.
We will talk in the corresponding value.
So how can we insert discuss the insert function?
You have to insert a key value pair.
So what you can do, you can insert the key value at different simple.
Now if you want to delete a given key, so delete.
The given key, so how can it lead to a given so what do you have to do?
You will, I dread over the long list.
And then you will and then you will match the given key with the key present at the node, so if they
are safe, that means you have to delete this one.
So I will delete like this.
OK, so we are able to delete what is our time complexity.
So first you have to get rid of the list to find the node that we have to delete.
And basically we will match the key, which we have to delete.
So.
Since we have to all the time, complexity will be big often now what you have to do, 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, you have to do you will trade over the long list and you will compare the lower key value
with the given key value if they assume you are able to find it.
So again, the time complexity in case of search is also big often.
Now, what is the time, complexity of inside function, so I told you the insert function, what we
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 you have to do, you will migrate over the long 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 Keith has to be unique.
He 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 long 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 the value.
So basically you will insert the value.
OK, so again, this insert function is also big, often because you have to add to the list to ensure
that these are unique.
If you will use list to implement hash map, then insert, delete and search, all three operations
are big often and this is very, very bad.
We definitely want something better.
Big often is really, really bad.
Now, let's see the second approach for implementing the Hashmat.
Now, the second approach for implementing the hash map is basically balanced, a balanced binary search
tree.
So for balance, the height is basically always low often, and it's the total number of nodes.
So first starters discuss inside function.
So what is I think we know for inserting a node in about.
The time complexity is basically proportional to the height and height is basically low often, so insert
function will take longer time.
OK, so the balance, 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 about basically
less than the we can use the ordering like lexicographical, we can compare the strings we can order
with the help of like lexicographical ordering.
So this character is basically less than this or a bit 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 key value added scores at the right position.
We can push the key value inside the body at its right position.
So and we know inserting an ordinary BSD log of an.
So deletion in balance again, so deletion is proportional to height and height is basically logoff.
And similarly, if you want to search for a node so in best you can, searching is also proportional
to height.
So this is also lower than ideally will go left or ideally will go right.
So if you lose the balance to bisdee for implementing the Hashmat insert, delete and search, all three
operations are taking longer time.
OK, so this is better than Linklaters implementation.
So actually, this hash map, so this kind of balanced budget is already implemented in C++, so this
is inbuilt.
We already have this implemented in C++ and we will use we will definitely use it.
Now, there is one more way.
There is a third way 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 function Birdwood function
and the search function, all three operations are basically big offline.
Yes, kynaston time we can insert in question time we can believe in constant time.
Began searching Question Time 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 video, we will see the world map and we will definitely discuss the hash table.
But later in the lessons, I will meet you in the next one by.