8. Randomization: Universal & Perfect Hashing

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
Instructor: Erik Demaine

In this lecture, Professor Demaine reviews hashing in the context of randomized algorithms.

License: Creative Commons BY-NC-SA

[shivjyotigarai]

Perfect Hashing starts from ABOUT 55:00

[mytennisjourney]

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

[lobstr]

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

[DenisG]

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

[corinachen]

thank you mit for teach me stuff that my lecturer should

[jjtwgvz]

Perfect and precise explanation! Thanks so much

[marcanthonybruno]

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

[monsteryoutube]

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 ?

[michelleslee]

love it but v curious about the frisbees

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

[aquilazyy]

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

[ldzjqfl]

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

[sudattabhattacharya]

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

[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.

[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.

[belightar]

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

[jimmypi]

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.

[dtrade]

La'ash got me rolling! Best prof ever

[tomwu]

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

[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?