So, in this video, we're going to start reasoning about the performance of hash tables. In particular, we'll make precise this idea that properly implemented they guarantee constant time lookup. So, let me just briefly remind you of the road map that we're in the middle of. So, we observed that every fixed hash function is subject to a pathological data set and so exploring the solution of making a real time decision of what hash function to use. And we've already gone over this really quite interesting definition of universal hash functions and that's the proposed definition of a good random hash function. More over, in the previous video I showed you that there are simple such families of hash functions. They don't take much space to store, they don't take much time to evaluate. And the plan for this video is to prove formally, that if you draw a hash function uniformly at random from a universal family of hash functions, like the one we saw in the previous video, then you're guaranteed expected constant time for all of the supported operations. So, here's the definition once more of a universal family of hash functions. We'll be using this definition, of course, when we prove that these hash functions give good performance. So, remember, we're talking now about a set of hash functions. These are all of the conceivable real time decisions you might make about which hash function to use. So, the universe is fixed, this is something like IP addresses, the number of buckets is fixed. You know that's going to be something like 10,000, say, and what it means for a family to be universal is that the probability that any given pair of items collides is as good, as small as with the gold standard of completely perfect uniform random hashing. That is for each pair xy of distinct elements of the universe, so for example, for each distinct pair of IP addresses, the probability over the choice of the random hash function little h from the family script h is no more than one over n, where n is the number of buckets. So, if you have 10,000 buckets, the probability that any given pair of IP addresses winds up getting mapped to the same bucket is almost one in 10,000. Let me now spell out the precise guarantee we're going to prove if you use a randomly chosen hash function from a universal family. So, for this video, we're going to only talk about hash tables implemented with chaining, with one length list per bucket. We'll be able to give a completely precise mathematical analysis with this collision resolution scheme. We're going to analyze the performance of this hash table in expectation over the choice of a hash function little h drawn uniformly from a universal family script h. So, for example, for the family that we constructed in the previous video, this just amounts to choosing each of the four coefficients uniformly at random. That's how you select a universal, that's how you select a hash function uniformly at random. So, this theorem and also the definition of universal hash functions dates back to a 1979 research paper by Carter and Wegman. The idea of hashing dates back quite a bit before that, certainly to the 50s. So, this just kind of shows us sometimes ideas have to be percolating for awhile before you find the right way to explain what's going on. So, Carter and Wegman provided this very clean and modular way of thinking about performance of hashing through this universal hashing definition. And the guarantee is exactly the one that I promised way back when we talked about what operations are supported by hash tables and what kind of performance should you expect, you should expect constant time performance. As always, with hashing, there is some fine print so let me just be precise about what the caveats of this guarantee are. So, first of all, necessarily this guarantee is an expectation. So, it's on average over the choice of the hash function, little h. But I want to reiterate that this guarantee does hold for an arbitrary data set. So, this guarantee is quite reminiscent of the one we had for the rand omized quick sort algorithm. In Quicksort, we made no assumptions about the data. It was a completely arbitrary input array and the guarantee said, on average over the real time randomized decisions of the algorithm, no matter what the input is, the expected running time was in log in. Here we're saying again, no assumptions about the data. It doesn't matter what you're storing in the hash table and expectation over the real time random decision of what hash function you use, you should expect constant time performance, no matter what that data set is. So, the second caveat is something we've talked about before. Remember, the key to having good hash table performance, not only do you need a good hash function which is what this universality key is providing us but you also need to control the load of the hash table. So, of course, to get constant time performance, as we've discussed, a necessary condition is that you have enough buckets to hold more or less the stuff that you're storing. That is the load, alpha, the number of objects in the table divided by the number of buckets should be constant for this theorem to hold. And finally, whenever you do a hash table operation, you have to in particular invoke the hash function on whatever key you're given. So, in order to have constant time performance, it better be the case that it only takes constant time to evaluate your hash function and that's, of course, something we also discussed in the previous video when we emphasized the importance of having simple universal hash functions like those random linear combinations we discussed in the previous video. In general, the mathematical analysis of hash table performance is a quite deep field, and there is some, quite mathematically interesting results that are well outside the scope of this course. But what's cool, in this theorem I will be able to provide you a full and rigorous proof. So, for hash tables with chaining and using randomly chosen universal hash functions, I'm going to now prove that you do get cons tant time performance. Right, so hash tables support various operations, Insert, Delete and Lookup. But really if we can just bound a running time of an unsuccessful lookup, that's going to be enough to bound the running time of all of these operations. So, remember in hash table with chaining, you first hash the appropriate bucket and then you do the appropriate Insert, Delete or Lookup in the link list in that bucket. So, the worst case as far as traversing though this length list is if you're looking for something but it's not there cuz you have to look at every single element in the list and followup into the list before you can conclude that the lookup has failed. Of course, insertion, as we discussed, is always constant time, deletion and successful searches, well, you might get lucky, and stop early before you hit the end of the list. So, all we're going to do is bother to analyze unsuccessful lookups that will carry over to all of the other operations. So, a little more precisely, let's let s be the data set. This is the objects that we are storing in our hash table. And remember that to get constant time lookup, it really needs to be the case that the load is constant. So, we are assuming that the size of s is bigger over the number of buckets n. And let's suppose we are searching for some other object which is not an s, call it x. And again, I want to emphasize we are making no assumptions about what this data set s is other than that the size is comparable to the number of buckets. So, conceptually doing a lookup in a hash table with chaining is a very simple thing. You just hash to the appropriate bucket and then you scan through the length list in that bucket. So, conceptually, it's very easy to write down the what the running time of this unsuccessful lookup is. It's got two parts. So, the first thing you do is you evaluate the hash function to figure out the right bucket. And again, remember we're assuming that we have a simple of a hash function and it takes constant time. Now, of course, the magic of hash functions is that given that this hash value, we can zip right to where the lenght list is to search for x using random access into our array of buckets. So, we go straight to the appropriate place in our array of buckets and we just search through the list ultimately failing to find what we're looking for s. Traversing a link list, as you all know, it takes time proportional to the length of the list. So, we find something that we discussed informally in the past which is that's the running time of hash table operations implemented with chaining is governed by the list lengths. So, that's really the key quantity we have to understand. So, lets call this, lets give this a name, Capital L, it's important enough to give a name. So, what I want you to appreciate at this point is that this key quantity, Capital L, the list of the length in x's bucket is a random variable. It is a function of which hash function little h, we wind up selecting in a real time. So, for some choices of our hash function, little h, this list length might be as small as zero but for other choices of this hash function h, this list, list length could be bigger. So, this is exactly analogous too in Quicksort where depending on the real time decision of which random pivot element you use, your going to get a different number of comparisons, a different running time. So, the list length and hence the time for the unsuccessful storage, depends on the hash function little h, which we're choosing at random. So, let's recall what it is we're trying to prove. We're trying to prove an upper bound on the running time of an unsuccessful lookup on average, where the on average is over the choice of the hash function little h. We've expressed that this lookup time in terms of the average list length in x's bucket where again the average is over the random choice of h. Summarizing, we've reduced what we care about, expected time for lookup to understanding the expected value of this random variable Capital L, the average list length in x's bucket. So, that's what we've got to do, we've got to compute the expected value of this random variable, Capital L. Now to do that, I want to jog your memory of a general technique for analyzing expectations which you haven't seen in awhile. The last time we saw it, I believe, was when we were doing the analysis of randomized Quicksort and counting its comparisons. So, here's a general decomposition principle which we're now going to use in exactly the same way as we did in Quicksort here to analyze the performance of hashing with chaining. So, this is where you want to understand the expect, expectation of random variable which is complicated but what you can express as the sum of much simpler random variables. Ideally, 0,1 or indicator random variables. So, the first step is to figure out the random variable, Capital Y, it's what I'm calling it here that you really care about. Now, we finished the last slide, completing step one. What we really care about is Capital L, the list length in x's bucket. So, that governs the running time a bit unsuccessful Look up, clearly that's what we really care about. Step two of the decomposition principle is well, you know, the random variable you care about is complicated, hard to analyze directly but decompose it as a sum of 0,1 indicator random variable. So, that's what we're going to do in the beginning of the next slide. Why is it useful to decompose a complicated random variable into the sum of 0,1random variables? Well, then you're in the wheelhouse of linear of expectations. You get that the expected value of the random variable that you care about is just the sum of the expected values of the different indicator random variables and those expectations are generally much easier to understand. And that will again be the case here in this theorem about the performance of hash tables with chaning. So, let's apply this three-step-decomposition principle to complete the proof of the Carter-Wegman theorem. So, for the record, let me just remind you about the random variable that we actually really care about, that's Capital L. The reason that's a random variable is that because it depends on the choice of the hash function, little h. This number could vary between zero and something much, much bigger than zero, depending on which each you choose. So, this is complicated, hard to analyze directly, so let's try to express it as the sum of 0,1 random variables. So, here are the0,1 random variables that are going to be the constituents of Capital L. We're going to have one such variable for each object y in the data set. Now, remember this is an unsuccessful search, x is not in the data set Capital S. So, if y is in the data set, x and y are necessarily different. And we will define each random variable z sub y, as follows. We'll define it as one if y collides with x under h and zero otherwise. So, for a given zy, we have fixed objects x and y So, x is some IP address, say, y is some distinct IP address, x is not in our hash table, y is in our hash table. And now, depending on which hash function we wind up using, these two distinct IP addresses may or may not get mapped to the same bucket of our hash table. So, this indicates a random variable just indicating whether or not they collide, whether or not we unluckily choose a hash function little h that sends these distinct IP addresses x and y to exactly the same bucket. Okay, so, that's zy, clearly by definition, it's a 0,1 random variable. Now, here's what's cool about these random variables is that Capital L, the list length that we care about decomposes precisely into the sum of the zy's. That is, we can write capital L as being equal to the sum over the objects in the hash table of zy. So, if you think about it, this equation is always true, no matter what the hash function h is. That is if we choose some hash functions that maps these IP address x to, say, bucket number seventeen, Capital L is just counting how many other objects in the hash table wind up getting mapped to bucket number seventeen. So, maybe ten different ob jects got mapped to bucket number seventeen. Those are exactly the ten different values of y that will have their zy equal to1, right? So, so l is just counting the number of objects in the data set s that's collide with x. A given zy is just counting whether or not a given object y in hash table is colliding with x. So, summing over all the possible things that could collide with x, summing over the zy's, we of course get the total number of things that collide with x which is exactly equal to the number, the population of x's bucket in the hash table. Alright, so we've got all of our ducks lined up in a row. Now, if we just remember all of the things we have going for us, we can just follow our nose and nail the proof of this theorem. So, what is it that we have going for us? Well, in addition to this decomposition of the list length in to indicate random variables, we've got linear expectation going for us, we've got the fact that our hash function is drawn from a universal family going for us. And we've got the fact that we've chosen the number of buckets and to be comparable to the data set size. So, we want to use all of those assumptions and finish the proof that the expected performance is constant. So, we're going to have a few inequalities and we're going to begin with the thing that we really care about. We care about the average list length in x's bucket. Remember, we saw in the previous slide, this is what governs the expected performance of the lookup. If we can prove that the expected value of capital L is constant, we're done, we've finished the theorem. So, the whole point of this decomposition principle is to apply linear of expectation which says that the expected value of a sum of random variables equals the sum of the expected values. So, because L can be expressed as the sum of these zy's, we can reverse the summation and the expectation and we can first sum over the y's, over the objects in the hash table and then take the expected value of zy. Now, something which came up in our Quicksort an alysis but which you might have forgotten is that 0,1 random variables have particularly simple expectations. So, the next quiz is just going to jog your memory about why 0,1 random variables are so nice in this context. Okay, so the answer to this quiz is the third one, the expected value of zy is simply the probability that x and y collide, that just follows from the definition of the random variable zy and the definition of expectation, namely recall how do we define zy. This is just this one, if this object y in the hash table happens to collide with the object x that we are looking for under the hash function x and zero otherwise, again, this will be, this will be one for some hash functions and zero for other hash functions. And then we just have to compute expectations. So, one way to compute the expected value of a 0,1 random variable is, you just say, well, you know, there are the cases where the random variable evaluates to zero and then there's the cases where the random variable evaluates to one, and of course we can cancel the zero. So, this just equals the probability that zy = one. And since zy being one is exactly the same thing as x and y colliding, that's what gives us the answer. Okay, so it's the probability that x collides with y. So, plenty of that into our derivation. Now, we again have the sum of all the objects y in our hash table and the set of the expected value of zy what's right that in the more interpretable form, the probability that this particular object in the hash table y collides with the thing we are looking for x. Now, we know something pretty cool about the probability that a given pair of distinct elements like x and y collide with each other. What is it that we know? Okay, so I hope you answered the second response to this quiz. This is really in some sense the key point of the analysis. This is the role, that being a universal family of hash functions plays in this performance guarantee. What does it mean to be universal? It means for any pair of objects distinct like x and y in that proof, if you make a random choice of a hash function, the probability of collision is as good as with perfectly random hashing, hashing. Namely at most, 1/ n where n is the number of buckets. So, now I can return to the derivation. What that quiz reminds you is that the definition of a universal family of hash functions guarantees that this probability for each y is at most 1/n, where n is the number of buckets in the hash table. So, let's just rewrite that. So, we've upper bounded the expected list length by a sum over the objects in the data set of 1/n. And this, of course, is just equal to the number of objects in the data set, the [inaudible] of s divided by n. And what is this? This is simply the load, this is the definition of the load alpha which we are assuming is constant. Remember, that was the third caveat in the theorem. So, that's why as long as you have a hash function which you can compute quickly in constant time. And as long as you keep the load under control so the number of buckets is commensurate with the size of the data set that you're storing. That's why, universal hash functions in a hash table with chaining guarantee expected constant time performance.
