Hi, everyone.
So now let's start discussing how we can implement hash map using hash table.
So basically, we want to start two things, I will stalky and I want to store value and in hash map
you can store in Question Time and you can access in Question Time.
So basically in hash, this is the property storing and accessing.
They built out Question Time.
And till now, we started only one data structure with support, storing and accessing in constant time,
and that data structure is actually Eddie.
So that means we have to use it for the implementation of Hashmat because it is the only structure which
can store and accessing Konstantine, the it is very simple Syntex index elfy.
So we will take the help of Eddie and this ad is actually called budgetary.
The name of that is actually called Bucket Eddie.
But I want to do so first approach is very simple, I will convert the key into integer somehow.
So this guy can be anything, so in Hashmat, keys and values can be anything, so he can be integer.
This can be a string, this can be student, so can be anything, so somehow I will convert the key
into an integer.
So what we will do, we will paskey is input.
We have some hash function.
And this hash function will return CNN, Pejar, and what will happen to the Intisar that it will return?
I will go to that BIJA.
And I will store the key here, and when I'm storing the key, I will also store the value, so I will
store the key value here.
For example, let's say the individual came out to be three.
So what I will do, I will go to the next three, so zero one, two, three, so I will go to the next
three and I will store this key here.
And simultaneously, we will also store the value.
So we will store two things.
So this is basically.
We are doing it in Question Time, so this has its function, it will take question time and we will
be able to find out.
Then we will go to that integer and we will start two things inside this budget that again will you
know, how can we access we have to excess in question time.
So for accessing the key, what we will do, we will pass the key.
Through the same hash function, so obviously the hash function will not change, and since that input
the same, the function is same.
So the output will also be the same.
So for the same key, the output will be three.
So what we will do this is at the time of excess, so you will give the key which you want to access,
it will go through the hash function, the output will again be same.
Then you will go to index three and you can see.
So this is the key that this present and this is the value that is present.
So again, this is also constraint time.
Everything is very clear.
Now let us discuss what is a hash function, how it will convert a key to an integer.
So this is the basic logic of so this is the mean idea.
This is the main idea of working of hash map.
You will give the key to a hash function, hash function will give you the integer and this integer
will act as index.
You will go to that index and you want to develop it and for the time of accessing.
So this is at the time of storing.
At the time of accessing, you will again give the same key, it will pass through the same hash function
again, you will get the index.
So this is index, you will go to that index and you can access the key value pair.
So this is the main idea, this is the basic idea of working off hash stable.
So now let us study the hash function, what is a hash function?
So basically hash function comprises of two things.
So our hash function, it comprises of two functions.
So first one is hash called.
And second one is basically compression function.
Has golden compassion function, so basically, let us assume your key is a string.
OK, so this string, it will go through the hash function.
So, in short, I'm writing F hash function and let's say the integer is basically, let's say 20000
593.
So the question is, will you be able to store this string at this index?
So the answer is it depends upon the size of the area.
So if the size of the arrays today, you cannot store this string.
OK, so what Haskell will do, Hedgecoe will return me any integer so it can return any integer, for
example, thousand 593 and then what is the work of compression function?
So compression function will convert this number two thousand five hundred ninety three from zero to
twenty nine because the size of the size of the bucket is 30.
So these are only the valid indexes.
So I hope you understood the working of hash code and compression function, so high school will give
me an integer.
It can give an integer, but we have to make sure that that integer is basically a valid index.
So this has to work as an index and we will convert this number 20000, 523 into a valid index.
And this is the work of decompression function.
So what can be a perfect comparison function, so perfect comparison function is basically percentage
buckets, buckets means area size.
So if the size of the ad is 30, so if you will do percentages 30, then obviously the output will be
between zero to twenty nine.
So the compression function, a perfect compression function, is basically percentage bucket size,
so if you will do percentage today, you will get all the value indexes from zero to 29.
So compression function is done.
We know how compression function works.
Now, the only thing left is basically Hirshfield.
So how we can find out the Haskell.
So now let's discuss the high school.
So basically hash called.
So actually, we can have many high schools, so there will be different different high school for different
different type of kids, so suppose GI is an integer.
Sapolsky is an integer, so what is the backing of high school, so high school?
Erzsi has got it will take as input and it can give an integer as output.
Now this one.
When the keys are indigent, so let's say the value is 50 50, so what can we take so Hedgecoe can be
identity function?
So we will return 50 only, OK, we can take hash as identity function so it can return 50.
Now, let's see if the keys a string if the keys are string.
So let's take an example.
So let's say ABC.
Now I have to convert ABC, so this ABC will pass through the high school, I have to convert ABC into
an integer.
OK, so what can I do so I can hard code so I can return?
When you give me anything, I will always return when you give me the if my high school student an integer,
I am returning when you give me an input.
So obviously this is very, very bad.
What you're trying to say, given energy, I will push the key value pair, I will insert the key will
appear at the next one.
And obviously this is like very, very bad.
So what Haskell, can we use so we can use Hoshko like some of ASCII values?
So if you will use high school like this, some of our school values.
And if you will pass string ABC, so what will be our integer so your data will be the asset value of
a 97.
Similarly, that's a value of B and similarly the value of C, so you can add all this.
And this will be your engager, then this individual will pass through a compression function, which
we already know, which is percentage of size of the area, and this will work as index.
OK, so this thing is very short.
We do not have to worry about this, we only have to worry about the high school of our tax code.
We should use so if you will use this high school to some of our school values, then the problem is
basically EBC.
Ciba, BSI, the high score for all the permutations of ABC, they will have the same hash code because
if you will add these three numbers, you add these numbers in any manner.
So every permutation of ABC will have the same high called will have the same integer.
OK, they will have the same high school.
So this is the problem with this high school.
OK, so what we can do now, so the third type of Hedgecoe that we can use is basically we can use like
you give me a listing, for example, ABCDE beef and my hash court will be I will some I will take the
sum of only the first three characters.
I will take the sum of only the first three characters, so basically it will be ASCII value of the
ASCII value of it and ask a value of F, so this will return in BIJA.
Now, in this case, it will take the permutations, so let's say DCB, AEF, so we will take the permutation.
The characters are different first, the characters are different.
So that's why we will get a different household.
But this high school is also not very good, white is not very good because because the range is not
huge.
The range is not huge if you are taking only the first three characters into consideration, how many
different characters can be?
So we have only 26 letters during the six alphabets, so we will not get a very huge range.
And what is the property of a good high school?
So the property of a good high school is basically it should give me a good distribution.
So basically, you should give me a huge range of integers, so good high school will give us a huge
range of integers and this is not giving us a huge range of integer.
So this is.
This will work, but this is not good, we can do much better.
So now let's discuss the code, which we use in practice, which is very, very common and very, very
popular.
So that hash called seas, for example, you have a string ABCDE.
So what we'll do, we will treat this ABCDE as it is a no, we will treat ABCDE as a no.
With base.
B, for example, you have an integer 123, so this has a very tough one, this has a rate of 10 and
this has a rate of hundred.
So basically, I can write like this.
So one in 10 to the power to then to intrude into the Power-One and similarly three into 10 to the power.
You similarly, what I will do, I will consider ABCDE as a number with BCB.
So here we have a base of 10.
Now, if you'll trade this number with the BSP, so what with the hash, so I can write basically like.
Value of a multiply.
Due to the power three plus the assembly of B multiply to the power to ask C, multiply, B to the power
one.
Similarly as of the multiply B to the power zero, which is B only.
So this will be my integer.
So if I will use this hash called.
Then I will get huge range of integers, I will get huge range of integers, because even if you will
change one digit.
So, for example, if you will do a BTC, then what will happen?
So they will come here and C will come here.
So you will get a very different integer.
So using this hash called, we will get huge range of integers and that is preferable.
So that's why this is very, very popular and this is used in practice, so very popular and this is
very much used in practice.
So actually this bee will take B so this one VSP So bees generally taken as a prime number, for example,
29, 31, 37.
So it is proved that on the basis of research it has been proved that if you will take the prime number,
then you will get a good distribution.
If the prime number, then you will get good distribution on the basis of research.
Now, we have discussed if the case in Peter.
You can use identity function.
If the case is a string, then we can use this one number with BSP.
To get huge range of intelligence and B, will be a prime number now, what if your key is a student?
So what if your guy is actually a student?
So you want to use a student as your key so there's no predefined method you can use.
Basically, you have to construct your own high school.
So what you have to do if you want to use a student as your key, then you have to make it on your own
because no one knows what will be the goal of any student.
OK?
No one knows what really has called for a student.
So you have to make your own high school, for example.
What can do?
You pass a student to the high school and you can take the high score, for example, Elbrus.
Now, we know address is actually hexadecimal and you can convert hexadecimal into an integer, OK,
and then that integer will be passed through the completion function and that will give me the index
of the booklet.
OK, so this is one such example.
You can use address as a hash code and then you will convert.
The hexadecimal to address are actually in hexadecimal hexadecimal format and you can convert the hexadecimal
into an integer and then the completion function, then you will get the index.
So what is the mean idea?
So finally, the main idea is you will be provided with the key.
Do you want to start developing?
This will pass through a hash function.
That hash function will comprise of two things hash code and completion function.
So finally, you will get a valid index in the range of the array within the range of the array.
So this index is actually integer.
Then you have a budgetary.
So you have this budgetary.
So after finding out the index, you will go to that index and you will store your key value pair.
So this is the main logic, suppose the size of the budget area is let's say there are 20 cells, basically
the size of the earth is 20, so 20 different cells will be there.
Now, the problem is basically we can have infinite possibilities, strings, so we can have infinite
strings.
Now, the problem with infinite strings is basically so suppose you have a string ABC and the hash function
of ABC is five.
Similarly, you can have one more string def and the hash function of the can also be five.
So basically there are two strings and they're hash function.
Their index is coming out to be five.
So how can you store two strings at one index?
Let us take an example, so suppose the hash school of ABC, I'm talking about high school, so suppose
you have written a very good high school and the hash code came out with one zero five for ABC and for
the F, the hash is came out there that came out to be two zero five.
So you have written a good hash code.
We have a good hash called and it is giving us very different, very huge range of integers.
But when you will apply the compression function to apply compression function Mordente apply a compression
function.
Mordente So the index is coming out wi fi if the index is coming out to be five.
So the problem here is basically we have two guys who want to go to the same index.
I'm repeating myself, I have to quiz ABC and B and they both want to go to the same index.
So this is the same index.
So how can you start to give a loopier at the same index?
So we call this thing as collision.
So this is called collision and what we have to do, we have to do collision handling.
Which of a study in our next video?
I will see you in the next one by.