Hi, everyone.
So as discussed in the last video.
You have a key, so it will pass today has function and the output will basically be an integer, so
this integer will be within the range of the error.
So this is my victory.
So they can be given by the hash function.
Will be present, will be within the range of the area.
So from zero to sides, minus one bucket size minus one.
And we will go to that index and we restored the key value pair.
Now we're discussing the last video that there will be a collision problem, so more than one case wants
to go to this same index.
So, for example, you have two guys, geeky 11 and geeky two.
So this is a hash function.
And basically the hash code is the hash function is giving the same index.
So both Keys wants to go here.
Watkis wants to go here, so how can we solve this problem?
So basically they are actually handling techniques.
So in the collision handling techniques, there are two types of collision handling techniques.
So the first one.
The name of first one is actually close to.
And the second one is actually called open addressing.
So these are coalition handling techniques.
Now, what is the meaning of closed hedging so closed means both the keys will be present at this index
only.
So how can we store two things at one index?
So basically what we will do, we will make a list at this point.
We will construct a list at this point.
So I will store, given its value even then give to key and value we do.
And so on.
Contributory value, gion value, so basically each each bucket will be ahead of a long list.
So each bucket will be a hell of a long list, so both guys giving you two wants to be present at this
index so close to Hastings's, then both present this index only.
So I will construct a link list at this point and I will store given Key Ghilarducci with their corresponding
values.
OK, so this method is actually called separate chinning.
This method is called separate training.
So we have separate genes for each bucket, so we will have separate genes for each bucket.
Similarly, it will also be a long list.
So each bucket will be head of the linked list.
Similarly, this one.
OK, so understood, separate training, they will be separate for each brigade.
Now let's discuss what is open addressing so open it is open.
The thing is, you have a key.
It will pass through a hash function, hash function.
It will give you the index.
Then you go to that index, so suppose this is the index.
Now there are two possibilities.
So first one, this index is basically empty.
There is no key value being stored.
So if it is empty, then you can store your key here.
No issues, but if it is not empty, if already a key exist.
So what you have to do, you have to find the alternate index.
You have to find the alternate index for storing the key value beer.
Now, how to find out that index.
So basically there are many ways for finding out the alternate index.
And now let us discuss those alternate indexes technique.
So what we can do.
So basically, I have a key key.
So it will pass through the hash function and the hash function will give me the index.
So now the eighth attempt for finding the index for Qiqi is actually so hash function, I will give
the keiki as input.
So the original hash function give Geer's input plus F off I.
So what is I i is basically the eighth attempt.
I is actually the academic for finding the index for geekier, so gay is key here.
Now, what is the basic requirement for the function FFI?
So if the value of AI is zero, so that means zero to attempt, so Addazio to attempt the key should
be stored at this index only.
So that means if the value of is it also the basic requirement for the function, FFI is so FFI should
be zero when.
I equals zero.
OK, so this is the basic requirement for the function FFI.
So there are many different techniques, many different opennet techniques based on different FFI.
So you change the value of FFI, you change FFI and you will get a different OpenNet.
The same technique.
So different FFI is different think technique.
Now, one most popular technique is basically called linear probing, so what is linear probing, so
linear probing seems so linear.
Probing, says FFI, is actually a.
So what is the meaning?
What you will do when the value of is zero, you will come here.
Then linnear probings Ortega Jump-Off, one check if it is filled or empty, if it is empty, then store
the key value pair had otherwise move ahead.
Similarly, check it if it is empty or not, if empty.
So the key will appear, otherwise move ahead and so on.
So this is actually linear probing.
FFI is EIU, so if the value of AI is zero, then what will happen to this will become zero.
I will store read the original index.
If the value of AI is one, then FFI will be one if I will be one.
So basically this value will become one.
So I will do plus one.
If the value of AI is to so FFI will become to, then I will do Plaistow, so I will do Plasto basically
I will move ahead.
OK, so what we are doing, we are probing linearly.
We are probing linearly.
So I will check if this index is empty.
Storyteller Adres Motörhead.
Check if this index is empty.
Still, if it isn't pretty -- straight otherwise move ahead.
Simple.
So this is linear probing.
Linear probing.
You can see the harsh cold.
What will be the harsh cold water with the hash function.
So this will be the original index.
So this will give us the original index, this one.
And then you can write a.
OK, so this will be actually a more and and is basically the size of the venue will reach here, then
you have to reach at this starting position.
So this is.
This is linear probing, take a jump off when, when, when, when, when they go, jump off one ahead.
OK, another second is basically quadratic blobbing.
Now, in the quality, probing what we will do.
So this time, FFI is actually eisgruber, FFI is actually isco.
So if I'm talking about this veiled attempt, so it will be zero if I'm talking about the first attempt.
So it will be fun if I'm talking about the second attempt for finding the next.
So it will become four.
If the value of five three third attempt, it will become nine.
So what we will do.
So suppose.
This is the original index, so suppose the original index, so if this is empty, so the value of is
zero, I restored it here.
Now, if it is not empty, what do I take a dump of one or take a jumper off one?
If it is empty, then storyteller advice.
Take a jump off for me.
So I will take a jumper for.
No, if it is empty straight here, otherwise take a jump of nine, so I will take a jump of nine.
And check if it is empty, then store it here, otherwise take a dump off so it will afford to take
a dump of 16.
So what will be our answer?
So it will be able to function.
Our function will be the original hash function.
Plus, I squared Mordaunt.
So if you will reach ahead out of so if you will reach the out of index, you will.
Richard Defroster, next.
OK, so that's why I square more than so at the eight attempts over the value of a zero, this will
become zero if the value of.
So this will become even if the value of Ista, this will become four.
And so on.
So I'm repeating myself linear and quadratic probing.
So linear, linear probing, says Paga Jump-Off one.
So basically the new index.
So new index will be the original index.
I will give kids input and.
I Ma'aden and the value of a meal starts from zero, simple, it will go zero, then one, then two
and so on.
So basically the probing is very, very simple.
Initially, the value of zero, so you will go to the original.
So this will become zero, the standard becomes zero.
So go to the original index, you will go to the original index.
Now, if it is empty, you can store.
Otherwise you will move ahead.
No check.
I have to take a jump of one one.
OK, plus it will wait.
It will be plus one, then it'll be plus two then plus three.
So then plus two then plus three.
So I am taking a jump of one at a time and this more than is due to because then you will reach at the
last index and then you will take a jump so that you can reach the first index and the quietest provinces
do not take a jump of one one take a jump in Times of Square.
So this will be the new index will be the original index and this will be a square more than.
So again, the value of I will start from zero and it will keep going on until you are able to find
an index.
Very constructive loopier.
Simple.
So again, what will happen?
So suppose this is your original index, so the value of five will be zero if it is empty storyteller
here, otherwise take a jump of one.
If it is empty, store it here.
Otherwise take a jump of what you have to do.
So this is this is plus zero.
Then it will be pleasant, then it will be plus four, then it will be plus nine.
So plus four then plus nine then plus 16 and so on.
Now which one is better.
Quality probing.
Probably linear probing.
So quality probing is better.
Why.
It is better because if we will see the problem with the linear probing.
Is that so suppose you have a.
So suppose you have a very popular index, so this is let's call it local popular index.
So somehow your household has a problem, your household is a problem.
You had a school has a problem and every kid wants to reach every kid wants to be present at this index.
Every kid wants to be present at this index.
So this is local popular index.
Then with the help of linear probing, you are taking a jump of one again.
You will take a jump of one.
So you are taking a jump often.
So they will be like many kids will be present here and rest.
All the areas will be empty, rest all at will become empty, and many kids will be present only at
a very small area.
But if you lose quality blobbing, it will solve this problem.
So this is basically clustering what is happening here.
Clustering is happening here.
So this is a local popular index, if you will, apply linear probing.
So many kids will be present in the nearby area of local popular index.
So they will be clustering.
But if you lose quality probing what it will do.
So this this will solve the problem of clustering.
So this is local popular index quiting dropping will say Tigger's improvement.
So if this is filled, then take a jump-off for if this is filled, then take a Jump-Off nine.
So with the help of.
So with the help of quite probing question will not be there, so if this is a local pope, it is a
local popular index, every wants to be here.
So with the help of quite probing, we will obtain a good distribution.
We will obtain a good distribution ghys these will be spread out all over the area, not just around
some particular area.
OK, so quietly probing is better.
Now, the third way is to basically use used to function.
So the third approach is actually called double harshing.
Now, what is the.
So it is very simple.
You find out the index using the hash function when.
Now, if so.
Now, this is the original index where the key wants to, but if.
This index is already occupied.
What do you do, you will apply that hash function, hash function to.
You will abandon his function as function to so probably if you will add the result of these to heart
function, so it will result in less conflict.
It will result in less conflict, so so the idea of the world is actually using off to hedge functions.
So what we will do so this is our original function.
You passed K through the original hash function.
Now, if there's a conflict, if this index is already occupied, what you will do, you you will apply
and hash function.
You will add the result and probably you will get an index, you will get an index which is probably
not occupied.
Basically empty and you can store it there and you can store your loopier there.
So in practice.
Separate chinning.
Performs as well as perform as good as open dressing.
So the performance of the burgeoning and open at the same technique they are releasing, OK, separate
training works as good as open addressing techniques.
So, again, what a separate training.
So separate training is very simple.
So each bucket of the list will actually be each bucket of the array will actually be a long list.
OK, each bucket of the will actually be elementalist.
So these are ahead of the list, these are head of the list, so from the next video onwards, we will
implement separate training because separate training is very easy to implement.
So bourgeoning is easy to implement from the next video.
We will implement separate training also in the next one by.