Anuruddha Premalal It's showing the amount of times you are likely to probe when you encounter a hash Collision as the number of elements in your hash table increases for two different hash Collision resolution techniques. This is correlated to Cache misses Since you have to do more lookups.
Great videos man , i really love your data structures videos . Please also make videos on solving competitive coding problems (like you did previously on some code jam problems) after data structures series.
@williamFiset why not using a data structure to store the free slots in the hashtable array, and maintain this data structure when a slot get used, or the capacity of the hashtable get increased, so at any point if a hash value (index) is used, we look for the first element in the freeSlot Data structure and use it, then update the freeSlot Data structure to flag that, this element is now in use, etc. I did not try this idea, but is it right conceptually?
I think its because you'd still end up checking it by a value. A data structure stores data, but it itself is not the data. You would still end up trying to access the data to check it. If this doesn't make sense, give me an example of a data structure so I can help explain it.
I would also. like to add, data structures can be stored in an empty slot, but to check if it is empty, you'd have to use a value. Also, what data structures did you have in mind?
@WilliamFiset Is chaining at least 2 cache misses as shown at @2:00 because of the overhead of accessing the first entry in the linked list (i.e. going from bucket to entry), as demonstrated here (th-cam.com/video/ZDyv__yfTKs/w-d-xo.html)? For implementations with list head cells, wouldn't the speed be the same as linear probing?
Awesome videos man.
Your explanations are crystal clear and i'm super greatful for your work
Hello William, I always handled my issues with Seperate Chaining Hashing method , could you tell me why we may need open addressing method anyway?
look at the graph at the beginning of the video, it could potentially be faster when load factor is small
How can there be a cache miss in a hash table? could you clarify more more about y-axis of the graph shown @2:43?
Anuruddha Premalal It's showing the amount of times you are likely to probe when you encounter a hash Collision as the number of elements in your hash table increases for two different hash Collision resolution techniques. This is correlated to Cache misses Since you have to do more lookups.
Great videos man , i really love your data structures videos . Please also make videos on solving competitive coding problems (like you did previously on some code jam problems) after data structures series.
@williamFiset why not using a data structure to store the free slots in the hashtable array, and maintain this data structure when a slot get used, or the capacity of the hashtable get increased, so at any point if a hash value (index) is used, we look for the first element in the freeSlot Data structure and use it, then update the freeSlot Data structure to flag that, this element is now in use, etc. I did not try this idea, but is it right conceptually?
I think its because you'd still end up checking it by a value. A data structure stores data, but it itself is not the data. You would still end up trying to access the data to check it. If this doesn't make sense, give me an example of a data structure so I can help explain it.
I would also. like to add, data structures can be stored in an empty slot, but to check if it is empty, you'd have to use a value. Also, what data structures did you have in mind?
@WilliamFiset Is chaining at least 2 cache misses as shown at @2:00 because of the overhead of accessing the first entry in the linked list (i.e. going from bucket to entry), as demonstrated here (th-cam.com/video/ZDyv__yfTKs/w-d-xo.html)? For implementations with list head cells, wouldn't the speed be the same as linear probing?
Why can't you just make the size of the hash table , n, a prime number, p , then a linear P with a multiple less than p can't create a cycle?
learning a lot thanks
thank you very much
great vid
Where did my comment go
Oh this is a different video lol hahahaha ha my bad lol haha