Video 5-1: Recap (universal) hashing

0:02 In the next unit, we'll leave the world of data structures that take the objects they're working with as black boxes. Which was, in a way, what we've done all the time so far. In particular, the first few units, they lived in the comparison-based model. Everything was some object I could not do anything with except compare two objects and ask which one is smaller. That was the world view. And that's fine, because if you do that, then it's a very generic data structure. You can stick any object in. You can compare almost all kinds of objects according to some criterion. Uh but it's also a bit unrealistic, because after all, computers can only really deal with bits. And a string of bits is kind of an integer. So, in a way, um integer data structures are the real the real thing that we deal with most of the time. I'm overselling a little bit. Um the point here is that it's fairly common that you deal with sets of integers or dictionaries that map integers to something.

1:07 Um at the very least, after applying a hash function, you can turn complex objects into some some set of integers. And um it turns out that you can do our classic dictionary operations way faster if you're dealing with integers.

1:27 Uh that's what we're looking at here. Um there's essentially two parts that are uh somewhat separate. Um maybe um I'll I'll I'll maybe just briefly talk about some lower bounds at the end. Um uh I'll I'll see how how far we get. Um the main two parts is a part about hashing, where the dictionary operations are only look up and insert delete, but I can't do ordered operations. Uh then we'll go back to ordered dictionaries, which for integers also makes sense, right? Integers are ordered by the usual order of lesser small and lesser bigger. Smaller and bigger. Um and I can ask myself, can I do something like a binary search tree, but better? If the keys are all integers. And the answer is a big yes. And it also turns out that these um refined versions here I'll I'll get to these silly names. Uh >> [laughter] >> Um they use the first part.

2:23 So, it is natural to cover that. And since um most of you seem not to have seen this perfect hashing story as well. Uh I think it's it's just a a very nice piece of of computer science.

2:39 Very nice in the sense that when you first hear about a hash function without collision, head scratch, head scratch, how should that be possible? And after you've seen it, you'll say, "Duh, of course." But, yeah. Uh we'll we'll get there hopefully with an aha moment in between. Uh let me set the scene um giving a bit more substance to what I've uh verbally said. Uh we're looking at a symbol table or a dictionary or a map or pick your favorite name for this basic data structure. It stores a key-value mapping. Um you have keys that are associated with some value. Uh you can put these in, so it's just an insert, and you can get them back out. You can delete them, and you can ask whether something is contained. Uh you've seen this many times over, but uh we'll focus here first on the unordered case for the first three parts. Uh where I I can't ask things like uh what is the next smaller element or uh how many are there in the data structure that are larger than myself? These kind of things.

3:43 Um so, only the operations that are listed here. Uh the second thing, standard in data structures, um if you've studied this for binary search trees, maybe as the first thing. Yes, you want to usually use them as a dictionary that maps some keys to some values. All the data structures don't care at all about your values. They're just carried around. So, we'll just look at sets of keys. And uh so, we'll replace these two operations by a generic lookup. And then you can implement gets by just lookup and return if you found the key. And put by looking up the key, which gives you access to the place where it is stored. And there you can update the value if if you uh if you care about uh storing a different value.

4:37 And uh you can call you can call insert if the key is not stored yet. That means for us um what we're dealing with are essentially sets of integers.

4:51 And you may also know that whenever you were not interested in these sorted dictionary operations, anything that offers these on top is a bit extra expensive, and hashing can beat these. Hashing has its own problems. Uh you always need to carefully check what the guarantees are. It's usually going to be some sort of randomization, or at least you have a probabilistic guarantee that you have to believe in. Uh but uh uh the the benefit is that you could potentially have constant time queries.

5:31 So, let's look at uh hash tables. And the first part will be essentially um recovering some basics you've you've probably seen, but let me uh set the notations so that we can use that in the second part as well. Um From a practical perspective, often times there's two types of hash functions that you may use. There's uh say in Java, you have classes and objects that have a hash code method that takes some arbitrary object and returns some weird bit string or it returns an integer, but uh in a way it's not bounded by anything. In particular, it's not between zero and the size of some hash table. Uh for one, because hash code doesn't even know about hash tables. All it does is takes an object and turns it into an integer. In hopefully a way that is okay for the hash table, whatever that means, right? So, the hope is that at least different objects get a different code and not too many different objects get the same code.

6:32 Inevitable in general, but we try to be uniform. That's the first type of hash function, and I'm here already assuming that this hash function has been applied already. There's going to be a second hash function, where now the input is an integer already. The hash code of some object. Maybe we can say hash code and hash function.

6:56 Not not great, maybe. Um keep in mind that whenever I'm talking about integers here, this could be because you took some arbitrary objects and applied hash code. But then we need a second hash function within a hash table to map from this still fairly large integer to this relatively small number of buckets that you're dealing with. That's what the notation is getting at. We have a universe, that's the hash codes that we get as input, integers of a fairly large range. Um we'll usually assume that this this range is identical to the word size of the computer, which happens to be true in Java, right? Hash code returns an int, and that's the 32-bit that I allegedly can deal with in constant time. Then um this capital S is a subset of this universe. That's the actual set we're trying to store. That's our our dictionary. And in general, this is dynamic. I can add and remove elements from this set.

7:56 And little n is the current size. And if we need to denote these elements, they're x1 up to xn. As already mentioned, a hash table um for me consists of of a number of buckets. The number is m. And then you can think of the hash table at the first level of abstraction, it's just an array where you use the the hash value of some object as the index in the array. Which means an element x is stored at this position. Where don't treat this hash table necessarily as just an array of elements. Uh this h t of h x could uh in general be a secondary data structure. Maybe a linked list, then you have chaining hashing. Or like in Java, do you know what hash map does in Java? Uh it's essentially linked uh linked uh and the chain chaining hashing. So, you have a a small number of relatively small number of buckets, say half of the number of elements you expect or so.

9:03 >> [snorts] >> Um and then they have a linked list for the buckets. But then they've um added an optimization. When the number of elements in this linked list where the the number of elements that hash to the same bucket exceeds some magic threshold, namely eight, uh they switch over to a binary search tree. And so, then the buckets are maintained in a binary search tree. Which means even if you have a worst-case hash function because stupid programmer didn't know what they're doing, hash code equals return 42, right? Uh then you still get logarithmic performance as opposed to linear.

9:43 Okay. Yeah. >> [snorts] >> Uh, that's if the same person teaches algorithm data structures at the same time. You learn these things by heart. Um, another another option you have in principle with hashing is that this this array can can just store a single element at each position. But then maybe not every element gets to live at its its desired location of H of X, but has to maybe move a bit in the array. That's open addressing hashing. Uh, these are the two classical options you have how to deal with collisions. Because we'll usually have to live with uh, collisions if two elements in the universe have the same hash value. That's why you even need any of these.

10:33 Um, here I'm I'm cutting a a discussion short that one usually does in some undergrad module that eventually collisions are inevitable. There's the combinatorial argument that the universe is much bigger than M. Um, but also in you can you can quantify this more with the birthday paradox that even if everything is is nicely and uniformly chosen and random and so on and so forth. Uh, you need an extremely large uh, hash table compared to your number of elements to have no collisions. Roughly roughly without so uh, you know the birthday paradox. How many people do you need in a room until with probability 50% there's two people having the same birthday? Assuming that you know, kids are born uniformly throughout the year, which we all know is not quite true.

11:31 Roundabout so there's Let's Let's not No no uh leap years during the 65 different birthdays. Suppose they're uniform, how many people do I need roughly so that 50% chance uh two have the same birthday.

11:53 I think it was roughly a small school class, maybe 25, something like this. You can of course I didn't put a a very large um I'm I haven't computed this again. Um I'm doing the full details in advanced algorithms if people want to see it.

12:43 So, um we don't we don't need the precise formula. Um But if you have M buckets and N people, then the the rough value you need for this it should be around two square roots the number of buckets. So, uh Does that check out here? Um I'm not good at uh mental calculations. Uh it's also asymptotics, so maybe I can be excused either way. Uh again, this is you can just calculate this, but it's it's not directly relevant for what what follows. Just keep that uh in mind roughly. Um we'll do a different calculation instead. So, with usually half to half collisions especially if we uh if we maybe fix the set, then I'll show you in the next section how to avoid this. But in general, if if you keep inserting and deleting, there's no way you're going to avoid collisions all the time. In particular, for a fixed hash function, no no chance, right?

13:53 So, any implementation that does that, pick a fixed hash function >> [clears throat] >> uh like Java, right? Uh it's inevitably going to have a worst-case input. Because I can always find uh by pigeonhole principle, I can find objects in in in theory that have the same hash code. Uh maybe you've done this this fun game with Java strings. You can you can crash hash map. Although not as badly anymore because of this binary search tree fallback. Uh but you can find different strings that all have the same hash code, and that's not going to change as as long as you stick with a fixed hash function, this is inevitable. So, from algorithms perspective, really what you want to do, same as for quicksort, even though there again people in practice are very reluctant to have non-deterministic behavior, you really want randomization. And here, what you randomize should be the hash function. Um I think from from that perspective, quite obvious. You want to pick a random hash function, but now random from what, right? So, you need to fix some family of hash functions because if you allow all possible mappings from the universe to your buckets, there's just too many of them.

15:16 So, uh uh there's a log missing here, right? This is the number of things. So, it's log of that. Uh, it still means it's linear in U. And U is the universe. That's a lot, right? It's 2 to the 64, say. You're never going to finish writing these all down. So, um, taking a random hash function from all thinkable functions is out of the question, just because you can't write it down. So, we have to restrict hashing, uh, the hash functions to some sensible family. And this, maybe you've also seen, uh, classic thing to do is to pick a universal family of hash functions. Uh, you can do many and and much more sophisticated things, but we don't for what I'm uh, showing you in this in this unit, we don't need any of these, uh, more more sophisticated ones. Uh, what we need is the following property. We have a a family H of hash functions, uh, again mapping from the same um, from the universe to the the buckets.

16:30 And, uh, if this function is chosen uniformly at random from this family, then we have this property that two different keys collide with, um, a small small enough probability. And to be precise, if if H was all hash functions, uh, so that's, uh, we're in this perfect, uh, random world, what should we expect for a random hash function and two given keys? The values of these two keys should be uniformly chosen among M. Right? So, uh, for fully random hash function, we would expect that both h of x1 is uniformly distributed among these buckets. And same for x2.

17:40 Uh that's equality in distribution and you the calligraphic U is for the uniform distribution over this this discrete set. If that's the case, you can uh fix any any arbitrary value for h of x1. There's going to be m choices for h of x2 out of which one is bad and all others are good. All others are uh no collision. So, in that case, the probability for a collision will be exactly 1/m.

18:25 Precisely the the thing that uh one would get. Now, we leave a little bit of leeway. We allow a constant factor worse than this 1/m. But we want to restrict the the set of hash functions. That's the game for universal hashing. Uh have you all seen universal hashing? Should I speed up on this or Something of this sort, some definition like this part A.

18:56 Okay, maybe too long ago, eh? Uh Again, I think the definition is very natural, right? Um you would hope that you get 1/m if the function is completely random. Maybe we can't get that quite, but uh with a constant factor overhead. Um there's a stronger notion where um uh you don't just want the collision probability to be small, but really uh all combinations of a value mapping to some some bucket and the other are uh equally likely in a way. We don't really need that stronger notion. Uh I think it's useful to think about pairwise independent as a good name. What is pairwise independent here is the hash values of two fixed keys. X1 and X2 are fixed and so all quantifier. Um but then the random hash function maps them to some random value. And if you do that with two keys and you have this property, that means these two events are pairwise independent.

19:54 That's the that's the goal there. Um we'll essentially just use this first uh this first version. That's good enough for all we need. And now the next question uh that you would asking in after defining this thing is does that exist? Is there any universal family of hash functions? There's the boring one, which is all hash functions, but that's already I already ruled that out as as useless. Uh there's several others known that also are universal and which have the property that they're very little very efficient to store and to evaluate. For example, um the the oldest or the most classic, I think is this first one. And that's what um technically the results I'm showing you use in the original publication. So you use um you use a function that looks a bit like a linear congruential random number generator. Uh you have two values A and B, which are fixed. These are parameters of the function.

21:03 And uh you essentially compute this linear or affine function ax + b but you compute it modulo some prime number. And then we have computed modulo m because we want we force the value to be between 0 and m minus 1 for our bucket index. So this this last step is kind of annoying. We would prefer not to have that. And one option is to set m to p to a prime number, then you can avoid it. But in general you have to do it. Um and then this that's why you have this c equals 2 here. If you didn't have this second step, it would be universal with c equals 1. But uh because you're you're messing up the uniformity a little bit with this modulo step, um you only get this two universal, but it's good enough uh for the the bounds you want. And the important thing about this these functions hab is to store such a function, I only need to store a and b.

22:03 p and m are globally fixed. They're known for the entire hash table. And a and b is the only random thing. Um and to compute the function is also cheap. All right, it's a a bunch of multiplications and divisions. Uh there's an even even better one in practice because it avoids the general multiplication and modulo. It just uses These are it's written as mod and div, but really this is with powers of 2 is just bit shifts. So you can implement these without um any divisions. You have just this one multiplication. And you also have just this one parameter. So it's kind of even cuter. Um it's a bit more modern. I think also mostly German inventors. Uh for some of the things there's a a lot of German authors for uh the following papers. Uh same same for this one. Uh Dietzfelbinger et al.

23:02 So these these families exist and they're not even that complicated. The proof that they satisfy this universality I decided not to do. It's not hard to to do the computation, but I'm at some point we want to move on to using this. So, for now as a black box, you can assume there is such a family of hash functions. Maybe I should should have written this as a little lemma. Um There's such a family of hash functions with a constant number of words I can store one random function. I can evaluate the random function with constant number of word operations. And that's it. That's what we need.

23:48 Okay. Then last bit, then we're going to finish for for this week. Uh How good is this universality? I've defined something and I claimed it's somewhat natural because it's close-ish to what a a totally uniform hash function would do. Uh and there's basically these these two statements. Um that uh maybe you can uh do the proof next time if you haven't seen it before. Um one says that if you sum up the total number of collisions so you have a a set of keys x1 to xn and you use your random hash function from this universal family of hash functions then you can define the number of pairs that's hash to the same position. It's a bit of a weird way of counting, but you'll see that this makes the analysis easier. That's all why we do it that way. So, it's the number of pairs where the hash value is the same. AKA the number of pairwise collisions.

24:51 And that is bounded by this mysterious quantity. I don't know if you have an intuition whether that is good or not. Uh an upper bound for C is clearly n squared or n choose two, because that's the number of pairs overall. And a lower bound is, I guess, uh well, zero would be a lower bound, but that's unrealistic. We have n elements that we distribute among m buckets. So, in the best case, they're going to be evenly distributed, so n divided m elements per bucket. So, n divided m squared is the smallest I can get. And that's per one bucket. I even have to sum this up over the buckets. Right? So, uh C is clearly less than n choose two, but also C will have to be in the best case, uh m divided n squared. And that's for one bucket, or I'm I mean, really, it's m divided n choose two.

26:01 That's the number of collisions inside one bucket. If they're all holding exactly m divided n divided m, I'm sorry. Uh okay. That's the average load of a bucket if everything is uniformly distributed. Say this is an integer, then for each such bucket, I have that many choose two pairs of indices that have the same hash value. And now I have to multiply this by the number of buckets. So, roughly roundabouts choose two is squared, the thing on the top. So, I have n squared over m squared times m squared as m m times m. So, one m cancels. n squared over m is almost the best case. And lo and behold, we have the almost best case up to some constant factor. Okay? So, in a way this is this is decent. We can't do much much better even with a perfectly random or even in the in the best case of distributing evenly.