Video 9-3: Universal hashing

0:02 In the next section, we'll look at universal hashing. So, uh bringing randomization into hashing. Um as I commented on earlier, the balls into bins model is very optimistic, maybe worryingly so uh by making all these independence assumptions.

0:18 And so it seems to work well in practice sometimes. But if if anything adversarial plays in, um you shouldn't rely on this. So instead uh we'd like to do what we've done in in other algorithms. Replace an assumption about the goodwill of data with an explicit randomization where we have control over the uh random bits. And so what that means here is we have to pick a random hash function which sounds crazy enough. Uh if we try this naively, pick a random function out of all possible functions, that's not going to work because you need too much bits of space to store them. Basically just a counting argument. If you were to do that, you have to distinguish all all possible functions and then you definitely need already superlinear space just to store the function and let alone uh calculate it efficiently.

1:12 Uh so that seems out of the question. Um but we still like to use this idea and instead of picking from all possible functions, we pick it from a much more restricted class. Uh but it has to be a convenient function so that we still get enough guarantees. If we just pick an arbitrary class of functions, I guess the behavior could be arbitrarily bad. Um what is the I guess oldest oldest such uh uh definition of a convenient class is a universal family of hash functions.

1:51 So same setup as before. We have hash functions mapping to the same to the fingerprint universe one zero up to m and we choose always uniformly at random from our our class. Uh that's that's uh important for the probabilities. And if we pick a um a class capital H here where the following things are true then it's either called universal or strongly universal. For universal we want that for any two different elements in the universe the probability that they collide under our random hash function. So in all these cases here the probability is over the hash function to be 1 / m and strongly universal is a slight twist on this where we say we can not just the collision has a certain probability but the collision of uh or that the the hash function takes two given values has to be essentially what you would expect from a from a uniform random hash function.

2:57 So both of these properties would be fulfilled by uh all possible hash functions. Taking a uniform function out of all possible hash functions would be a universal family of hash functions. But we've already established that it's not a useful one. Um you can easily show that the strongly universal indeed implies universal as the name suggests. uh but most of the analyses actually work with universal. So that's uh strong enough for the analysis we'll do. Um we'll always assume uniformly at random chosen a hash function from some such class. Uh whereas the input data can then be completely adversarial. We don't care because we choose a random hash function. So we're defending ourselves against this. Uh probably you've seen some examples of universal families of hash functions before. There's basically two two types and maybe you've only seen one of them. Uh the more traditional one is this uh modular arithmetic magic function. You take two parameters a and b and then the function is essentially a random line but you compute everything modulo or prime.

4:16 um we need some prime number that's larger than m but then we take modulo m at the end that's that's one way to get good hash functions and you see uh depending on which parameter um range you pick you either get universal or strongly universal and it's it's kind of curious that this strongly universal family allows the function where the line is is trivial where it doesn't have any slope so you're mapping everything to the same hash value. But adding this seemingly stupid function makes the family stronger in terms of its randomness probabilities. But that's just because it um establishes some symmetry. That's all that happens. Um the second class is slightly more useful in practice because it's faster to compute. The thing with these uh with this first one is you need to compute modulo a prime. So that's a division each time. Sounds like not that that a big deal and it isn't. But uh in terms of relative performance, if you can do the modulo arithmetic with a power of two, you can just do bit shifts and that's a tiny bit faster. And so there's um another family of hash functions that's also universal where you have a a random multiplier and then you first take the least significant bits and then you take the most significant bits.

5:43 Uh it turns out this can also be shown to be to to yield a universal function if you pick only odd numbers for a.

5:55 Uh I don't want to prove that they're universal. Um this is uh often something you've done in undergrad. Um I want to briefly uh use the universal guarantees here and to kind of complement what we've seen for the balls into bins model. Again, remember balls into bins had or xhat the most loaded bin roughly log n over log n. And um here is a bit more a murky statement. Um what we get is that the the most loaded bin that's our x hat is uh with good probability not larger than n divided square root m in particular if you if you again set n to m then you can just combine these to be let's take n then um the most loaded bin is not usually bigger than 2 * well square root of 2 n. So roughly square<unk> n but that's still a lot more than log n or login over log n. But let's uh let's see at least that's that's not nothing. And this is the worst case um for all those hash functions. If you take what's the expected query time, if you average over all buckets, then you get these nice constant expected uh running times. If you care about the worst of all the buckets, the largest uh load of any bucket, you get a a much more uh much more um yeah much bigger number, much weaker guarantee.

7:50 Um let's denote by CI that uh the two keys X I and XJ collide which of course is just the the event that the hash values are the same And so you immediately see this is uh where the universality comes in because that means the probability for any of these CIS will be bounded by 1 / m.

8:38 And let's also define the total number of collisions as the sum over all the pairs one to n. I guess I don't want to double count. So say one.

9:03 So ordered pairs. Uh fine. So why bother with collisions? Um that's what we get from the universality guarantee. uh let's let's maybe first say what is no longer true. Um if we just assume these uh universal hash functions the number of balls in any given bin is no longer a binomial distribution. So if I look at my uh XJ that's in general no longer binomial.

9:44 binomial is inherently using the independence of all the choices of the balls. And uh this is no longer true. An easy way to see this uh think about the universal hash functions we've had where you pick a random line ax + b and do some modular arithmetic. But fine, the point is if you um if you give me two uh x i's x1 and x2 and their hash values, I can compute what a and b are. There's just two variables. Or maybe if I'm very unlucky that it's not unique. But uh for most for most instances you get after two fixed values you know what the hash function is and then uh of course the rest is no longer independent like is all deterministic up from that point on. So this can't work and that's the reason why we get much much weaker guarantees. Uh what we still can do is compute the probability of these collisions.

10:42 So immediately from the definition um we get the expected number of collisions overall just the sum of those right cig um how many are there? Well, n choose two ordered pairs. And the probability for each of them is 1 / m.

11:19 So we get an upper bound for the number of these um these collisions. And of course um well okay as a as an upper bound we can say it's n^2 / 2m uh that's good enough.

11:37 What why do we care about collisions? Well, um let's also say uh we have x head the number of balls in the fullest bin.

12:01 All of those balls in that bin obviously collide. So if I take Xhat and take all two element subsets, these will all be collisions.

12:24 I get that the number of collisions C must be at least this Xhat choose 2. which of course we can rewrite xhat xhat -1 / 2. And so we can now plug together um and get get a bound for this.

12:48 The probability that our x head is larger than some value. And here I'm I'm using hindsight knowledge to pick that value. Uh if I want to upper bound the probability I have to make this more likely. So uh um I'm replacing the x head for this. Um I can use something like this or is roughly xhat^ squar over two.

14:14 So to bound that this is bigger than some value this has to be bigger than that value squared And this is something we can compute because we can compare it with its expected value.

14:43 In this case, that's precisely two times the expected value. And so that's by mark of inequality at most 1/2. So the probability that this exceeds roughly a square root of this uh is is 1/2. And that's how you get from the number of collisions to some bound on the fullest bins.

15:11 And if we insert n equal m uh we get the simplification that we had before. that's that's already the end of the proof. Um which means universal hashing achieves something. The worst case guarantee for the worst case query time is square root n. But it's not comparing so well with binary search trees anymore. Much much worse than the bound that we had for universal uniform hashing. Now we only proved an upper bound. In principle it could be that just the analysis is too weak. But this turns out not to be the case. And um we'll we'll look at this in the upcoming exercises a bit more. uh if all all you assume is essentially the universality of the family of hash functions then you can actually get this square root n uh for practical choices somewhat of a good and bad news if you if you want for these kind of hash function families I showed you you can actually show a better bound but it's still not poly loarithmic it's better than the square root n but it's cube root n roughly uh so I I wrote close to because there's some uh polylog factors missing and the analysis is is a uh is more complicated.

16:55 So the and I think this is this is essentially tight. So it seems for the practical choices of universal hash functions the truth lies somewhere in between but morally closer to the uh square root n than the login case from universal from uniform hashing.