Nice explanation, I really liked the way you explained. Just one thing which can be added... please demonstrate search and delete attempt for non-existing key only... for example attempt to search key=8 in linear probing and show where to stop searching in both cases (1-all keys are occupied, 2 hash table has some empty slots)
At 5:44 shouldn't it be h1(18)=h1(((18%11)+1)%11) and not h1((18+1)%11), as the formula is (Hash(x)+i)%size. The formula applied here worked as we are taking mod here but had the key been a string or had we used some other operation other than mod the probe would not be correct.
Hey Rahul, The point you are making is correct, we have skipped calculations as (X%t + i) % t = (X+i) % t for i >= 0. And, yes, Hash(X) can be any suitable function depending on the type of keys that we are dealing with.
I think it is not good to simplify this step which makes the listeners confused. Hope you can modify it later. Probably, calculating Hash(key) first, then do (Hash(key) + i) % size. :-)
First of All thanks for the nice video. Linear & Quadratic Probing calculations are very clear. I am not clear on the Double hashing formulae application.
In case of (62 mod 11), the result is 7 which is already occupied. So, we go for ((62 + 1*1) mod 11) which gives us 8, again occupied. Next we go for ((62 + 2*2) mod 11) which gives us (66 mod 11) which is 0. So, we insert at 0th index. Hope this solves your confusion. :)
@@GeeksforGeeksVideos In case of (62 mod 11), the result is 7 which is already occupied. So, we go for ((7+ 1*1) mod 11) which gives us 3. we should use h0 index for computing h1(x) we don't use the number itself. The formula is correct Hash(key) + i) % size but your example problem is wrong
The linear probing distributes data in the hash table more uniformly, which increases the cache hit probability. For eg. in video 7, 18 and 62 were placed uniformly one after another using linear probing, but in quadratic probing 62 was placed very randomly way above at the first slot. This randomness decreases the cache hit probability. If you don't know about the cache hit probability, you can find about it on the internet.
for quadratic probing the equation you written is h(x)=(hash(x)+i^2)%hash table size but in the explanation you written 1^1 and 2^2 please clarify my doubt
I am copy-pasting my reply from above but the answer is the same. The linear probing distributes data in the hash table more uniformly, which increases the cache hit probability. For eg. in video 7, 18 and 62 were placed uniformly one after another using linear probing, but in quadratic probing 62 was placed very randomly way above at the first slot. This randomness decreases the cache hit probability. If you don't know about the cache hit probability, you can find about it on the internet.
in open hashing you explained how we allot same index value by linked list,but i want to know that at searching time,how will itgive us exact key @t ,we will simply pass our key to get the value during searching,and that hash function will convert it into a index which having lots of value in form of linked list because of collision,then how will it know the particular value of our key? how will it know there that which value of same index is value of the our key? please do answer
hello Sir, it was pretty tough for me to understand the complexity part towards the end of the video could be please explain it in some more details thank you!
Think of it this way. n/m gives you probability of finding an occupied slot in the table. So 1-(n/m) gives you the probability of finding an empty slot in the table. Now both insert, find or delete operation require searching for an empty slot at the end. So, how frequently, on average, is our empty slot occuring? Answer is 1-n/m. Now this is the frequency. For calculating time, you need to do the reciprocal of the frequency. Hence that gives the result.
excellent series, thank you. But i have 1 question if i have 10 elements to be placed in 10 slots, complexity is infinite? Can you elaborate on the ending part where alpha=n/m?
Think of it this way. n/m gives you probability of finding an occupied slot in the table. So 1-(n/m) gives you the probability of finding an empty slot in the table. Now both insert, find or delete operation require searching for an empty slot at the end. So, how frequently, on average, is our empty slot occuring? Answer is 1-n/m. Now this is the frequency. For calculating time, you need to do the reciprocal of the frequency. Hence that gives the result.
I'm a little bit confused...do I have to calculate the modulus two times i.e. First - while calculating the Hash(X) and then secondly when the '%' is encountered. Is that correct?
Its good video. the concepts were easily understud ,....but I have one issue that ,there is requirement of English subscription..as we can't see the images/screen completely...
What do you mean English subscription? Do you mean subtitles? We have subtitles with this video. You can turn subtitles on by clicking on the CC (Closed Captions) button. It's on the left of Settings button at the bottom right corner. What images/screen can you not see completely? Could you please share the timestamp where you are facing these issues?
Hi :) How \ Do we need to know which h1\h2 etx we used? how do we keep track or this detail doesnt matter once we place the value in its place? Thanks !
No, we do not need to know which h1/h2/h3 etc we used. This detail does not matter. Once we put it there, we can always find it back using the same logic. When we are searching, we keep on probing until the value we are searching matches the value that is stored. If the value is in the table, we will surely find it. If it's not in the table, we will end up reaching an empty slot.
All your videos are good when we watch them in "1.5x speed" :-)
im used to 2x
Yes
haha couldn't agree more
I'm using 1.25 because I can barelly hear his voice :s
Simple, To the point covering all the important topics ..Kudos to gfg!
Nice explanation,
I really liked the way you explained.
Just one thing which can be added... please demonstrate search and delete attempt for non-existing key only... for example attempt to search key=8 in linear probing and show where to stop searching in both cases (1-all keys are occupied, 2 hash table has some empty slots)
At 5:44 shouldn't it be h1(18)=h1(((18%11)+1)%11) and not h1((18+1)%11), as the formula is (Hash(x)+i)%size. The formula applied here worked as we are taking mod here but had the key been a string or had we used some other operation other than mod the probe would not be correct.
Hey Rahul,
The point you are making is correct, we have skipped calculations as (X%t + i) % t = (X+i) % t for i >= 0.
And, yes, Hash(X) can be any suitable function depending on the type of keys that we are dealing with.
I think it is not good to simplify this step which makes the listeners confused. Hope you can modify it later. Probably, calculating Hash(key) first, then do (Hash(key) + i) % size. :-)
Thank you for your feedback, Yanbo.
We will do something about this in the coming days.
@@GeeksforGeeksVideos what is ILLUMINATI ?
straight reading from your website. effortless
could you explain how you calculated the expected time to search/insert/delete ? 10:49
First of All thanks for the nice video. Linear & Quadratic Probing calculations are very clear. I am not clear on the Double hashing formulae application.
I see this "This video is contributed by Illuminati." in description box. What does it mean?
It's a handle. No worries! 😁
Beacuse HE IS
I would appreciate if you could define what hash2 function is.
hash function2(x) is just like hash(x) ,2 only represents that it is second function
Sir what does cache performance mean over here?
so is this o(n) in the worst case?
I am very confused @8:40
64Mod11 is 9, not zero. why did you assign 62 to 0th index?
In case of (62 mod 11), the result is 7 which is already occupied. So, we go for ((62 + 1*1) mod 11) which gives us 8, again occupied. Next we go for ((62 + 2*2) mod 11) which gives us (66 mod 11) which is 0. So, we insert at 0th index.
Hope this solves your confusion. :)
@@GeeksforGeeksVideos In case of (62 mod 11), the result is 7 which is already occupied. So, we go for ((7+ 1*1) mod 11) which gives us 3. we should use h0 index for computing h1(x) we don't use the number itself. The formula is correct Hash(key) + i) % size but your example problem is wrong
what do you mean by cache performance
The linear probing distributes data in the hash table more uniformly, which increases the cache hit probability. For eg. in video 7, 18 and 62 were placed uniformly one after another using linear probing, but in quadratic probing 62 was placed very randomly way above at the first slot. This randomness decreases the cache hit probability. If you don't know about the cache hit probability, you can find about it on the internet.
@@mrbobcat7399 COA 😎
why poor cache performance in case of double hashing
It is better you learn concept but also try to implement this concept by also coding than it gives more batter idea about the topic for programmer.
That is true.
You can try practice problems related to Hashing here:
practice.geeksforgeeks.org/tag-page.php?tag=hashing
so is lookup time O(n) if the value is not in the table? It just keeps incrementing i until reaching the end of the table?
for quadratic probing
the equation you written is
h(x)=(hash(x)+i^2)%hash table size
but in the explanation you written
1^1 and 2^2
please clarify my doubt
bro its 1*1 2^2
Sir, How cache performance is determined here ?
I am copy-pasting my reply from above but the answer is the same. The linear probing distributes data in the hash table more uniformly, which increases the cache hit probability. For eg. in video 7, 18 and 62 were placed uniformly one after another using linear probing, but in quadratic probing 62 was placed very randomly way above at the first slot. This randomness decreases the cache hit probability. If you don't know about the cache hit probability, you can find about it on the internet.
Sir your communication is really very nice, your acsent along with your explanation makes things crystal clear..
Hi my accent is also very good
Hii
Sir ,How time complexity came out to be this expression???
What does it mean by "Best cache performance"? Can anyone please help!
What kind of hashing do python dicts use?
What does best cache performance mean?
Can you please explain the case when you know the size of elements that will be inserted ??
why did you choose 11 slots for your hash table?
It is arbitrary.
in open hashing you explained how we allot same index value by linked list,but i want to know that at searching time,how will itgive us exact key @t ,we will simply pass our key to get the value during searching,and that hash function will convert it into a index which having lots of value in form of linked list because of collision,then how will it know the particular value of our key? how will it know there that which value of same index is value of the our key? please do answer
Is their any change in the internal implementation of map as par jdk8
Sir., If we insert an element 29.. After the deletion of element 18...in linear probing... Will it add at position 8 Or at position 10?
hello Sir,
it was pretty tough for me to understand the complexity part towards the end of the video
could be please explain it in some more details
thank you!
Think of it this way.
n/m gives you probability of finding an occupied slot in the table. So 1-(n/m) gives you the probability of finding an empty slot in the table.
Now both insert, find or delete operation require searching for an empty slot at the end. So, how frequently, on average, is our empty slot occuring? Answer is 1-n/m. Now this is the frequency.
For calculating time, you need to do the reciprocal of the frequency. Hence that gives the result.
@@saurabhbaranwal5031 thanks bro it helped
@@saurabhbaranwal5031 thank you so much man
@@akshitachander1 welcome ♥️♥️♥️♥️
@@saurabhbaranwal5031 thanks bro
If we have any circle and how would we insert?
excellent series, thank you. But i have 1 question if i have 10 elements to be placed in 10 slots, complexity is infinite? Can you elaborate on the ending part where alpha=n/m?
what will be if numbers more than size of table ?!
Table size can be changed as it is user defined
Isn't the avg time complexity o(1) for hashing ? As told in previous video .
Hello
Explain time complexity of Open Probing ....HOW is it [1/(1-a)] ??
explain the delete operation
If we are working with hashmap which hashing techniques are used. And why.
Please see this article: www.geeksforgeeks.org/internal-working-of-hashmap-java/
Hope this helps :)
Content is good but the volume is too low even while using a headphones. This definitely needs improvement.
Could someone explain why *1/(1-a)* ?
Think of it this way.
n/m gives you probability of finding an occupied slot in the table. So 1-(n/m) gives you the probability of finding an empty slot in the table.
Now both insert, find or delete operation require searching for an empty slot at the end. So, how frequently, on average, is our empty slot occuring? Answer is 1-n/m. Now this is the frequency.
For calculating time, you need to do the reciprocal of the frequency. Hence that gives the result.
@@saurabhbaranwal5031 Thanks Brother for the explanation , Well done
Thank you so much 🙏🙏
Nice Explanation
Great video! Thank you
Great explanation
Sir how can we calculate successful and unsuccessful search??
I'm a little bit confused...do I have to calculate the modulus two times i.e. First - while calculating the Hash(X) and then secondly when the '%' is encountered. Is that correct?
please also provide codeing examples for better understand
Its good video. the concepts were easily understud ,....but I have one issue that ,there is requirement of English subscription..as we can't see the images/screen completely...
What do you mean English subscription? Do you mean subtitles? We have subtitles with this video. You can turn subtitles on by clicking on the CC (Closed Captions) button. It's on the left of Settings button at the bottom right corner.
What images/screen can you not see completely? Could you please share the timestamp where you are facing these issues?
Please provide an example for double hashing
NICELY Explained with good ex
Thanks harsh kumar :)
1.75x !
sir can you please explain ..how you decide the size of hash table
I wish youtube had "3x speed"
Thanks for this video.
what if h2=h0
Hi :)
How \ Do we need to know which h1\h2 etx we used? how do we keep track
or this detail doesnt matter once we place the value in its place?
Thanks !
No, we do not need to know which h1/h2/h3 etc we used. This detail does not matter.
Once we put it there, we can always find it back using the same logic. When we are searching, we keep on probing until the value we are searching matches the value that is stored. If the value is in the table, we will surely find it. If it's not in the table, we will end up reaching an empty slot.
Thanks mates ! :)
You're welcome, Maayan!
Thank you sir.
am i the only one who thinks his voice is very low?
Videos are amazing, but I had to watch them at 1.75x speed.
To good sir but I am confuse in double hashing😕
Excellent best teach thx
the volume was too low
nice explanation.
Thanks :)
nice video on hashing :)
Thanks vikas :)
Great video thx!
More than teaching amazing concepts, it is better to make it audible to viewers. Audio important buddy
Use 1.5 speed
sandeep jain sir ka copy kr rhe
thnxx for confusing
I did not understand ):
Thanks! : D
His English is cool
❤❤
FIX YOUR SPEAKING ACCENT PLEASE