Good Vid. However there is something I didnt get. When you have a collision and two piece of data are stored at the same index. I understand that with linear prob for example we just move forward the index of the generated hashcode until we find an empty space. However I dont think you explain how I will unambiguously retrieve my data afterward because a similar hashcode still refers to two different data. Do we have an extra array to keep track of which data was "linear probed" ?
Bcz in linear Probing, Primary and Secondary clustering occurs however in quadratic probing the Primary clustering problem gets resolved (bcz data is uniformly distributed in the hashtable)but Secondry clustering still remains. Double Hashing resolves both these problems. Primary clustering means as he said in the video, data gets stored in the same area (the hash value for entries/data is same and we search for the next free space in a linear manner so every new entry/data have to be stored to the next free/available space) which basically makes a cluster of data. Let say array is of length 20 and the values are stored at 3 4 5 6 7 and 8 indexes and all other indexes are null If you notice, a cluster is made, now to find an element, it can take O(n) time at worst but we don't want this bcz hashing technique was made to search for our data is constant O(1) time. Now let's understand Secondry clustering through Quadratic probing. Secondry clustering means u can say, the probing sequence for finding an empty space become same. Means let say 10 length's array is filled at 2 3 6 and 9 indexes. Now an element arrives and its hash function gives us the hash value or the index where it should be stored let say it's 2 now 2 is already filled we shall move forward to 3 it's also filled then we shall move to 6, it's also filled then 9 then again 2 then again 3 then again 6 then 9 and this process goes on until at some point the hash function finally gives us the hashvalue / the index where it can be stored but in some cases the search gets infinite. So again in this case the the time complexity becomes O(n). Hope you got the idea of I'm saying and if u notice any mistakes in my explanation or concepts let me know. ❤️
Great format! Really enjoying your videos!
i have exam in 30 min thanks this helped me a lot
Really awesome videos
thank you doctor ❤️
Pretty useful, thumbs up!
Well explained :)
how to make sure the result of openAddressing is not out of boundary of array.
Great video! But I didn’t get the last one about double hashing. What if after adding two hashes my hash code will point to already taken space?
in that case final index will be (index1 + 2*index2) , where index 1 is from hascode 1() and index2 is from hashcode2()
Good Vid. However there is something I didnt get. When you have a collision and two piece of data are stored at the same index. I understand that with linear prob for example we just move forward the index of the generated hashcode until we find an empty space. However I dont think you explain how I will unambiguously retrieve my data afterward because a similar hashcode still refers to two different data. Do we have an extra array to keep track of which data was "linear probed" ?
You have to compare the hash of the thing you found at the location with the hash you calculated originally if they match its the correct item.
why should I use quad probing rather than linear ?
Bcz in linear Probing, Primary and Secondary clustering occurs however in quadratic probing the Primary clustering problem gets resolved (bcz data is uniformly distributed in the hashtable)but Secondry clustering still remains. Double Hashing resolves both these problems.
Primary clustering means as he said in the video, data gets stored in the same area (the hash value for entries/data is same and we search for the next free space in a linear manner so every new entry/data have to be stored to the next free/available space) which basically makes a cluster of data. Let say array is of length 20 and the values are stored at 3 4 5 6 7 and 8 indexes and all other indexes are null If you notice, a cluster is made, now to find an element, it can take O(n) time at worst but we don't want this bcz hashing technique was made to search for our data is constant O(1) time.
Now let's understand Secondry clustering through Quadratic probing.
Secondry clustering means u can say, the probing sequence for finding an empty space become same. Means let say 10 length's array is filled at 2 3 6 and 9 indexes. Now an element arrives and its hash function gives us the hash value or the index where it should be stored let say it's 2 now 2 is already filled we shall move forward to 3 it's also filled then we shall move to 6, it's also filled then 9 then again 2 then again 3 then again 6 then 9 and this process goes on until at some point the hash function finally gives us the hashvalue / the index where it can be stored but in some cases the search gets infinite. So again in this case the the time complexity becomes O(n).
Hope you got the idea of I'm saying and if u notice any mistakes in my explanation or concepts let me know. ❤️
Thank you for videos, but make that 0x7FFFFFFF a variable, man :)
Hash &= ~ -1
Nice format, but does not explain difference between linear and quad probing. Also, what happens to search and delete in quad probing.
Yes he does.
He can write backwards!!!
th-cam.com/video/m_lGOYhtGEA/w-d-xo.html