Video 9-5: Perfect hashing analysis

0:03 So the algorithm to find a perfect hash function is first we choose h H1 uniformly from some universal class of hash functions and uh we use n bins for that. So we build a hash table with n bins Do we have notation for the buckets? I think we only had the size of the buckets. Let's just say for each bucket I and this goes from one up to N.

1:12 Now we only need to do something if there's um some elements in there. If there's at least two Let me draw a random hash function. Um, ash two from uh another universal class of fash functions. I mean it could in principle be the same but let's say it's it's some uh h prime again universal and uh this we repeat I should say with um x i squared sorry x i is already the number x i 2 bins Repeat this until this hash function is perfect.

2:45 And that's the part we already analyzed that takes um a constant number of repetitions in expectation. Uh and that's that's all. So the output then is the hash function that we get from the uh so output this as a function or plus the hash tables I guess we just build the hash table but there's there's one more step here um in that We repeat the entire construction.

3:29 I guess we can smuggle that into step one. I don't have to move that is not too big. Um and lesser equal n should be should be good enough.

4:05 So that's that's the um the algorithm uh we're proposing. Now we have to show two things that it it succeeds with good probability or um the number of repetitions is is reasonable otherwise it would uh run forever. Um and we have to show um number of repetitions is small and we have to show not confuse that with the algorithm steps. And we have to show that uh the space usage isn't too big.

4:53 Uh that's the two things we need for this algorithm to be useful. And uh both is a relatively simple argument. So I'm I'm trying to squeeze it into the part of the slide so we can still see the algorithm while we're doing it. Uh for part a um we just use that the expected number of collisions we get by the same argument as before because it's a pair-wise independent function. Each of the pairs has probability 1 / n to collide. And so the expected number of collisions is just n minus one / two. Which means the probability that we get less than n collisions is going to be at least 1/2 by marov.

5:52 So we uh in expectation only need um two repetitions for uh for the uh topmost step. And for the part for the steps two that was in step one and in step two uh this is analysis from before I'm just going to say see above same result um expected number of repetitions is two.

6:33 So over all of those um all of those repeated steps, we're going to get time proportional to what it takes to do one of these random samplings. And these are all these are all fairly fast. Um so the overall expected time is going to be what uh the time to draw the random functions is is actually small. we have to compute the bins and we have to find the functions here. Uh so I guess it's going to be linear.

7:11 Now for the second step um the space usage if it succeeds the way we defined it is um is upper bounded deterministically. The space we use is the space for the hash table cells and the hash tables the hash functions. But that's um say for the classes we looked at that's two numbers for per hash function. So we have linear that's for the top level hash function for the top level hash table and all hash functions.

7:58 And then we have a a part that comes from the secondary hash tables. And because these all use X I squared bins, what we get is the sum over all the bins. X I squ. Now that seems um potentially scary. All we know is that the number of collisions is bounded. But we already know how these relate. Um because okay tiny site calculation here we've established that from a single full bin from a single bin we get x i choose two collisions.

8:52 So if we um if we have x i^2 that's almost this right this is uh x i^ 2 over 2 minus x i / 2.

9:16 And so, uh, we're going to rewrite this as the linear term from before. Uh, might might run out of space. We'll see. The space analysis runs out of space. Um, then we have the X I choose to. And we have plus these guys.

9:51 that's summing up the sizes of the bins and divides by two. So that that's going to be less or equal n half really. Uh so that part goes into the theta of n bit. And this other term well every bin causes exactly that number of collisions. So what we're summing up here is all collisions. This is exactly our C and C we was uh we assume was bounded by N as well. So in total the overall space is beta N and that just follows from the construction the random part was um just the time. So in a way it's a a Las Vegas algorithm with respect to how much space it uses. Uh that's always fixed and the running time because of the repetition is is random.

10:56 Uh that's all on on perfect hashing. Um, with this combination of very simple tricks, you get some uh result that may at first seem seem relatively hard to uh uh even imagine that it's possible. Uh but really all of these we have achieved. the hash functions. We can pick our favorite um pair wise independent hash functions from uh the random lines modulo prime. Uh so these are easy to store as well and um we can construct a perfect hash function of using using a linear number of overall space in linear time. So all of the requirements are fulfilled and all that we needed is some clever random sampling and the two-level scheme.