This sequence of videos are going to take it to the next level with Hash tables and
understand more deeply the conditions under which they perform well, amazingly
well in fact As you know, we've constant time performance for all of their
operations. The main point of this first video is to explain in sense in which
every hash function has its own Kyptonite. A pathological data set for
it which then motivates the need to tread carefully with mathematics in
the subsequent videos. So, a quick review So remember that the whole purpose of a
hash table is to enable extremely fast look ups, ideally constant time lookups.
Now, of course, to have anything to look up, you have to also allow insertions. So
all hash tables are going to export those two operations And then, sometimes, a hash
table also allows you to delete elements from it. That depends a little bit on the
underlying implementation. So certainly when you have it implemented using
chaining, that's when you have one linked list per bucket, it's very easy to
implement deletion. Sometimes, with open addressing, it's tricky enough, you're
just gonna wind up punting on deletion. So when we first started talking about hash
tables, I encouraged you to think about them logically. Much the way you do as an
array, except instead of being indexed just by the positions of an array, it's
indexed by the keys that you're storing. So just like an array via random access
supports constant time look up, so does a hash table. There was some fine print
however with hash tables. Remember there were these two caveats. So the first one
is that the hash table better be properly implemented And this means a couple of
things. So, one thing that it means is that the number of buckets better be
commensurate with the number of things that you're storing in the Hash table, we'll
talk more about that in a second. The second thing it means is you better be
using a descent Hash function. So we discussed in a previous video the perils
of bad Hash functions, and it will be even more stringent with our demands on Hash
functions in the videos to come. The second caveat which I'll try to
demystify in a few minutes is that you better have non-pathological data. So, in
some sense, for ever Hash table there's Kyptonite , a pathological
data set that will render its performance to be quite poor. So in the video on
implementation detail we also discussed how hash tables inevitably have to deal
with collisions. So you start seeing collisions way before your hash table's
start filling up so you need to have some sort of method for addressing two
different keys that map to exactly the same bucket. Which one do you put there? Do you
put both there or what? So there's two popular approaches let me remind you what
they are First called chaining. So this is a very natural idea, where you just keep
all of the elements that hash to a common bucket in that bucket. How do you keep
track of all of them? Well, you just use a linked list. So, in the seventeenth
bucket, you will find all of the elements which ever hashed to bucket number 17.
The second approach which also has plenty of applications in practice is
open addressing. Here the constraint is that you are only going to store one item
one key in each bucket. So if two things mapped the bucket number seventeen, you
gotta find a separate place for one of them And so the way that you handle that
is you demand from your hash function not merely one bucket but rather a whole probe
sequence. So the sequence of buckets so that if you try to hash something into
bucket number seventeen, 17's already occupied then you go on to the next.
Bucket in the probe sequence. You try to insert it there And if it, you fail again
you go to third bucket in the sequence. You try to insert it there, and so on. So
we mentioned briefly the sorta two ways you can specify probe sequences. One is
called linear probing. So this is where if you fail in bucket seventeen you move on
to eighteen and then nineteen and then twenty and then 21. And you stop once you
find an empty one And that's where you insert the new element And another one is
double hashing And this is where you use a combination of two hash functions Where
the first hash function specifies the initial bucket that you probe. The second
hash function specifies the offset for each subsequent probe. So for example if
you have a given elements say the name Alice and the two hash functions give you
the number 17 and 23 then the corresponding finding probe sequence is
going to be initially 17, failing that we'll try 40, still failing that
we'll try 63, failing that we'll try 86 and so on. So in a course on the design
and analysis of algorithms like this one you typically talk a little bit more about
chaining than you do open addressing. That's not to imply that chaining is
somehow the more important one both of these are important But chaining is a
little easier to talk about mathematically. So we will talk about it a
little bit more cuz I'll be able to give you complete proofs for chaining whereas
complete proofs for open addressing would be outside the scope of this course. So
I'll mention it in passing but the details will be more about chaining just for
mathematical ease. So, there's one very important parameter which plays a big role
in governing the performance of a hash table, and that's known as the load
factor, or simply the load, of a hash table. And it's a very simple definition.
It just talks about how populated, a typical bucket of the hash table is. So
it's often denoted by alpha And in the numerator is the number of things that
have been inserted, and not subsequently deleted in the hash table. Divided by
the number of buckets in the hash table. So, as you would expect, as you insert
more and more things into the hash table, the load grows, keeping the number of
items in the hash table fixed as you scale up the number of buckets, the load drops.
So just to make sure that the notion of the load is clear, and that also you're
clear on the different strategies for resolving collisions, the next quiz will
ask you about the range of relevant alphas for the chaining and open addressing
implementations of the hash table. Alright, so the correct answer to this
quiz question is the third answer. Load factors bigger than one do make sense they
may not be optimal but they at least make sense for hash tables that implement with
chaining but they don't make sense for hash tables with open addressing. And the
reason is simple remember in open addressing you are required to store only
one object per bucket so as soon as the number of objects exceeds the number of
buckets there is no where to put the remaining objects. So the hash the hash
table will simply crash if, if load factor is bigger than one. On the other hand a hash table
with chaining there is no obvious problems with load factor bigger than one so you
can imagine a load factor equal to two say, say you insert 2,000 objects into a
hash table with 1,000 buckets. You know that means, hopefully At least in the best
case. Each buckets just gonna have a length list with two objects in it. So
there's no big deal. With having load factors bigger than one, and hash tables
With chaining. Alright, so let's then make a, a quite easy but also very important
observation about a necessary condition for hash tables to have good performance
And this goes into the first caveat that you better properly implement the hash
table if you expect to have good performance. So the first point is that
you're only gonna have constant time look-ups if you keep the load to be
constant. So for a hash table with open addressing, this is really obvious,
because you need alpha not just O(1) but less than one, less than 100 percent full,
otherwise the hash table is just gonna crash, cuz you don't have enough room for
all of the items, but even for hash tables that you implement using chaining, where
they at least make sense for load factors which are bigger than one, you'd better
keep the load not too much bigger than one if you want to have constant-time
operations. Right, so if you have, say, a hash table with. N buckets and you hash in
NlogN objects, then the average number of objects in a given bucket is gonna be
logarithmic And remember, when you do a lookup, after you hash to the bucket, you
have to do an exhaustive search through the linked list in that bucket. So if you
have NlogN objects and you hashed it with N buckets, you're expecting more like
logarithmic lookup time - not constant lookup time And then, as we discussed with
open addressing, of course, you need not just alpha = O(1), but alpha less
than one. And in fact, alpha better be well below one. You don't want to let an
open addressing table get to a 90 percent load or something like that. So I'm going
to write need Alpha less than less than one. So that just means you don't want to
let the load grow too close to 100%, you will see performance degrade. So again, I
hope the point of this slide is clear. If you want good hash table performance, one
of the things you're responsible for is keeping the load factor under control.
Keep it at most a small constant with open address and keep it well below 100%. So
you might wonder what I mean by controlling the load. After all, you know
you writing this hash table when you have no idea what some client's gonna do with
it. They can insert or delete whatever they want. So how do you, how do you
control alpha? Well, what you can control under the hood of your hash table
implementation is the number of buckets. You can control the denominator Of this
alpha so if the numerator starts growing at some point the denominator is going to
grow as well. So what actual implementations of hash tables do is they
keep track of the population of the hash table. How many objects are being stored,
and as this numerator grows, as more and more stuff gets inserted, the
implementation ensures that the denominator grows at the same rate so that
the number of buckets also increases. So if alpha exceeds some target, you know,
that could be say 75%, .75, or maybe it's.5. Then what you can do is you can
double the number of buckets, say in your hash table. So you define a new hash
table, you have a new hash function with double the range, and now having doubled
the denominator. The load has dropped by a factor two. So that's how you can keep it
under control. Optionally, if space is at a real premium, you can also shrink the
hash table if there's a bunch of deletions, say, in a chaining
implementation. So that's the first take away point about what has to be happening
correctly under the hood in order to get the desired guarantees for hash table
performance you gotta control the load. So you have to have a hash table whose size
is roughly the same as the as the number of objects that you are storing. So the
second thing you've gotta get right and this is something we've touched on in the
implementation videos is you better use a good enough hash function And so what's a
good hash function? It's something that spreads the data out evenly amongst the
buckets And what would really be awesome would be a hash function which works well
independent of the data And that's really been the theme of this whole course so
far, algorithmic solutions which work independent of any domain assumptions. No
matter what the input is, the algorithm is guaranteed to, for example, run blazingly
fast And I can appreciate that this is exactly the sort of thing you would want
to learn from a course like this, right? Take a class in the design analysis of
algorithms and you learn the secret hash function which always works well.
Unfortunately I'm not going to tell you such a hash function And the reason is not
cuz, I didn't prepare this lecture. The reason is not because people just haven't
been clever enough to discover such a function. The problem is much more
fundamental. The problem is that such a function cannot exist. That is for every
hash function it has its own kryptonite. There is a pathological dataset under
which the performance of this hash function will be as bad as the most
miserable constant hash function you'd ever seen. And the reason is quite
simple; it's really an inevitable consequence of the compressing that hash
functions are effectively implementing from some massive universe to some
relatively modest number of buckets. Let me elaborate. Fix any hash function as
clever as you could possibly imagine. So this hash function maps some universe
through the buckets indexed from 0 to n -1. Remember in all of the
interesting situations of hash functions, the universe size is huge, so the
cardinality of U should be much, much bigger than n. That's what I'm going to
assume here. So for example, maybe you're remembering people's names, and then the
universe is strings, which have, say at most, 30 characters, and N, I assure you
in any application is going to be much, much, much smaller than say, 26 raised to
the thirtieth power. So now let's use a variant on the pigeon hole principle, and
acclaim that at least one of these n buckets has to have at least a 1/n
fraction of the number of keys in this universe. That is, there exists a bucket
I, somewhere between 0 and n -1 Such that, at least the cardinality of
the universe over N Keys Hash to I get mapped to I under this hash function H. So
the way to see this is just to remember the picture of a hash function mapping in
principal any key from the universe, all keys from the universe to one of these
buckets. So the hash function has to put each key somewhere in one of the n buckets
So one of the buckets has to have at least a 1/n fraction above all of the possible
keys. One more concrete way of thinking, thinking about it is that you might want
to think about a hash table implemented with chaining. You might want to imagine,
just in your mind, that you hash every single key into the hash table. So this
hash table is going to be insanely over-populated. You'll never be able to
store it on the computer because it will have the full cardinality of U objects
in it, but it has U objects, it only has n buckets. One of those buckets has to have
at least U /n fraction of the population. So the point here is that no
matter what the hash function is no matter how clever you build it there's gonna be
some buckets say bucket number 31 which gets its fair share of the universe maps
to it. So having identified this bucket, bucket number 31 where it gets at least
its fair share of the universe maps to it now to construct our pathological dataset
all we do is picked from amongst these elements that get mapped to bucket number
31. So for such as a data set and we can make this data set basically as large as
we want because the cardinality of U/n is unimaginably big, because U itself is
unimaginably big Then in this data set, everything collides. The hash function
maps every single one to bucket number 31 and that's gonna lead to Terrible hash
table performance. Hast table performance which is really no better than the naive
linked list solutions. So for example an hash table with collisions, in bucket 31,
you'll just find a link listed every single thing that's ever been inserted
into the hash table and for open addressing maybe it's a little harder to
see, what's going on but again if everything collides, you're gonna
basically wind up with linear time performance A far cry from constant time
performance. Now, for those of you to whom this seems like just sort of pointless,
abstract mathematics, I want to make two points. The first is that at the very
least these pathological data sets. Tells us, indicates, that we will have to
discuss hash functions in a way differently than how we've been discussing
algorithms so far. So when we talked about merge sort, we just said it runs in n log
n time. No matter what the input is. Whether we discuss the Dijkstra's algorithm
It runs in n log n time, no matter what the input is. That first search, that
first search many a time no matter what the input is. We're gonna have to say
something different about hash functions. We'll not be able to say that a hash table
has good performance, no matter what the input is. This slide shows that's false.
The second point I want to make is that while this pathological data
sets of course are not likely to arise just by random chance. Sometimes you're
concerned about somebody constructing a pathological data set for your hash
function, for example in a denial service attack. So there's a very clever
illustration of exactly this point in a research paper, from 2003 By Crosby and
Wallach. So the main point of Crosby and Wallach was that there's a number of real
world systems And maybe there, most interesting application was a network
intrusion detection system, for which you could bring them to their knees by
exploiting badly designed hash functions. So these were all applications that made
crucial use of hash tables and, the feasibility of these systems really,
completed depended on getting cost and time performance from the hash tables. So
if you could exhibit a pathological data set for these hash tables and make the
performance devolve to linear, devolve to that of a simple link list solution, the
systems would be broken, they would just crash of they'd fail to function. Now we
saw in the last slide that every hash table does have its own Kryptonite. Has a
pathological data set But the question is. How can you come up with such a
pathological data set if you're trying to do a denial of service attack on one of
these systems? And so the systems that Crosby and Wallach looked at generally
shared two properties. So first of all, they were open source. You could inspect
the code. You could see what hash function it was that they were using And second of
all, the hash, function was often very simplistic. So it was engineered for speed
more than anything else And as a result, it was easy to, just be inspecting the
code, reverse engineer a data set. That really did break the hash table. That led
it That devolved the performance to linear. So for example, in the network
intrusion detection application, there was some hash table that was just remembering
the IP addresses of packets that we re going through, because it was looking for
patterns of pack, data packets that seemed to indicate some sort of intrusion. And
Crosby and Wallach just showed how sending a bunch of data packets to this system
with cleverly chosen sender IP's really did just crash the system because the hash
table performance blew up to an unacceptable degree. So how should we
address this fact of life that every hash function has a pathological data set? And
that question is meaningful both from a practical perspective, so what hash
functions should we use if we are concerned about someone constructing
pathological data sets, for example, the implemented denial-of-service attack, and
secondly, mathematically, if we can't give the kinds of guarantees we've given so
far, data-independent guarantees, how can we mathematically say that hash functions
have good performance. So let me mention two solutions, the first solution is, is
meant more just on the practical point. You know what hash function should you
implement if you are concerned with someone creating pathological data sets?
So there are these things called cryptographic hash functions. There for
example, one cryptographic hash function or really family of hash functions, for
different numbers of buckets, is SHA-2 And these are really outside the scope of
this course. I mean, you'll learn more about this in a In a course on
cryptography And obviously using these keywords you can look it up on the web and
read more about it. The one point I want to make is, you know these cryptographic
hash functions like SHA2, they themselves, they do have pathological datasets. They
have their own version of kryptonite. The reason that they work well in practice is
because it's infeasible to figure out what this pathological dataset is So unlike the
very simplistic hash functions which Crosby and Wallach found in the source
code of their applications, where it was easy to reverse-engineer bad datasets, for
something like SHA2 nobody knows how to reverse-engineer a bad dataset for it And
when I say infeasible, I mean in the usual cryptographic sense, in a way similar to
how one would say it's infeasible to break the RSA cryptosystem if you implement it
properly, or it's infeasible to factor large numbers except in very special case,
and so on. So that's all I'm going to say about cryptographic hash functions. I also
want to mention a second solution, which would be reasonable both in practice, and
also for which we can say a number of things mathematically about it Which is to
use randomization. So more specifically we're not going to design, a single.
Clever hash function Because again, a single hash function we know Must have a
pathological data set But we're gonna design a very clever, family of hash
functions And then, at run time. We're going to pick, one of these hash functions
at random. Another kind of guarantee you are going to want, we are going to be able
to prove on a family affairs function would be very much in the spirit of quick sort.
So you would call that in the quick sort algorithm, pretty much. For any
fixed pivot sequence there is a pathological input for which quick sort
will devolve to quadratic running time. So our solution was randomize quick sort
which is rather than committing up front to any particular method of choosing
pivots at run time we are gonna pick pivots randomly. What did we prove about
quick sort? We proved that for any possible input for any possible array the
average running time with quick sort was O(nlogn) with the average was over the
run time random choices of quick sort. Here we are gonna do the same thing we'll
now be able to say for any dataset. On average, with respect to our run time
choice of a hash function. The hash function will perform well, in the sense
that it will spread out the data of the data set evenly. So we flip to the
quantifiers from the previous slide. There, we said if we pre-commit to a
single hash function. If we fix one hash function, Then there's a data set that
breaks the hash function. Here we're flipping it, we're saying for each fixed
data set a random choice of a hash function is going to do well on average on
that data set. Just like in Quick Sort. This doesn't mean notice that we can't
make our program open source. We can still publish code which says here is our family
of hash functions and in the code we would be making a random choice from this set of hash
functions But the point is by inspecting the code you'll have no idea what was the
real time random choices made by the algorithm. So you'll know nothing about
what the actual hash function is so you won't be able to reverse engineer
pathological dataset for the real time choice of the hash function. So the next
couple of videos are gonna elaborate on the second solution Of using a real time
random choice of a hash function as a way of saying. You do well on every data set
At least on average. So let me just give you a road map of where we're going to go
from here. So I'm going to break the discussion of the details of a randomized
solution into three parts, spread over two videos. So in the next video we're going
to begin with the definition of what do I mean by a family of hash functions, so
that if you pick one at random, you're likely to do pretty well. So that's a
definition that's called a universal family of hash functions. Now a
mathematical definition by itself is worth approximately nothing. For it to be
valuable, it has to satisfy two properties. So first of all there have to
be interesting and useful examples that meet the definition. So that is, there
better be Useful looking hash functions that meet this definition of a universal
family. So the second thing will be to show you that they do indeed exist And
then the other thing a mathematical definition needs is applications. So that
if you can meet, the definition. Then, good things happen. So that'll be part