8. Randomization: Universal & Perfect Hashing

[@shivjyotigarai2141]

Perfect Hashing starts from ABOUT 55:00

[@shivjyotigarai2141]

update 55:40

[@FastFSharp]

Thank you!

[@stormanning1163]

Perfect Hashing: @56:17

[@danumichael4864]

thank you

[@lobstr17]

I like this guy. Finally someone who explains how to find the size for the second hash table! I wish I went to MIT

[@privateaccount4460]

Look at the exams no you do not 😅😂

[@corinachen4954]

thank you mit for teach me stuff that my lecturer should

[@marcanthonybruno6022]

this is the best video I have ever seen on HASHING, HASHING gets my armpits moist on Tuesdays!

[@mytennisjourney4949]

It’s amazing.I’m so excited for understanding the proof. Math from 6042 is really helpful.Thanks MIT!

[@ViktorEngelmann]

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!

[@ViktorEngelmann]

btw. I think we've met at STACS 2007 in Aachen :-D

[@DenisG631]

Great explanation! And BTW the video quality is just awesome :)

[@aquilazyy1125]

14:10 That is an unexpected stab to my heart...

[@michelleslee8040]

love it but v curious about the frisbees o_____o

[@user-jj6tw3gv1z]

Perfect and precise explanation! Thanks so much

[@belightar9079]

This edition, personally I think, is better than 2020 edition

[@hasparus]

jesus, Demaine is amazing

[@sumitsinghchauhan2425]

Perfect hashing, great explanation

[@monsteryoutube8327]

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 ?

[@pnachtwey]

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.

[@cparks1000000]

Step 50:00 is really Fubini's theorem in disguise. This lecture was brilliant.

[@Thien--Nguyen]

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!

[@cparks1000000]

@@Thien--Nguyen The expected value of a random variable is actually an integral over a probability space. This requires measure theory to fully appreciate.

[@Thien--Nguyen]

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!

[@김주홍-d4h]

27:17 I think n/m might be (n-1)/m, cause number of k != l is n-1. I'm I right?

[@shivamrana4633]

Looking over this lecture.. i wish to be in MiT😢

[@DheemanSaha]

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.

[@halfEnlightenedOne]

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.

[@simpleffective186]

this is GOLD.

[@dtrade4787]

La'ash got me rolling! Best prof ever

[@yoyoclockEbay]

i, i, i, Captain!

[@sudattabhattacharya7927]

Isn't u the number of all possible hash functions? all possible keys is different

[@jimmypi7]

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.

[@darkclone5738]

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.

[@jayhoeliotdecabrio4050]

what is clrs

[@lula4148]

it's the book introduction to algorithms by clrs which lots of universities use for their courses

[@luojihencha]

Why log n trail whp?

[@pervognsen_bitwise]

You can see the calculation here. It uses Chernoff bounds. courses.csail.mit.edu/6.856/17/Notes/n8-balls-bins.html

[@paulogsf76]

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?

[@tianxiaoyang1123]

really good

[@tomwu163]

Can anybody explain to me, why n people with n^2 birthdays gives a collision probability of 1/2?

[@foobargorch]

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

[@Adam-zh6qr]

But how's 23^2 365? Also when you substitute n^2 for m in your equation, it is not a constant.

[@sudarshanh.v993]

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

[@hix0071]

@@sudarshanh.v993 Thanks man for the course name. Shall do it.

[@AkshayAradhya]

10:55 Correction, when he says a[1] he means to say a[0] which is the first element in the array.

[@gravity6316]

hey Ive seen your answers on graph theory on stack exchange ....small world

[@henryzhu7309]

proof of universal hashing seems confusing

[@maoqiutong]

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?

[@93nites]

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)!

[@mond2440]

44:12 those two sums only need to be equivalent modulo m, not equal. So I don’t get your demonstration.

[@halfEnlightenedOne]

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.

[@mehmetaliozer2403]

Is it true that you are accepting the 500th person who liked this video as a visitor to your lesson in mit? :D

[@halfEnlightenedOne]

Lol XD