Video 3-11: Universal Hashing

0:02 All of the analysis that we've seen about this uh linear and linear separate chaining hashing was under the assumption that the world doesn't conspire against us and that indeed the world is very nice to us. It gives us keys so that the collision probability is as if they were all independently drawn. Now that's not always the case and um under this assumption everything's good. um you still need the doubling trick if you get more and more keys but all of this is fine and essentially how Java implements hashmaps. There is though um a fallback because Java essentially does this. There's a fallback for the bad case that you have many things hashed at the same bucket. And in that case, Java has a switch over. If this is a dozen keys or so, they um stop building a linked list and say, "Ah, something's going going wrong here. Let's rather be careful and build a red black tree, a balanced binary search tree."

1:04 This is one option, but it's kind of an unhashing option, one where you don't truly believe in hashing. Let's instead find a different one. Also, I mean, this this then degenerates to log n running time. We could have used a red black tree from the start. So, all of this um is is kind of constant if you assume this uh assumption. Worst case we've discussed before is very bad linear time. So another way to avoid this is to um inject randomness actively ourselves.

1:47 Uh we'll see this again or you've seen this with with quicksort. That's the classic example where where you study this idea. In quicksort, you've you have to choose your pivot element and you might arbitrarily pick any position, but then you're leaving it up to choice and it might be the choice of your adversary. Uh the other option is you pick a random position, then your adversary has a harder time making your life difficult because you you're unpredictable. you keep an aura of randomness around you and make make something unpredictive unpredictable and that that is harder to get a worst case against the same very very same trick here. We can um inject randomness into our hash functions as an abstract idea. I think this is very convincing but um how like the hash function shouldn't be just random. I want to find my elements again. So you have to be a bit careful. uh but there's a an appropriate notion it's a very classical uh result as well from for data structures and this is called universal families of hash functions or in short just universal hashing.

2:59 I stress the fact that this is an old and kind of classic trick because again the name is a bit bad. It should have just been called randomized hash functions, but okay. Uh, it's called universal hashing because of its universal applicability or I'm not sure.

3:19 It's a notion that says something about um a set of functions, a set of possible hash functions that you can choose from. H the assumption is that you uniformly at random pick a hash function from this set. But this is fine. You get to decide this. You're actively sampling one of those functions. And then such a family is called universal with a certain tuning parameter C. If um the the collision probability of two items is C divided M. So think think C equals 1, then you uh you get something very close to what we've had previously. But there's a um let me show the connection with the simple uniform hashing assumption from the previous section. Right? If you set C to one, this is essentially the same well the same right hand side. But there's a crucial difference which is that here there's an all quantifier over the values.

4:25 Uh this is a statement where I fix the values X and Y and I say it has to hold for every value. Well, what's random then? Well, the choice of the hash function. That's why I'm stressing here below this P, what is the random thing? And here in the uniform hashing assumption, of course, it was the the values themselves that we assume to be random.

4:48 So, we essentially just declare we want to have the same collision probability, but this time over something random that we control. Okay, that's a lovely definition. Um, let's see what the advice us. And if you wish, it is kind of cherrypicked. It's chosen precisely to make this slide work. Suppose I have such um a C universal family of hash functions and I pick my random hash function. Then the adversary might as well pick the bad inputs for me. But the um the crucial thing is that the adversary doesn't know my hash function otherwise they can always still fool me. So the uh here it's important without knowing my age.

5:43 Okay. And then we'll do the same analysis. We ask how many other it um keys are hashing to the bucket that a certain uh value xi hashes to.

5:55 And we'll define the same things as before. This is a literal copy from the previous slide. But lovely how collide collides with the sum. Uh almost a literal copy. This now is slightly different, right? This is the condition from universal hash function. It looks almost the same, but here's the little C. It's a lesser equal and there's the fall. The right hand side is the same. We analyze again the expected length of our uh separate chaining chain. This is for a key X I is the sum of all the other keys that also hash to the same bucket that it collides with by linearity of the expectation. I could pull the expectation inside the sum. Then the expectation of an indicator random variable is its probability of happening. And that one I can by uh equal distribution or I can I can plug in the definition and now I can use my universality and uh lo and behold I get essentially the same upper bound as before except there this there's this factor C but if C is one then it's literally the very same thing. Okay and it's chosen to make exactly that happen. So it's the same analysis. The only thing that changed is that this expectation which is hidden in the notation is over an entirely different object. Previously we used to take the expectation over the values that are inserted into the hash table and now we take the expectation over our random choice of this function.

7:29 But that's great. This means we get the same guarantee for our hash table as previously. Just now we have full control over what happens and we can let even an adversary pick the data. That's good. One catch, we need such a family of hash functions. And maybe we've defined an a very lovely notion that doesn't even exist and then we're back to square one. Uh sometimes this happens, but of course here it doesn't happen. First of all, there's a trivial example of a universal family of hash functions. You can just take all functions, all thinkable functions, all mappings from the universe to uh the slots 0 to m minus one. If you pick that uniformly at random, then well, the hash values indeed are truly random. And so each individual one if if you fix one specific value of the universe and pick your random hash function the distribution of that slot is is literally uniform and independent of all others. Question.

8:39 >> Yes. in the bucket how many This is depending on the hash function. Uh but I take the expectation over the hash function. So it's an average, right?

9:22 >> Well, this is uh um um I'm taking the expected length of a list and which list is also random because it depends on age. But it turns out it doesn't matter which list we look at, right? Because this is also uniform.

9:43 >> No, L is just a name. L is length uh of the list or L for list, I don't know. uh li I is the number of keys in bucket I and then the subscript here is not a fixed I but rather whatever x i hashes to is a bit yeah that's right h is the hash function is a bit uh sneaky because here this quantity is depends on on age in that sense u But once you're on this side, it doesn't more than via the collision probability.

10:35 Okay. Do we even have such families of hash functions? Well, the family of all half of all functions satisfies this. So, it is perfect. It is one universal. Uh the problem here is that this is too rich a family. We want our hash function not just to have good properties of being random. We also want to be able to store it and evaluate it. The thing that's now uh an added an added thing we have to do now that we pick a random function, we also have to store which one we picked otherwise we're uh unable to retrieve our data. So that means we have to write down which function we used. And here there's just too many. This uh the number of of functions here is is essentially m to the power u and u is humongous and it's in the exponents is really bad. This is uh very expensive. Uh so you would need log of that many bits, right? So u * log m bits.

11:40 In other words, you have to write down for every darn element of the universe which element it h which which bucket it hashes to. That entirely defeats the purpose of hashing. So that that won't work and it's also slow to evaluate.

11:57 What we really need is a small family of hash functions only big enough to make this um collision probability trick work. So ideally it should fit in a constant number of words and be fast to evaluate. Maybe that's asking for too much now. But let's see some examples on the positive side of what is what is doable. The first one is a bit esoteric and even if you've seen universal hashing before it's unlikely that you've seen this example, but I I kind of like it because it's it's distilling the essence of what this is about. And then the other are a bit more um practical or a bit more typical. So the assumptions here are a bit awkward. The first one's fine. Um we say the hash table has the size of a prime number. Um again if you're worried about this uh there's uh Bertron postulate which is is really just a theorem that there's always a prime between n and 2n and you can also efficiently find it. So if you have a target size, you want your table to be roughly a certain size. You can always make it a prime by making it at most twice as big. So that's not the problem. The second assumption is a bit awkward. You assume the universe is not your zero to a power of two but some some power of the uh hash table size.

13:35 And this is um a bit inconvenient. You can however always assume you make your universe a bit larger and you just don't use some parts of it. That is fine. So that's that's um used in the calculation. So remember this.

13:52 Now um with this weird universe we can say every value in the universe can be read as a vector namely uh r entries written as a base m uh number which with digits between 0 and m minus one. So I write this in this angle bracket notation to indicate this is a bit like a vector and we'll use it like a vector because now we can define our hash functions as inner products modulo m. So um it's it's written down what this is right this is nothing but summing up uh the well the the uh digit wise multiplication of of these numbers and then adding things up. It's a bit like uh you do a pointwise multiplication of the digits and then you do sum of digits and all of this modulo m because we need a number between 0 and m minus one. This is a bit bonkers but it it works so why not and it has this uh it has this nice symmetry that makes the analysis a bit cleaner and uh these are the hash functions we look at. So the hash functions have a a parameter x. That's the the variable that we evaluate the function at. But it has a second it's completely symmetric of course in a and x, but it has a second parameter that is fixed. So I have one function h a for every value a in the in the universe.

15:29 Now um the size this this still sounds a lot one function for every value in the universe but this is way smaller than what we had before. Before u was in the exponent okay now it's just u so we can uh in log u bits store such a function by just writing down the value a and that is one entry of our universe. So it's it's a number and that's it. Then you know the function and you can also implement this this calculation in constant time with maybe with a little bit of tricks but in principle it's easy.

16:05 Okay. So it is it is a good family subject to this slightly awkward assumption about the universe size. It's a it's a practical choice for a hash function. And um we'll show that this family of hash functions is indeed one universal. So what we have to do for this is where arbitrary values x and x prime show that the collision probability under a random choice from this from this hash function family is 1 / m precisely.

16:35 Okay. So let x and x prime different values be arbitrary but fixed now. uh we try to show here's already rewritten a bit with the knowledge of h picking a random hash function should send these to the same bucket with only a probability of 1 / m and uh the random thing here the hash function has this parameter a it's it's essentially randomizing over this value a now let's uh take these two values apart both of them are from our universe from this m to the r so they both are two vectors of size r of um digits up to m right and these are by assumption not the same vector. So if two vectors are different one component is different at least. So there is a an index d where the two components are different. Okay. Now because m is a prime this uh modulo m field is well taking the numbers modulo m with addition and multiplication gives a field that's classic uh algebra and number theory that's where where you use all this stuff you learned in first year uh which means in operating under modulo m there are multiplicative inverses for every nonzero row value there is another value between 0 and n minus one so that the two multiply to one that's what multiplicative inverse means and you can say is this the equivalent of um in the real numbers the reciprocal is the uh um multiplicative inverse and we write it in the same notation but here it's actually an integer they multiply to one modulo m okay that's that's essentially all the uh all the math knowledge that we need for this. Now let's calculate. We want the probability that these two are the same or two vectors where we know at least one component is different. Right? This was the uh assumption. Well, this is plugging in what the hash functions were defined like they sum up these element wise multiplications of the digits modulo m. So when is that the same?

18:59 Well, we know uh so this is a bit of um notation now. So we write this a subscript not equal d. Uh we don't need that here yet, right? Okay. So here I've just um split this up. there's this one um special index d where I know this whole thing is this is equal to this. I'm just rearranging this equation. I move all the indices where d is involved to the left. So I have the a d which is the same on both sides and then xd minus xd prime. And this should be the same as well the sum of all the other digits that are left with the same subtraction. [clears throat] Okay, not more has happened here. Now what we're using here is that this is not zero because this is the one component that we know for sure the one index where the two vectors differ. So it's some number in our field that is not zero. So it has a multiplicative inverse and we can multiply that to the other side so that we get a d equals this multiplicative inverse times whatever this awkward sum evaluates to.

20:25 The the thing is we don't care what this ugly term is. Um all we need is that it is some value that depends on x and x prime and the a not equals d. So all the components of a from our hash function that are not equal this index d. Well, and if you look at that, that's an equation over uh a vector a that says one of the components is related to some function of the other components.

21:01 So let's rewrite that a bit. Um and here this is the innermost thing that has hasn't been changed. Now let's take uh the law of total probability says here I'm taking one probability over the entire vector A. But because I'm I'm choosing this vector a uniformly at random, I can also first uh randomize over one component keeping all the others fixed and then take the expectation over the others. That's what the law of total total probability means. And so here um I condition the inner part the inner probability on all the components that are not ad and then I take the expectation over those afterwards.

22:01 And then um this inside here this is now a constant for the calculation of this probability. Nothing there depends on on anything random. Whereas this is one value that is uniformly chosen. So this is going to have probability 1 / m to be true. And then I'm taking the expectation over these a not equals d, but they don't even occur anymore.

22:30 Maybe you could have shortcircuited at this point. It's um it's an equation that relates one out of these um one out of the uh independent variables to some combination of all the others. And because this one's uniformly no matter what value this one takes, it's going to be uniform one over m chance. So you get even an equality here, not just the lesser equal that we needed to show. Yeah.

23:05 Uh, what do you mean by memorize the theorem? I think this one is fair to ask. Like, uh, there's there's nothing really bad in there. Um there won't be an exam question that says uh what was line five on slide 56 in unit 3 or four. That's unlikely. Uh but the essence of such calculations with probabilities that's fair game I think and universal hashing as a concept also this is zooming out of the specific construction. I think this is uh maybe is not the notationally cleanest. If I look at the slide from a bit further away, it looks a bit scary, but it is rather clean in what is what is happening and the calculation is not very nasty.

24:12 The more traditional version of universal hashing is this one. Uh, it's a different way to construct yet a yet another family of universal hash functions. I think this is slightly less clean and a bit more messy. It's maybe a tad more practical, but you know, not all that much. Um, I'll I'll have a comment on on the next slide about what is often used in practice instead. So um here we again have that uh we have some prime number p that we fix larger than the universe size and we have um m the size of the table smaller than that. Then we define this um this family of hash functions hpm as again some family of functions with now two parameters a and b. A and B are two numbers uh all between well A between one and P and B between zero and P minus one. And the function now is this linear concurrential function that maybe if if you've seen any you've seen this one. You take your value X that you want to evaluate. You multiply it by A.

25:24 You shift it by B and then take modulo this prime number. And then afterwards modulo m as well because you need it to be in the slots of your hash table. That's what this double modulo is a bit inconven more inconvenient. Uh but this also works and it turns out this is also one universal but uh requires a bit more of a careful look to see why it's indeed one universal. Uh this proof I would say is not as essential for me because it's it exploits a very clever trick but it seems a bit brittle in that it works here and is a bit hard to generalize. I I still think it's worthwhile seeing. Uh so same structure we start with two values in the universe not equal and we have to show that uh the under a random choice of these parameters A and B the collision probability is small. So um first of all we write let me go back once uh we write the hash values or almost the hash values R and S. This is the inner inner part right ax + b mod p and a y + b mod p but without the outer modulo m. So this is a the p s pseudo hash if you want.

26:55 Now um if r is not the same as s then r minus s is if you rewrite it using these uh definitions is a * this difference x - y and um because x and y are different this um also is not zero because uh it's It's a field again and so there's no zero divisor.

27:28 So R and S are not the same. Okay, if X and Y are not the same. That's the first observation. And furthermore, if you look at the two random parameters of your function A and B, this mapping from those random parameters of the function to these pseudo hash values R and S, that turns out to be a bjection onto the uh P * P minus one possible pairs of R and S that are not equal. And that's the brittle part that I think is is rather clever, but doesn't generalize as well. And um so you can uh this again you you see this from that this is a bjection you see this from just expressing a and b in terms of rns right you can you can get rns from a and b like this it's written here and there's an inverse function uh which you get from this again here using that x x - y is not zero because they're different so there's is a multiplicative inverse.

28:44 Okay, I think verifying every individual line may be okay. I think this is a bit a bit harder to see uh to not get lost in the forest.

28:54 What this means is that if I take my A and B the parameters of my hash function uniform this I do by assumption universal hashing then uh I get mapped to this is what this picture is trying to show I get mapped to some some random cell in this in this grid that is not the diagonal. So what what do you what do you see here? Um here on the x-axis is r then here you have s. So you see every cell is one of these RS pairs, but the diagonal is forbidden because they're they would be equal and we know they're not. And um choosing A and B uniformly at random because there's a bjection to these RNs means you pick one of the cells uniformly at random.

29:43 Okay, forget about the colors that's um coming up now. uh we get a collision if and only if these two are the same modulo m. Okay. Now um [clears throat] m you don't see in this picture. Uh this is going from 0 to p minus one. 0 to p minus one. And m is some smaller number smaller than p.

30:24 Now if you look at a certain column R, so uh fix fix a value for R, then that is some residue class of of uh taking um if if you take now this the pseudo hash and apply modulo m which you need for the the actual hash hash table then uh you get at most p divided by m rounded up cells. We have m cells in total that we want to fill and we start with p of the p of of the entries here. Column has p uh rows and you divide that by m. It may not evenly divide if you do modulo. So you get this rounding up for um maybe sometimes having an extra an extra cell in this row but one of them is the diagonal and that is not possible for our random choice.

31:34 So we get at most P divided M rounded up minus one of these that are shaded in the sense that they're corresponding to a collision.

31:46 And that means your probability of if you start with random A and B values any of the uniformly chosen P * P minus one possible pairs there's only um bounded by this P. This is counting good versus bad, right? The the collision means you have free choice for the first value that's for the column and then at most P minus one over M choices for the red cells in that in that column divided by all possible pairs and that works out again to be 1 / M. This is a bit magic because it happens to be that the the diagonal just cancels out and this the cleverness is in this observation with the bjection and if you um apply the same proof and forget the diagonal this is the way how I learned it originally you get also universality but with a larger constant you don't get one universal you get four universal but the calculation is even more ugly it's just uh less insightful.

32:56 So, um I was rather motivated to show this to you, but I think this is on the edge of being a bit too uh specific. Okay, what you should keep in mind is is the statement here. I think the statement is is valuable because it's the historically first to my knowledge that achieves this and is is still reasonably practical.

33:26 Um moving on to practical and now I'll skip the proof entirely is this class of um hash functions. So here um we have w bit keys. W bit means I now have everything between 0 and 2 to the w minus one which is much closer than to what we really want. Right? And also the hash table is a power of two. That's finally now we're talking business. Powers of two is what we know and what we like. And you can build a hash a hash a universal family of hash functions based on that by taking these functions h zed where zed is again a random number but it needs to be an odd number. Okay, I can do that. Right? Take a uniform one and flip the last bit. Um and then you take z * x but you have this modulo and division just with powers of two. So you have this one multiplication that you have to do but then these modulo and division steps these are just bit shifts on an on binary architecture. That's what makes this this hash function much faster.

34:35 And uh the result is slightly worse. is only two universal, not one universal. But this is really harmless. Okay, so that's the most practical of these hash families. Um unlike Java, uh Python does do some randomization. Um in the end they've modified the uh the theoretical construction to do something a bit more uristic but it's in in spirit not so far away from this.

35:13 Okay, coming up for for air from from this deep dive. We've seen with hashing with universal hashing, you can take an average case where you had to hope that the input values are are good into an expectation for the worst case inputs where the expectation is over something you you control, namely the random choice of your hash function. Now, we'll see this this pattern again or you've seen it before with quicksort. With hashing, it's it's a little more intricate, but the very same principle applies. And you should probably just always do this and not not fall back to binary search trees.

35:53 Note that the total running time, universal hashing or not, is still amortized because you double the hash table when you run when you run out of space. Uh we've seen tricks how to deamortize doubling arrays. There's tricks how to deamortize hashts as well. I decided not to go into detail there. Um maybe you can believe that these exist after you've seen one example of deamortization. Um there's more clever ways than that, but uh let's ignore that. Um so for now still amvertised but this is the fastest you can get in terms of typical access speed for a dictionary where you don't need the sorted operations and it's still a rather simple operation. Uh the space you could say is a bit use wasteful because we have either we need open addressing a large table or we need space for the pointers in our bucket list and certainly the worst case um for all operations it remains but we can get the expected case down. Um in worst case it's still linear.

37:09 Okay. Uh here's a final overview of various methods that um we didn't all discuss like this is this is a citation um for overview. What we've looked at is separate chaining this first row and um we've seen that we can get these kind of search and uh and insertion crosses etc as an expectation over our randomness. What we didn't look into in detail are all the options for open addressing. There um you have the choice of if you collide with someone which other position do you try? Linear probing says oh just try the next one and as soon as you find the first one that's free that's yours. Quadratic probing says oh do that but always jump in doubling steps so that you're not all bunching up together. And then there's variations of that. um that uh decide when when you find a spot do you take it or do you bump the element that's there further on let's um this I think is only for your information this I wouldn't ask you in the exam about the details other than that these things exist uh cuckoo hashing is a kind of separate fun idea where you have more than one hash table You start with D hashts from the start and every element every universe uh element in the universe has a position in each of those hashts and you're always going to try those position this is single position in each of the d hash tables and nothing else and then there's uh randomized guarantees that if this d is maybe two or three or four you can set up this hash table so that with large probability You're never going to run out of space for the elements. One of the D slots will always work.

39:12 And if that ever fails, you have to rebuild the entire thing. But once you have it built and once you handled your insertions, any search has to check depositions at most. And if the element is not there, it's not there. So cuckoo hashing turns for lookups the read operations into worstase constant time.

39:33 That's what's what's written here. Um, again, you don't need to need to know more than this vague vague idea. Okay. Uh, same this this comment on Robin Hood hashing. Um, for for the experts that want to know more, uh, we can maybe dig into this some some point offline. Uh, I think is is cute to know but not necessary to pass here. uh some some more tricks and more modern uh improvements you can find in our uh master modules but uh I'll leave it with that here.

40:21 I'll zoom out further. Um we started this chapter by saying ah can we do better than binary search trees and we found kind of yes with hashts. Um but both have their place because balanced binary search tries easily give you worst case cost whereas hashts you have to pull a lot of levers to get there and you don't need any uh special assumptions. You don't need to know about prime fields and so on. Maybe that's good. [snorts] Um also very predictable predictable because of this worst case. uh more crucially maybe they support these additional operations uh rank select ceiling floor or ordering operations that hashts just cannot support sensibly. Uh the benefits of hashts is of course the only data structure really that gives constant time symbol table operations uh under some randomized in some sense.

41:15 Okay.