Video 5-3: Perfect Hashing

0:02 Now, it turns out these simple arguments about pairwise collisions are good enough to prove uh an interesting data structure, an interesting algorithmic result. And that's perfect hashing. Uh let's first define what that means. Uh perfect supposed to be good, I guess, right? So, a hash function is called perfect if it doesn't have any collisions. So, it maps all the n elements to different hash values. Well, clearly there's some constraint here that uh this only ever can make sense if the number of keys is at most the number of buckets. Otherwise, it cannot be perfect. Um we can also ask for a hash function to be minimal, which means n is n is m.

0:52 So, I have exactly as many buckets as I have keys. And I could ask for the same for the two things together, minimal and perfect. Then it's just the permutation of the keys into buckets. Um interestingly enough, these even exist. You can construct them, but that's more complicated. Uh and we don't care as much about minimality here because that's just making the hash table a little bit bigger. So, um this is just for for context. Uh what we're interested in here is perfect hashing because it if if you have a perfect hash function, it means any lookups are constant time because well, if the hash function can be evaluated in constant time, you compute the hash function, you look at that position in the hash table, and there you find your element or it's not in the set.

1:46 Because this perfect hashing sounds extremely strict, maybe this is very hard to do. Let's first focus on a static set X. Um I think this is S. A static set S of keys that are known and then we build for that specific set our hash function. Okay. Uh [snorts] still we would like the hash function to have some good properties. Otherwise, it's not very useful algorithmically. Um what I what I said before is we want the hash function itself to be cheap, fast to compute. Uh remember these examples we had before, these universal hash functions.

2:23 These guys, this is all fine. This is constant time assuming that the numbers fit in in the words of of a computer. It's a few additions, multiplications, and divisions. Maybe maybe not even additions divisions.

2:38 That's the kind of functions we would like to see. >> [snorts] >> Uh we also here may have to store this function or if we compute it specifically for each set, so that becomes important. Um the overall Well, I guess the overall function This is the overall space for the hash table. The function should ideally be even smaller. And again, um I wish I had stayed on the slide for a second, but the functions we looked at from these universal uh families, they just need one or two numbers. So, in a way uh a constant number of words uh was enough for those.

3:27 So, I could write down I know that the general pattern of the hash function is kind of statically known. And for each individual data structure, I store just the words um for a constant number of words for the parameters. Uh it should also be fast to find it given a set of of keys. So, we don't have construction time that's too slow. Maybe this is okay to compromise a little bit. Uh and ideally we won't not want the number of buckets to be much bigger than needed. Minimal is maybe very strict, but at least close to that, a constant factor away from the number of keys would be fine. That's quite a mouthful. Why would that even exist? I think it's it's a fair question to ask whether this is asking for too much. Uh, but it turns out it's totally fine. It exists. And here it is. Well, that's the claim. Um, the construction I'll show you.

4:22 Uh, this is due to Fredman, Komlos, and and Szemeredi. Uh, and it's formally stated as follows that if you have, um, a class of hash functions that is universal, for example, the ones we've looked at, and a a static set S of n numbers, then you can construct in linear time, so just the time to read the set, um, expected time, I should stress though, uh, a perfect hash function H that is fast to evaluate because it's taken from this, well, it's as fast to evaluate, uh, essentially as fast as evaluate as the hash functions themselves. That's this part. So, if I have time T to evaluate the functions in capital H, the function I construct has a constant factor worse at most. Uh, it's perfect, and it the number of buckets that it uses is also linear. So, in a way, if we use, um, with our hash functions from before, all the properties from the previous slide are fulfilled simultaneously.

5:56 >> Uh maybe the expected time is is potentially not perfect, but uh randomization is good. I I tried to convince you lengthy of that fact at the beginning of this module. Um So, it is is is rather uh even even though it is static, um Ha, is this No, it's here. This should be uh like stressed, of course. It's a static set, so you cannot change the numbers you store at this point. Uh still, I think it's surprising this even exists. Let's try to prove that. So, uh the first step of the proof is kind of an um a toy example that doesn't quite solve the problem yet, but we'll use it as a building block. So, what if we just try to make the a hash function from our family perfect by giving it many many buckets.

7:08 And here the the point is that we'll pick the functions at random, the hash functions. >> [snorts] >> There's no number of buckets that gets this guaranteed 100%, so I think I should here say with a good probability.

7:34 And what does good probability mean? Maybe constant probability, probability 1/2. So, if you pick a random hash function, it may or may not succeed, but if it has probability 1/2 to succeed, you do it a constant number of times in expectation, and then you have a good one. >> [snorts] >> Note that the number of keys n is fixed. What we have is that m, the number of buckets, is something we can play with, and this can be a function of n. I can adjust it to the number of elements I want to store. Now, remember the birthday paradox.

8:27 The way people usually state it is how many people do you need before it's likely that there's two with the same birthday. But, you can also flip it around. How many people do you need before there's how how many people can you have before there's likely no people with the same birthday? Or, how many days a year would you need for a given set of people to make them have likely no joint birthdays? It's a bit You would have to subdivide the days, I guess. Uh so, the birthday paradox says that roughly at this funny number of with squinting a bit, uh uh roughly when the number of people is square root of the number of days, that's the threshold where it becomes an interesting probability to have either of the outcomes, collision or no collisions at all. If you invert that, we're getting m as a function of n.

9:36 So, let's just do that and see what happens. What is the probability that any bucket or the largest bucket has at least two elements in it? Then we have a collision and then we have that is uh not perfect.

9:58 That's something we would like to upper bound. That's the bad event. Now, remember everything was nicer if we expressed it in terms of uh pairwise collisions.

10:18 Um let me maybe smuggle in here first. Uh if X head is at least two, the number of pairwise collisions must be at least one.

10:30 Because at least from that bucket I get one pairwise collision. Right? for the choice of parameters we've used, that means C is larger than n squared divided m. Because m was n squared, C is greater than or equal to one. That's precisely one. Okay? Let me maybe uh This used to look like a large quantity because we usually think of n and m being roughly the same, but if m is picked so much larger, that's no longer true. So, on this quantity uh this is the probability that C is greater than or equal to one, but really I can re-express that uh this as C being larger than n squared over m. And remember our lemma from a bit before?

11:36 A while ago. Uh the probability that the largest bucket is larger than than this is at most 1/2. But here it's it's easier to go directly via the first lemma. Um the expected number of of elements here was with this uh factor two.

12:01 So this is 1/2 again by Markov's inequality. Okay. Let me smuggle in That's the probability that C is greater equal to its ex- two times its expected value.

12:25 Uh very same calculation as before. But what it says that is that with probability 1/2 or larger than 1/2, I have no collisions at all. That's great. So with probability 1/2, my function is perfect.

12:51 So I'm done. Well, this function has a slight problem, namely it uses tons of space, quadratic space in N. So that alone doesn't work. I don't want a large hash table that has so many empty cells. So that seems doomed. Except that with a very small trick, we can make it work better. And the idea is to do uh two hash functions. The first hash function has roughly a a linear number of of entries.

13:35 So, I don't know. Let's call this What did I call it? H0 or H1? H1. So, there's a a function H1 that maps our universe to And here we pick M say 2 * N. So, we're going to have some collisions here, quite a few actually, but that's going to be fine. Now, for each of these uh buckets, so there's potentially many elements in here. Maybe there's some empty ones. But most cells will have more than one entry. For each of these, I have a secondary hash table with ample space compared to the number of elements hashing to it. And each bucket here, so each bucket I has uh a different hash function H2 superscript I that maps these remaining elements to now uh secondary buckets. And these we want to be perfect. Well, we want the overall thing to be perfect, but these specifically we can use the precise scheme from before. So, we still use this quadratic space solution as a building block, but we use it in a way that it doesn't blow up the space overall because we first scatter the keys across buckets in the kind of normal hashing way.

15:20 So, here we use MI as the number of buckets. And that's going to be uh the number of elements hashing to the buckets X I squared. So, here we have X I elements.

15:50 Now, first of all, um each of these um the right-hand side here, we may have to retry a few times before we get a perfect hash function.

16:17 then um the buckets here are all distinct. And if you now look at the the combined hash function, you first have to hash the actual value to its buckets, and then within the bucket to another location. That second location is unique. So, overall, you're assign every element in your set a unique bucket. It's no longer one contiguous table, but you can reinterpret it as such. Everything is static and known up front, so it could uh this one could essentially be just a a virtual table.

16:57 So, the final hash function is H2 H1 of X of X, right? We The I is chosen using the first hash function. And we have to make it so that the they don't collide in different sub tables. Now, there's um there's a few things we want to prove about this um hash function. That's the construction. Uh let's look at the construction time for the evaluation time first.

17:34 What do we do to compute one of our um hash values for the constructed function? Well, we just apply this formula. We first compute one hash function. That takes constant time in the schemes we have or T times uh T times steps in general. And then we do the same thing again on a different uh universal hash function. So, evaluation time is essentially two times T. Maybe plus a a little bit for stitching the value together and shifting things so that they're mapped to um unique integers.

18:18 The second thing we want to show is maybe more and more important. Um that the overall space is not too much. So, the M here is not the M from my uh proof, but rather this is the total number of buckets we use across all the secondary hash tables.

18:36 Maybe let's call this M0 then just to be able to distinguish those. So, we have M0 for the top level and then M1 up to M M0. Uh Okay, let's call this S instead. Doesn't matter. The number of slots. Okay.

19:07 What's the total space? Well, the total number of buckets in in final hash function, M is the sum of all those buckets here. I will if if you want to compute the space usage of the entire data structure, there's the uh first-tier hashing scheme that we have to add, but that is linear in N. So, even including storing the hash functions, if they can be stored in constant words each as in our hash families, all of this is is linear in M in N. Excuse me.

19:49 So, I have N plus M for M these number of buckets. The crucial thing is how many buckets I have summed over all the subtables. So, how many do I have? Well, by definition, uh I have from one up to S M S M I.

20:18 >> [snorts] >> Okay. Uh so, in general, this could be really bad if I have bad luck with my top-level hash function, I map many things to the same bucket, this might be large. What I'll do again is I compute the expected value for M. And then we just keep retrying until that space is small enough. That's again just Markov's inequality. If we're happy with a bound that's a factor two worse than the expected value, we're good. But we have to compute the expected space, the expected number of these buckets, and hopefully that's not too large, otherwise we have a problem. So, the key in the analysis is to compute the expected number of these buckets, or in other words, the expected number of these Now, that's an annoying quantity, but we can do a little trick.

21:27 I'm going to split XX squared is the same as X * X, and that's the same as X * X - 1 + X. I'm just uh rewriting creatively.

21:59 Now, the second term is very harmless. That's the total number of elements in the bucket. Well, that's N. That's by definition the keys. So, that that term is fine if I want to bound the overall thing in terms of of N. How about the the first part? Well, apart from um a factor two, this is uh so, let's say N plus This inside here is essentially XI choose two, but a factor two in front.

22:44 And I can move the factor two in front of the sum, maybe. Now, that quantity, that's precisely our C because it counts for every bucket, how many pairwise collisions do I have? Well, as many as there are elements in this bucket, choose two. So, again, I found something that relates to my uh my quantity C. And uh expected value of C.

23:25 And the expected value of C we've computed already. Scroll, scroll, scroll. Just convince you. That was this guy. Um I think in all my constructions so far I've pretended the little C is one. Let me pick a or we ignore the constant factor there. Uh otherwise, you have to scale the numbers uh the the sizes of all the hash tables. You have to multiply it by small C. So, it's actually n squared over 2 m.

24:27 Uh that's that's true, but m is S in my case. And so, the two cancels, and S was set to 2 n. All right, so we have one more factor that cancels, and the overall expected size of the secondary buckets summed up all together is linear in n.

25:09 So again, what does that mean? If I sum up the sizes of all my secondary hash tables, the expected size I need is linear in n. So I can keep retrying a few times. If I allow it twice that expected number with probability 1/2, I'm going to succeed. So after trying a a constant number of times, I'm going to find an example for my top-level hash function so that all its its buckets, even squared, sum to n.

25:41 >> [snorts] with m less or equal, say, twice this, so 3 * n. And for that, we start generating our secondary hash functions, which again, we may have each we may have to try a constant number of times before we find one that is perfect. But then we're done.

27:04 >> So, that satisfies all the properties that we claimed. The overall space for the data structure is linear in N. And the time to evaluate our hash function is essentially twice as much as I had for the original hash function. And we're perfect. Now, this is fairly simple because the set the set of numbers was static. It's a bit of uh bit of expected value calculations and getting lost in these um gazillion parameters of the construction, but it's not conceptually very complicated. And this is very practical. It's not not hard to implement. It's maybe a bit annoying that the table has to be a good constant factor larger than the number of keys, but other than that, um fairly practical. >> [snorts]