There are so many useless videos on this topic. Finally a video that explains it well, beyond a rough idea of what hashing /is/ and a trivial implementation!
Dear All, I just checked the CLRS book and also listened to this lecture. I think there is one step they did not elaborate: how can universal hashing be repeatable? after I map a particular key k-particular to a slot, if I look it up in the future, how do I get the "a" that was choosed randomly to do dot product with k-particular? ps. "a" here means : 569 00:35:40,680 --> 00:35:45,690 But the hash family h is just all of these ha's 570 00:35:45,690 --> 00:35:48,560 for all possible choices of a. 571 00:35:52,276 --> 00:35:56,860 a was a key so it comes from the universe u.
If you haven't yet found your answer: When you build the hash table and generate the hash function(s) (by choosing a random 'a') you store and re-use the 'a'. 'a' is not chosen randomly for each k-particular. You choose one 'a' for each hash function you use. The main idea is randomly choosing a hash function (by selecting a random 'a') to more likely get a random distribution of the keys across the bins, instead of assuming keys are random and having a static hash function.
It's great to see to much people typing that it's a fantastic video. But, why i get stuck to many times because the formulas and theorems? Would someone tell me how improve it ?
Hey can you elaborate on Fubini? I just got this: Pr{a_d = -(k_d-k'_d)^{-1}*∑a_i*(k_i-k'_i)} = (independence of a_d from a_i) = Pr(f(a_d))*Pr(f(k,k',a_i not d)) = E_{a_i}[Pr{a_d=f(...)]. Would appreciate any insight!
@@Thien--Nguyen The expected value of a random variable is actually an integral over a probability space. This requires measure theory to fully appreciate.
Hmm. Can you give me a hint? I know that E[X] = ∫_V xf(x)dx where V is the space that X maps to and f is the pdf. I know a bit of measure theory but a bit rusty on probability so can you point me to a source? Thank you in advance!
Finally, the instructor starts with "why bother!" It would have helped to have an example for the universal hashing. I also wonder about how practical the perfect hashing is if u is extremely large like the number of chess positions. Obviously perfect hashing wouldn't work for chess position because they are updated all the time. You don't know hashing until you have really done it. Not all applications lend themselves to the formulas.
I am confused when the dot product is performed on the Universal Hashing algorithm. Why there we are considering k_d - k'_d = 0 and is not (mod m) of that is also 0.
n people have n^2 chances of sharing a birthday, because each person has n chances of sharing a birthday with someone. Adjusting for double counting (two people share a single chance), by counting the probability of *not* having a match, the formula for p is 1 - ( n! * (m choose n) ) / (m^n). if m = 365, then for the probability of a collision to be 1/2, n actually has to equal 23 (actually it's p = 50.7%).
Discrete Math course was a prerequisite. In fact, if you had taken the MIT ocw 6.042J course, the number theory and math part becomes waaaay more easier. Look up the 6.042J course. Tom Leighton does an amazing job at explaining the Birthday Problem in Lecture 20
Also didn't get that. If Pr[total space of 2nd level linear] > 1/2 (for some constant we get to choose which does not depend on the absolute value of n), then I think that we'd have Pr[#trials until we get linear space > t] < 1/2^t, that is Pr[#trials > lg s] < 1/s (with s=2^t) which is whp on s which has nothing to do with n imho. I don't see how it would depend on n. What am I missing?
One key may be hashed multiple times when using a hash table to insert an item, search for the item and finally delete it. So, there is a problem that how can i guarantee the hash code stays the same each time the key is hashed using randomized hashing? For example, how can i make sure the dot product hash function uses the same vector a (a1, a2, ..., ar-1) for the same key (k1, k2, ..., kr-1) at different times?
Only when we are doubling/halving the table we make the random choice. Once chosen, same hash function (vector a in the example) will be used for all subsequent hashes until next doubling/halving. And yet the analysis is correct for O(1+n/m)!
Perfect Hashing starts from ABOUT 55:00
update 55:40
Thank you!
Perfect Hashing: @56:17
thank you
I like this guy. Finally someone who explains how to find the size for the second hash table! I wish I went to MIT
Look at the exams no you do not 😅😂
this is the best video I have ever seen on HASHING, HASHING gets my armpits moist on Tuesdays!
thank you mit for teach me stuff that my lecturer should
It’s amazing.I’m so excited for understanding the proof. Math from 6042 is really helpful.Thanks MIT!
Great explanation!
And BTW the video quality is just awesome :)
There are so many useless videos on this topic. Finally a video that explains it well, beyond a rough idea of what hashing /is/ and a trivial implementation!
btw. I think we've met at STACS 2007 in Aachen :-D
27:17
I think n/m might be (n-1)/m, cause number of k != l is n-1.
I'm I right?
14:10 That is an unexpected stab to my heart...
Dear All,
I just checked the CLRS book and also listened to this lecture.
I think there is one step they did not elaborate: how can universal hashing be repeatable?
after I map a particular key k-particular to a slot,
if I look it up in the future, how do I get the "a" that was choosed randomly to do dot product with k-particular?
ps. "a" here means :
569 00:35:40,680 --> 00:35:45,690 But the hash family h is just all of these ha's
570 00:35:45,690 --> 00:35:48,560 for all possible choices of a.
571 00:35:52,276 --> 00:35:56,860 a was a key so it comes from the universe u.
If you haven't yet found your answer:
When you build the hash table and generate the hash function(s) (by choosing a random 'a') you store and re-use the 'a'.
'a' is not chosen randomly for each k-particular. You choose one 'a' for each hash function you use. The main idea is randomly choosing a hash function (by selecting a random 'a') to more likely get a random distribution of the keys across the bins, instead of assuming keys are random and having a static hash function.
love it but v curious about the frisbees o_____o
It's great to see to much people typing that it's a fantastic video. But, why i get stuck to many times because the formulas and theorems? Would someone tell me how improve it ?
Perfect and precise explanation! Thanks so much
jesus, Demaine is amazing
This edition, personally I think, is better than 2020 edition
44:12 those two sums only need to be equivalent modulo m, not equal. So I don’t get your demonstration.
For future viewers:
It does not matter.
Just replace = 0 with (c1 - c2) x m
which will eventually become
ad = f(...) with f containing a term for cm.
Perfect hashing, great explanation
Step 50:00 is really Fubini's theorem in disguise.
This lecture was brilliant.
Hey can you elaborate on Fubini?
I just got this: Pr{a_d = -(k_d-k'_d)^{-1}*∑a_i*(k_i-k'_i)} = (independence of a_d from a_i) = Pr(f(a_d))*Pr(f(k,k',a_i not d)) = E_{a_i}[Pr{a_d=f(...)]. Would appreciate any insight!
@@Thien--Nguyen The expected value of a random variable is actually an integral over a probability space. This requires measure theory to fully appreciate.
Hmm. Can you give me a hint? I know that E[X] = ∫_V xf(x)dx where V is the space that X maps to and f is the pdf. I know a bit of measure theory but a bit rusty on probability so can you point me to a source? Thank you in advance!
Finally, the instructor starts with "why bother!" It would have helped to have an example for the universal hashing. I also wonder about how practical the perfect hashing is if u is extremely large like the number of chess positions. Obviously perfect hashing wouldn't work for chess position because they are updated all the time.
You don't know hashing until you have really done it. Not all applications lend themselves to the formulas.
10:55 Correction, when he says a[1] he means to say a[0] which is the first element in the array.
hey Ive seen your answers on graph theory on stack exchange ....small world
I am confused when the dot product is performed on the Universal Hashing algorithm. Why there we are considering k_d - k'_d = 0 and is not (mod m) of that is also 0.
It does not matter.
Just replace = 0 with (c1 - c2) x m
which will eventually become
ad = f(...) with f containing a term for cm.
Isn't u the number of all possible hash functions? all possible keys is different
Looking over this lecture.. i wish to be in MiT😢
this is GOLD.
Can anybody explain to me, why n people with n^2 birthdays gives a collision probability of 1/2?
n people have n^2 chances of sharing a birthday, because each person has n chances of sharing a birthday with someone. Adjusting for double counting (two people share a single chance), by counting the probability of *not* having a match, the formula for p is 1 - ( n! * (m choose n) ) / (m^n). if m = 365, then for the probability of a collision to be 1/2, n actually has to equal 23 (actually it's p = 50.7%).
This website explains very well: mathforum.org/dr.math/faq/faq.birthdayprob.html
But how's 23^2 365? Also when you substitute n^2 for m in your equation, it is not a constant.
Discrete Math course was a prerequisite. In fact, if you had taken the MIT ocw 6.042J course, the number theory and math part becomes waaaay more easier. Look up the 6.042J course. Tom Leighton does an amazing job at explaining the Birthday Problem in Lecture 20
@@sudarshanh.v993 Thanks man for the course name. Shall do it.
Why log n trail whp?
You can see the calculation here. It uses Chernoff bounds. courses.csail.mit.edu/6.856/17/Notes/n8-balls-bins.html
Also didn't get that. If Pr[total space of 2nd level linear] > 1/2 (for some constant we get to choose which does not depend on the absolute value of n), then I think that we'd have Pr[#trials until we get linear space > t] < 1/2^t, that is Pr[#trials > lg s] < 1/s (with s=2^t) which is whp on s which has nothing to do with n imho. I don't see how it would depend on n. What am I missing?
what is clrs
it's the book introduction to algorithms by clrs which lots of universities use for their courses
La'ash got me rolling! Best prof ever
i, i, i, Captain!
One key may be hashed multiple times when using a hash table to insert an item, search for the item and finally delete it. So, there is a problem that how can i guarantee the hash code stays the same each time the key is hashed using randomized hashing? For example, how can i make sure the dot product hash function uses the same vector a (a1, a2, ..., ar-1) for the same key (k1, k2, ..., kr-1) at different times?
Only when we are doubling/halving the table we make the random choice. Once chosen, same hash function (vector a in the example) will be used for all subsequent hashes until next doubling/halving. And yet the analysis is correct for O(1+n/m)!
proof of universal hashing seems confusing
really good
Is it true that you are accepting the 500th person who liked this video as a visitor to your lesson in mit? :D
Lol XD