Video 9-4: Perfect hashing

0:04 In the last little bit about hashing, uh I want to show you a nice probabilistic method construction. Um which is perfect hashing. Uh what is that? So uh as we mentioned before, a hash function is perfect for a set if there's no collisions. Uh maybe perfect, maybe you have higher standards, but uh somehow people coined this term here. And of course it is somewhat good if uh if you have no collisions then at least using this as a as a dictionary as worst case constant time then for lookups after computing the hash value. Uh you could also ask about minimal hash functions then you're you're assuming that the number of bins and balls is the same. That's going to get really tight. Yeah. Same as objective objectivity of a function. Yeah. uh is similar. So the the thing is that we think about a hash function to map from this large universe uh and then it cannot possibly be injective. But if you restrict it to the class then perfect means injective and minimal means subjective I guess.

1:13 But yeah, um is uh the the point is that you often think of functions mapping from the whole universe to some uh hash. You don't necessarily know up front which uh values you get. But for perfect hashing, you almost have to say uh you can always when when you choose the hash function first and then you get the set afterwards, there's always a set that makes collisions. That's that's clear.

1:41 Um so you can think of it as as an injective hash function. Um now you can also ask whether you can combine those two and then it gets it gets uh really tight. You're supposed to use exactly the space that you have and you can't have collisions. All of this um okay certainly only possible if you have enough space. That's that's sure. Um but it's still a very stringent requirement. So we'll in this case focus on a static set of elements and the schemes I know for making this dynamic are essentially uh rebuilding tricks where you then get amortized bounds. Um but there are fancy constructions available that compute minimal perfect hashing hash functions for a given set of elements.

2:37 And uh indeed what we want for a hash function is not just to be perfect um well want more than perfect uh it should be fast to evaluate which the term doesn't contain right it should be small to store again uh not in the term it should also be quick to find such a perfect hash function that's uh perfect things are not easy to find sometimes um and of course the per the term perfect doesn't tell us how many bins we're using and the job gets a bit easier if you spread things out a lot. So ideally we'd like um a linear number of bins and otherwise these are all essentially best possible guarantees. So it's it sounds like a a relatively um strict requirement and it's not clear why that would even be possible.

3:32 Let's start simple. Um we're going to pick uh a function from one of the classes that we've used before. So, one of these uh universal hash functions and let's just hope and pray and see what we can get. Okay.

4:30 The number of balls that we throw is fixed. We have we have the set xis given, right? What we can do is we can increase the number of bins until it becomes reasonably likely that this hash function is perfect.

5:06 So how big do we have to pick it? And of course you can you can just plug in numbers and uh try to randomly guess the solution. But perfect hashing that's the birthday paradox, right? We're trying to avoid having any bin with two balls. So we kind of know this the answer. We need that the number of balls is square root of the number of bins.

5:44 Now there's a constant factor and so on. Uh we'll have to take care of that. Um but that's that we roughly know what the answer will be. So in in other terms let's try what uh what pops out if we take just uh n squ okay as the number of pins the probability that some uh we want that the probability that the highest loaded in is is one.

6:32 Um So we're in the universal class uh from before. So we're using the analysis the same trick that we've used in the analysis here.

7:16 Except that now we pick just one here and uh we'll we'll use the same upper bound in terms of collisions. And so if you if you work out uh if m is at least n^2 then this is indeed one All right.

8:35 And we already know that this is the probability that this exceeds twice its expectation. That's the calculation from before. And so that's going to happen with probability 1/2, right?

9:00 Which also means um the converse that we have no collisions with probability at least 1/2. So if you just pick enough bins, specifically it's enough to pick n squared bins, we have a good probability that just a standard universal hash function from one of the classes we know will do the trick and will be perfect.

9:54 course, we're not all that happy because uh that uses quadratic space not for storing the function but for storing the hash table. We have to somehow store all the bins. If if you were using this in an in a hasht data structure, it's only efficient if you can access buckets by index. And so you have to materialize an array of size m and that's that's not that great, but it's a starting point. And um indeed a very simple trick gets this to work. uh in um much more reasonable space.

10:44 And the trick here is to uh apply two hash functions. We'll have a hash function one that distributes the universe or the elements in X to uh tier one buckets.

11:07 And here we don't insist on on perfectness because we can't really we want these uh first level buckets to be of a reasonable size. So maybe linear.

11:29 So we must live with some collisions and we kind of know there will be one that has roughly a square root n unless we're lucky or maybe cube root n. That's that's where we'll have to live with that. But then for each of the tier one buckets, we're going to find a secondary hash function using exactly the construction we've just done where we allow the quadratic blowup to be sure that it's with good probability perfect. But we'll show that that's good enough because uh intuitively there's no bucket bigger than square root n. So even quadratically blowing up these things is not going to get more than linear.

12:39 So we're using a number of buckets mi that is quadratic in the size of the bucket. So now I need a notation for these. Uh let's say we use x i again.

13:07 Um so first of all um that's likely to succeed because the first level we just draw a random hash function and then for each bucket we draw a hash function where we have probability 1/2 to succeed. So maybe we have to on average repeat each of the buckets twice to get a a perfect function. But that's that's still expected linear time.

13:55 And the overall hash function of course is you uh first apply h1 to get the bucket and then you use the secondary hash function. And so you take a value x and you map it to h2 of h1 of x of x.

14:17 It looks a bit more crazy than it really is. You just evaluate the two one after the other. Now the the the bit that's missing is to analyze the space. Um, I think we'll postpone that till tomorrow.

14:44 I'm just going to write down the the statement.