The primary topics in this part of the specialization are: data structures (heaps, balanced search trees, hash tables, bloom filters), graph primitives (applications of breadth-first and depth-first search, connectivity, shortest paths), and their applications (ranging from deduplication to social network analysis).
Universal Hashing: Analysis of Chaining [Advanced - Optional]
Loading...
From the course by Stanford University
Graph Search, Shortest Paths, and Data Structures
812 ratings
From the lesson
Week 4
Hashing; bloom filters.
Meet the Instructors
Tim RoughgardenProfessor
Computer Science
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.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
