Hash table double hashing

[@jananir9323]

This is a great explanation and loving all the videos in the hashing series so far! Thank you!

[@nonamehere9658]

About construction of H2(x): You've used (more or less) offset_increment = H2(x) % N, if H2(x) %N !=0, 1 otherwise. However, I think it would be more elegant (and also, make offset_increment uniform in set {1, 2, ... N-1}) by using offset_increment = 1 +H2(x) % (N - 1). Cheers.

[@iyadaithou228]

Excellent Content!

[@amoghdadhich9318]

How do we decide on the number to resize to? Is there an algorithm to find the next prime number?

[@svrmmb]

en.wikipedia.org/wiki/Generation_of_primes

[@magno5157]

Resizing is so expensive

[@sarthakshah1058]

Thank you for the video, it helped me a lot. However, why do we use Quadratic Probing when Linear Probing works?

[@WilliamFiset-videos]

I'm not sure there's a particular reason other than a different way to distribute the key-value pairs in the table (for better or worse).

[@ThePRINCEBARPAGA]

During Linear Probing items tend to cluster together in a bucket array, as clustering gets worse insertion and find will take longer like O(n).

[@BiancaAguglia]

@@WilliamFiset-videos It would have been nice to see an animation of how specific probing functions lead to different distributions of key-value pairs in the hash table. 😊Still, this is a very helpful and very well done series. Thank you for all the effort you put into it.

[@maxxxwan]

P(k, x) in your first slide, but in next slides P(x) is used. Why? thanks

[@WilliamFiset-videos]

Lifeng W, To be consistent I really should be using P(k,x) everywhere. However, Screen space is limited and simply writing P(x) saves me lots of room. In practice, you want to compute H2(k) only once because it can be expensive and furthermore it's a constant. So there's often no need to actually pass in k as a parameter since H2(k) is known.

[@LinhVũNguyễnDuy]

why H1(k6) +2* delta mod 7 = 0?, why not 7?

[@WilliamFiset-videos]

Multiples of 7 such as 7, 14, 21, 28... modulo 7 equals 0

[@sasanktadepalli1231]

Sir, Can u say some examples for Universal Hash functions

[@dallasmilanista8291]

At 7:39 , you say delta = H2(K2) mod 7 = 5. But H2(k2) = -79. How is -79 mod 7 = 5? Can you please help me understand if I missing something?

[@ankitmidha7993]

If you want to evaluate a modulus of a positive number you find the largest number that is less than the number and then find the remainder. Do the same thing for a negative number i.e. find the number that is less than the number and find the remainder. In the case of -79 it is -84 (and not -77 as this is greater than -79). So -79 - (-84) = 5. Hope that helped.

[@LinhVũNguyễnDuy]

@@ankitmidha7993 why is -84? and not 80 (thanks

[@Luna-vk9xy]

I need to confirm something. Why does N usually preferred to be taken as a prime number? I know for most probing sequences it prevents an infinite cycle of collisions But is there any reason for it? Does it also provide a more uniform distribution of elements within our HT?

[@constantijndekker8343]

Interesting question. From this video, I understood cycle length as the key property. Otherwise you can get the situation where certain slots are filled up and because of that the insertion might reach an infinite loop which is very bad, even if you catch this, what do you tell the user? “Sorry you cannot insert this element, try some other element”? :)

[@constantijndekker8343]

Small addendum. It was not mentioned in the video, but you can also select your second hash function in such a way to avoid these infinite cycles. If you like table sizes of powers of two, you have to make sure H_2 always returns an odd number for instance (or modify it in such a way that it does). I think you would have to do measurements to see if that is an acceptable compromise.