So now that we understand why we can't have a single hash function which always
does well at every single data set, that is every hash function is subject to a
pathological data sets. We'll discuss the randomize solution of how we can have a
family of hash functions and if you make a real time decision about which hash
function to use, you're guaranteed to do well on average, no matter what the data
is. So let me remind you of the three prong plan that I have for this part of
the material. So in this video, we'll be covering the first two. So part one, which
we'll accomplish in the next slide, will be to propose a mathematical definition of
a good random hash function. So formerly, we're going to define a universal family
of hash functions. Now, what makes this definition useful, well, two things. And
so, part two, we'll show that there are examples of simple and easy to compute
hash functions that meet this definition, that are universal in the sense described
on the next slide. So that's important. And in the third part, which we'll do in
the next video, will be the mathematical analysis of the performance of hashing,
specifically with chaining when you use universal hashing. And we'll show that if
you pick a random function from a universal family, then, the expected
performance of all of the operations are constant. Assuming, of course, of the
number of buckets is comparable to the number of objects in the hash table which
we saw earlier is a necessary condition for good performance. So let's go ahead
and get started and let's say what we mean by a good random hash function. So for
this definition, we'll assume that the universe is fixed. So maybe it's IP
addresses, maybe it's our friends names. Maybe it's configurations of a chessboard,
whatever. But there's some fixed universe u and we'll also assume we've decided on
the number of buckets n. And we call the set H universal if and only if it meets
the following condition. In English, the condition says that for each pair of
distinct elements, the probab ility that they collide should be no larger than with
the gold standard of perfectly uniform random hashing. So for all distinct keys
from the universe, call them x and y, what we want is that the probability if we
choose a random hash function, h, from the set script h, the probability that x and y
collide. And again, just to be clear, what that means is that, x and y hash to
exactly the same bucket under this hash function h, this should be no more than
1/n, and don't forget n is the number of buckets. Again, to interpret this, you
know, 1/n, where does this come from? So, we said earlier that an impractical but in
some sense, gold standard hash function would be to just independently for each
key, assign it bucket uniformly and random with different keys being assigned
independently. Remember the reason this is not a practical hash function is because,
you'd have to remember where everybody went. And then that would basically
require maintaining a list which would devolve to the list solution, so you don't
want that. You want hash functions where you have to store almost nothing and we
can evaluate them in constant time. But, if we throw out those requirements of
small space and small time then, random function should spread stuff out pretty
evenly, right? I mean that's what they are doing. They're throwing darts completely
at random at these n buckets. So what would be the collision probability of two
given keys say, of Alice and of Bob if you are doing everything independently and
uniformly at random. Well, you know, first Alice shows up and it goes to some totally
random bucket, say, bucket number seventeen. Now, Bob shows up. So, what's
the probability that it collides with Alice? Well, we have these n buckets that
Bob could go to, each is equally likely, and there's a collision between Alice and
Bob if and only if Bob goes to bucket seventeen. Since, each bucket's equally
likely, that's only a one in n probability. So really what this condition
is saying, is that, for each pair of elements, the collision probability should
be as small, as good as with the holy grail of perfectly random hashing. So this
is a pretty subtle definition, perhaps the most subtle one that we see in this entire
course. So, to help you get some facility with this, and to force you to think about
it a little deeply, the next quiz which is probably harder than a typical in class
quiz, asks you to compare this definition of universal hashing with another
definition and ask you to figure out to what extent they're the same definition.
So the correct answer to this quiz question is the third one that there are
hash function families h, that satisfy the condition on this slide that are not
universal. On the other hand, there are hash function families H, which satisfy
this property and are universal. So, I'm going to give you an example of each. I'd
encourage you to think carefully about why this is an example and a non-example
offline. So an easy example to show that sometimes the answer is yes, you have
universal hash function families h, which also satisfy this property of the slide,
would be to just take H to be the set of all functions from mapping the universe to
the number of buckets. So that's an awful lot of functions, that's a huge set, but
it's a set nonetheless. And, by symmetry of having all of the functions, it both
satisfies the property of this slide. It is indeed true that exactly a one on one
refraction of all functions, map arbitrary key k to arbitrary bucket i. And by the
same reasoning, by the same symmetry properties, this is universal. So really,
if you think about it choosing a function at random function from H, is now just
choosing a completely random function. So it's exactly what we've been calling
perfect, random hashing. And as we discussed in the last slide, that would
indeed have a collision probability of exactly 1/n for each pair of distinct
keys. So, this shows sometimes you can have both this property and be universal.
An example where you have the property in this slide, but you're not universa l,
would be to take h to be a quite small family, a family of exactly n functions,
each of which is a constant function. So it's going to be one function which always
maps everything to bucket zero, that's a totally stupid hash function. There's
going to be another hash function which always maps everything to bucket number
one, that's a different but also totally stupid hash function, and so on. And then
the end function will be the constant function that always maps everything to
bucket n-1. And if you think about it, this very silly set H does indeed satisfy
this very reasonable looking property on this slide. Fix any key, fix any bucket,
you know say bucket number 31 what's the probability that you pick a hash function
that maps this key to bucket number 31? Well, independent of what the key is, it's
going to be the probability that you pick the constant hash function whose output is
always 31. Since there's n different constant functions, there's a one in n
probability. So, that's an example showing that in some sense, this is not as useful
a property as the property of universal hashing. So this is really not what you
wanted. This is not strong enough. Universal hashing, that's what you want
for strong guarantees. So now that we've spent some time trying to assimilate
probably the subtlest definition we've seen so far in this class, let me let you
in on a little secret about the role of definitions in mathematics. So on the one
hand, I think mathematical definitions often get short shrift, especially in, you
know, the popular discussion of mathematical research. That said, you
know, it's easy to come up with one reason why that's true, which is that any schmo
can come up and write down an mathematical definition. Nobody's stopping you. So,
what you really need to do is you need to prove that a mathematical definition is
useful. So how do you indicate usefulness of a definition? Well you gotta do two
things. First of all, you have to show that the definition is satisfied by
objects of interest. For us right now, objects of interest, are hash functions,
we might imagine implementing. So they should be easy to store, easy to evaluate.
So there better be such hash functions meaning, that complicated universal hash
function definition. The second thing is, is something good better happen if you
meet the definition. And in the context of hashing, what good thing do we want to
have happen? We want to have good performance. So those are the two things
that I owe you in these lectures. First of all, a construction of practical hash
functions that meet that definition, that's what we'll start on right now.
Second of all, why meeting that definition is a sufficient condition for good hash
table performance. That will be the next video. So in this example, I'm going to
focus on IP addresses although the hash function construction is general, as I
hope will be reasonably clear. And as many of you know, an IP address is 32 bit
integer consisting of four different eight bit parts. So let's just go ahead and
think of an IP address as a four two fold, the way you often see it. And since each
of the four parts is eight bits, it's going to be a number between zero and 255.
And the hash function that we're going to construct, it's really not going to be so
different than the quick and dirty functions as we talked about in the last
video although in this case we'll be able to prove that the hash function family is
in fact, universal. And we're again going to use the same compression function.
We're going to take the modulas with respect to a prime number of buckets. The
only difference is we're going to multiply these xi's by a random set of
coefficients. We're going to take a, a random linear combination of x1, x2, x3
and x4. So I'm going to be a little more precise. So we're going to choose a number
of buckets, n, and as we say over and over, the number of buckets should be
chosen so it's in the same ball park of the number of objects you are storing. So
you know, let's say that n should be roughly double the number of objects that
you are storing as initial rule of thumb. So, for example, maybe we only want to
maintain something in the ball park of 500 IP addresses and we can choose n to be a
prime like 997. So here's the construction. Remember, we want to produce
not just one hash function, but the definition is about a universal family of
hash functions. So we need a whole set of hash functions that we're ultimately going
to chose one member from, at random. So, how do we construct a whole bunch of hash
functions in a simple way? Here's how we do it. So you define one hash function,
which I'm going to note by h sub a, a here is a four tuple. The components of which
I'm going to call a1, a2, a3 and a4. And, all of the components of a are integers
between zero and n-1. So they're exactly in correspondence with the indices of the
buckets. So if we have 997 buckets, then each of these ai's is an integer between
zero and 996. So it's clear that this defines, you know, a whole bunch of
functions. So in fact, for each of the four coefficients, that's four independent
choices, you have n options. Okay so each of the integers between zero and n-1 for
each of the four coefficients. So that's fine, not giving a name to end of the four
different functions, but what is any given function? How do you actually evaluate one
of these functions? Just remember what a hash function is supposed to do. Remember
you know, how it type checks it takes as input something from the universe in this
case an IP address, and outputs a bucket number. And the way we evaluate the hash
function h sub a, and remember a here is a 4-tuple. And remember IP address is also a
4-tuple, okay, so each component of the IP address is between zero and 255. Each
component of a is between zero and n-1, so for example, between zero and 996. And
what we do is just take the dot products or the inner products of the vector a and
the vector x, and then we take the modulus with respect the number of buckets. So
that is we take a1 x1 + a2 x2 + a3 x3 +a4 x4. Now of course, remember the
x's lie be tween zero and 255, the ai's lie between the zero and n-1, so say zero
and 996, you know, so you do these form of multiplications now make it a pretty big
number, you might well over shoot the number of buckets n. So to get back in the
range of what the buckets are actually indexed that in the end we take the
module, modulus the number of buckets. So in the end we do output, a number between
zero and n-1 as desired. So that's a set of a whole bunch of hash functions, n to
the fourth hash functions. And each one meets the criteria of being a good hash
function from an implementation perspective, right? So remember, we don't
want to have to store much to evaluate a function. And for a given hash function in
this family, all we gotta remember are the coefficients, a1, a2, a3 and a4. So you
just gotta remember these four numbers. And then to evaluate a hash function on an
IP address, we clearly do a constant amount of work. We just do these four
multiplications, the three additions, and then taking the modulus by the number of
buckets n. So it's constant time to evaluate, constant space to store. And
what's cool is, using just these very simple hash functions which are constant
time to evaluate and constant space to store, this is already enough to meet the
definition of a universal family of hash functions. So this fulfills the first
promise that I owed you, after subjecting you to that definition of universal
hashing. Remember the first promise was, there are simple, there are useful
examples that meet the definition, and then of course, I still owe you why.
Meaning this definition is useful, why does it leave the good performance. But I
want to conclude, this video of actually proving this theorem to you, arguing that
this is, in fact, a universal family of hash functions. Right. So this should be a
mostly complete proof and certainly will have all of the conceptual ingredients of
why the proof works There will be one spot where I'm a little hand-wavy because we
need a little number theory, and I don't want to have a big detour into number
theory. And if you think about it, you shouldn't be surprised that basic number
theory plays at least some role. Like as I said, we should choose the number of
buckets to be prime. So that means at some point in the proof, you should expect us
to use the assumption that n is prime. And pretty much always you're going to use
that assumption will involve at least elementary number theory, okay? But I'll
be clear about where I'm being hand-wavy. So what do we have to prove? Let's just
quickly review a definition of a universal hash function. So we have our set h that
we, that we know exactly what it is. What does it mean that it's universal? It means
for each pair of distinct keys, so in our context it's for each pair of IP
addresses, the probability that a random hash function from our family script h
causes a collision, maps these two IP addresses to the same bucket should be no
worse than with perfectly random hashing. So no worse than 1/n where n is the number
of buckets, say like 997. So, the definition we need to meet is a condition
for every pair of distinct keys. So let's just start by fixing two distinct keys. So
I'm going to assume for this proof that these two IP addresses differ in their
fourth component. That is that I'm going to assume that x4 is different than y4. So
I hope that it's intuitively clear that, you know, it shouldn't matter, you know,
which, which set of 8-bits I'm looking at. So they're different IP addresses. They
differ somewhere. If I really wanted, I could have four cases that were totally
identical depending on whether they differ in the first eight bits, the next 8-bits,
the next 8-bits, or the last 8-bits. I'm going to show you one case, because the
other three are the same. So let's just think of the last 8-bits as being
different. And now, remember what the definition asked us to prove. It asked us
to prove that the probability that these two IP addresses are going to collide is
at most, 1/n. So we need an upper bound on the collision probability w ith respect to
a random hash function from our set of n to the fourth hash functions. So I want to
be clear on the quantifiers. We're thinking about two fixed IP addresses. So
for example, the IP address for the New York Times website and the IP address for
the CNN website. We're asking for these two fixed IP addresses, what fraction of
our hash functions cause them to collide, right? We'll have some hash functions
which map the New York Times and CNN IP addresses to the same bucket, and we'll
have other hash functions which do not map those two IP addresses to the same bucket.
And we're trying to say, that the overwhelming majority, sends them to
different buckets, only a 1/n fraction at most, sends them to the same bucket. So
we're asking about the probability for the choice of a random hash function from our
set h that the function maps the two IP addresses to the same place. So the next
step is just algebra. I'm just going to take this equation which indicates when
the two IP addresses collide over a hash function. I'm going to expand the
definition of a hash function, remember it's just this inner product modulo the
number of buckets n, and I am going to rewrite this condition in a more
convenient way. Alright, so after the algebra, and the dust has settled. We're
left with this equation being equivalent to the two IP addresses colliding. So
again, we're interested in the fraction of choices of a1, a2, a3, and a4, such that
this condition holds, right? Sometimes it'll hold for some choices of the ai's,
sometimes it won't hold for other choices and we're going to show that it almost
never holds. Okay, so it fails for all but a 1/n fraction of the choices of the ai's.
So next we're going to do something a little sneaky. This trick is sometimes
called the Principle of Deferred Decisions. And the idea is when you have a
bunch of random coin flips, it's sometimes convenient to flip some but not all of
them. So sometimes fixing parts of the randomness clarifies the role that the
remaining randomness is going to play . That's what's going to happen here. So
let's go ahead and flip the coins, which tell us the random choice of a1, a2, and
a3. So again remember, in the definition of a universal hash function, you analyze
collision probability under a random choice of a hash function. What does it
mean to choose a random hash function for us? It means a random choice of a1, and
a2, and a3, and a4. So we're making four random choices. And what I'm saying is,
let's condition on the outcomes of the first three. Suppose we knew, that a1
turns up 173, a2 shows up 122 and a3 shows up 723, but we don't know what a4 is. A4
is still equally likely to be any of zero, one, two all the way up to n-1. So
remember that what we want to prove is that at most 1/n fraction of the choices
of a1, a2, a3, and a4, cause this underlined equation to be true, cause a
collision. So what we're going to show is that for each fixed choice of a1, a2, and
a3, at most a 1/n fraction of the choices of a4 cause this equation to hold. And if
we can show that for every single choice of a1, a2, and a3, no matter how those
random coin flips come out, almost a 1/n fraction of the remaining outcomes satisfy
the equation, then we're done. That means that at most of 1/n fraction of the
overall outcomes can cause the equation to be true. So if you haven't seen the
principle of, for these decisions before, you might want to think about this a
little bit offline, but it's easily justified by just say two lines of
algebra. Okay, so we're done with the setup and we're ready for the meat of the
argument. So we have done is, we've identified an equation which is now in
green, which occurs if and only if we have a collision between the two IP addresses.
And the question we need to ask is, for a fixed choices of a1, a2 and a3, how
frequently will the choice of a4 cause this equation to be satisfied? Cause a
collision? Now, here is why we did this trick of the Principle of Deferred
Decisions. By fixing a1, a2, and a3, the right hand side of this equation is now
just some fixed number b etween zero and n-1. So maybe this is 773, right? The xi's
were fixed upfront, the yi's were fixed upfront. We fixed a1, a2, a3 at the
beginning, at the end of the last slide, and those were the only ones involved in
the right hand side. So this is 773 and over on the left hand side, x4 is fixed,
y4 is fixed but a4 is still random. This is an integer equally likely to be any
value between zero and n-1. Now here's the key claim, which is that the left-hand
side of this green equation is equally likely to be any number between zero and
n-1. And I'll tell you the reasons why this key claim is true. Although this is
the point where we need a little bit of number theory, so I'll be kind of
hand-wavy about it. So there's three things we have going for us, the first is
that x4 and y4 are different. Remember our assumption at the beginning of the proof
was that, you know, the IP addresses differ somewhere so why not just assume
that they differ in the last 8-bits of the proof. Again this is not important if you
really wanted to be pedantic you could have three other cases depending on the
other possible bits in which the IP addresses might differ. But anyway, so,
because x4 and y4 are different, what that means is that x4 - y4 is not zero. And in
fact, now that I write this, it's jogging my memory of something that I should have
told you earlier, and forgot, which is that the number of buckets n should be at
least as large as the maximum coeffcient value. So for example, we definitely want
the number of buckets n in this equation to be bigger than x4, and bigger than y4.
And the reason is, otherwise you could have x4 and y4 being different from each
other, but they still, the difference still winds up being zero mod-n. So for
example, suppose n was four, and x4 was six and y4 was ten. Then x4-10 would be
-four and that's actually zero modulo four. So that's getting now what you want.
You want to make sure that if x4 and y4 are different, then they're difference is
non-zero modulo n. And the way you ensure that is that you just make sure n is
bigger than each. So you should choose a number of buckets bigger than the maximum
value of the coefficient. So in our IP address example, remember that the
coefficient don't get bigger than 255. And I was suggesting a number of buckets equal
the same 997. Now, in general, this is never a big deal in practice, if you only
wanted to use say, 100 buckets, you didn't want to use 1000, you wanted 100, well,
then you could just use smaller coefficients, right, you could just break
up the IP address, instead of into 8-bit chunks, you could break it into 6-bit
chunks, or 4-bit chunks, and that would keep the coefficient size smaller than the
number of buckets, okay? So you could choose the buckets first, and then you
choose how many bits to chunk your data into, and that's how you make sure this is
satisfied. So back to the three things we have going for us in trying to prove this
key claim. So x4 and y4 are different, so their difference is non-zero modulo n. So
second of all, n is prime, that was part of the definition, part of the
construction. And then third, a4, this final coefficient is equally likely to
take on any value between zero and n-1. So, just as a plausibility argument, let
me give you a proof by example. Again, I don't want to detour into elementary
number theory, although it's beautiful stuff, so you know, I encourage those of
you who are interested to go learn some and figure out exactly how you prove it.
You really only need the barest elementary number theory to give a formal proof of
this. But just to show you that is true in some simple examples, so let's think about
a very small prime. Let's just say there's seven buckets and let's suppose that the
difference between x4 and y4 is two. Okay, so having chosen the parameters of set n =
seven, I've set the difference equal to two. What I want to do is I want to step
through the seven possible choices of a4, and look at what we get in this blue
circle quantity, on the left hand side of the green equation. So, we want to say the
left hand's equally likely to be any of the seven numbers between zero and six, so
that means that as we try our seven different choices for a4, we better get
the seven different possible numbers as output. So, for example, if we set a4 =
zero, then the blue circled quantity is certainly itself zero. If we set it equal
to one, then it's one two, so we hit two. For two, we get two two which is
four. For three, we get three two which is six. Now, when we set a4 = four, we get
four two which is eight, modulo seven is one. Five two - seven is three. Six
two - seven is five. So as we cycle through a4, zero through six, we get the
value zero, two, four, six, one, three, five. So indeed we cycle through the seven
possible outcomes one by one. So if a4 is chosen uniformly and random, then indeed
this blue circled quantity will also be uniformly random. So just to give another
quick example, we could also keep n = seven, and think about the difference of
x4 and y4. Again, we have no idea what it is, other than that its non-zero. So, you
know, maybe instead of three, maybe, maybe instead of two, it's three. So now again,
let's stop through the seven choices of a4, and see what we get. So now we're
going to get zero, then three, then six, then two, then five, and then one, and
then four. So again, stepping through the seven choices of a4, we get all of the
seven different possibilities of this left hand side. And it's not an accident that
these choices are parameters. As long as n is prime, x4 and y4 are different, and y
ranges over all possibilities, so will the value on the left-hand side. So by
choosing a four uniformly random, indeed, the left-hand side is equally likely to be
any of its possible values, zero, one, two up to n-1. And so, what does that mean?
Well, basically it means that we're done with our proof cuz remember, the
right-hand side that circled in pink is fixed. We fixed a1, a2, and the a3. The
x's and y's have been fixed all along so this is just some number, like 773. And
so, we know that there's exactly one choice of a4 that will cause the left-hand
side to also be equal to 773. Now a4 has n different possible values and it's equally
likely to take one on becaus e only a one-end chance that we're going to get the
unlucky choice of a4 that causes the left-hand side to be equal to 773 and of
course, there's nothing special about 773. Doesn't matter how the right-hand side
comes out. We have only one-hand chance of being unlucky and having a collision and
that is exactly the condition we are trying to prove and that establishes the
universality of this function each of n^4, very simple, very easy to evaluate hash