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).
Hash Tables: Implementation Details, Part I
Loading...
Del curso dictado por Stanford University
Graph Search, Shortest Paths, and Data Structures
1030 calificaciones
De la lección
Week 4
Hashing; bloom filters.
Conoce a los instructores
Tim RoughgardenProfessor
Computer Science
So in this video we'll take a peek under the hood of hash functions. And I'll
discuss some of the high level principles by which their implemented. So let's
briefly review the raison d'etre of a hash table. So the purpose in life for a hash
table is to support super-fast lookups. So maybe you're keeping track of the
transactions that happened on your website yesterday. Maybe you're keeping track of
your employees; maybe you're keeping track of IP addresses in an Internet router.
Maybe you're keeping track of chess configurations in a, in a chess-playing
program, Whatever, The point is, you want to be able to insert stuff into a hash
table, and later remember whether something's there or whether something's
not there. So the implementations we'll discuss will generally also support
deletions. But that's pretty much it. It's a very restricted set of operations. But
the hash, It was going to execute them at very, very well. So, basically in constant
time, again subject to some fine print, which we'll discuss a little bit in this
video but, then more deeply in a separate optional video. So, the two caveats are
first of all the hash table had better be properly implemented. It's actually pretty
easy to screw up a hash table to screw up hash functions. We'll talk a bit about
that in a few minutes and, then, also, the data should, in some sense, be
non-pathological, and that, we will discuss more deeply in a separate video.
Alright, so let me give you an initial glimpse of some of the magic that's
happening under the hood in hash functions. So, at first let me say exactly
what the setup is. The first step is to identify all the things that you might
want to be storing. So, in other words, the universe of your application, So this
would be something like, all possible I-P addresses, of which there's 2^32 .
All possible names you might encounter, perhaps with a maximum of, say,
30 characters. All possible configurations of a chessboard, and so on, And one thing
I hope you can appreciate from these examples is that, in many cases, this
universe is really big. Sothe number of ] IP address is, quote unquote, only two 2^32.
The number of all names, you're probably talking more like 26 raised to the 30.
All chessboard configurations I don't even wanna think about. And what you
wanna accomplish is, you wanna maintain an evolving subset of this universe U. So
maybe you wanna keep track of all the IP addresses you've seen on your website in
the last 24 hours. You wanna keep track of the phone numbers of all of your friends.
You wanna keep track of the chessboard configurations that you've explored in the
past three seconds, whatever. And again I hope what is clear from the applications
we've been discussing, is that the set S is usually of a reasonable size. It's,
it's something you could store in main memory. You know, it maybe it's tens of
thousands of IP addresses. Maybe it's, you know, a few hundred names of your various
friends. You know, maybe it's in the, you know, millions of chessboard
configurations, but still way, way, way smaller than the size of the universe. So
without data structures, you'd have to resort to other unsatisfactory solutions
to maintaining this set. So the first thing you could try, as we discussed in
the previous video, would be just have an array with one position for every
imaginable thing you might want to store in your set. So this is the solution
that's going to work well if all of your friends happen to have names that are
integers between 1 and 10,000, but doesn't scale when the universe size
becomes really big, as in most of these applications. So, the good news is, is of
course, is an array of and it's of course fast random access so you can access any
position in constant time. So, if you have an array base solution index by all the
elements of the universe, you can do constant time, insert, delete and look up.
The bad news is, is the space requirement is proportional to the
universe. And again, forget about being unsatisfactory. That's just literary
impossible. Infeasible in many applications in which you'd use hash
tables. Now of course to get the memory proportional to the size of the set stuff
that you're storing, an easy solution would just be to use a list. You know, say
a doubly-linked list. Something like that. Now with a list-based solution the good
news is, is your memory is certainly proportional to the size of the set that
you're storing, and independent of the size of the universe from which these
elements are drawn. The bad news is that to figure out whether something is, or is
not, in a list you generally have to traverse through most of that list. And
that's gonna take up time proportional to the length of the list. So, really the
question we're faced in implementing cache table is, can we get the best Of both
worlds, of these two naive solutions. And the one hand, we want to have the constant
time operations enjoyed by the array based solution. But on the other hand, we wanna
have the, linear space in the size of the set that we're storing; that we get in the
list based solution. So to get the best of both worlds, we are going to use an array
based solution. But the array will not be big. It'll not be with size proportional
to the universe. The array will only have size, you know, roughly the same as the
set that we're storing, So somewhere in the ball park of the cardinality of S. So
the first thing we do is we decide on how big we want our array to be. So that, that
length is gonna be called n. We're gonna have an array of length n. And n is gonna
be in the ballpark of the size of S. It's gonna depend on a few things. Exactly how
n compares to S, but for now think of n as like double the size of S. We're gonna be
calling each entry of the array a bucket, so there's n buckets, and then, the size
of S is about 50 percent of the number of buckets, let's say. So one objection you
might legitimately raise at this point is, you know I thought, I said the set was
dynamic. The set S. Right? Stuff can be added, stuff can be deleted. So the size
isn't always the same. It can fluctuate over time. So what does it mean to define
an array which is the, roughly the same length as this changing set. So for
simplicity, for the purposes of this video to focus on the key points I am going to
assume that the set size S. While S itself can be changing, I'm going to assume that
the size of S doesn't fluctuate too much. So there are additional bells and whistles
you can add to a hash table implementation, and they're all quite
natural. I think most of you could probably figure them out on your own, to
deal with the fact that S might be changing sizes. So for example, you can
just keep track of how many elements are in your hash table. And when it exceeds a
big, a certain threshold, so when it's too big relative to the size of your array,
you just double the array. And then you reinsert all of the elements into this new
doubled array. Similarly, if you want to, if the set shrinks, you can have tricks
for shrinking the array dynamically as well. So I'm not gonna discuss these bells
and whistles for resizing your hash table dynamically. They are, of course Important
for a real implementation, and they are part of the implementations in the
standard programming libraries. But I view those as sort of a, a second order point
in the implementation of a hash table. And I wanna focus on the first order points,
in this video. So, summarizing, think of the set S. There are insertions and
deletions we have to accommodate. But, you know, S is gonna be roughly the same size.
And the number of buckets will be, you know, within a constant factor of the size
of the set. All right so there we have our array with totally reasonable space, space
proportional to the size of the set that we are storing. And now what we want is we
want is some way of translating between the things that we care about, say our
friends names or whatever the elements in the universe are to the positions in this
array. So the object responsible for that translation from keys drawn from this universe to
positions in this array is called a hash function. So formally, a hash function
Takes as input a key. So this is gonna be an IP address or the name of somebody or a
chessboard configuration or whatever. And it's going to spit out an position in this
array. So I'm gonna label the array entries from 0 to n-1 for this lecture.
Obviously at the moment this is super underspecified. There's a zillion
functions you could choose. Which one you use, we'll talk about that, but for now
there's just gonna be some hash function mapping from elements of the universe to
buckets, to positions in this array. Now, as far as the semantics of this hash
function, what the hash function is doing, it's telling us in which position we
should store a given key from the universe. So, if we have some new friend
named Alice. And we run Alice, we key Alice through the hash function and it
gives us a 17. It says we should store Alice's phone number in position
17 of the array. If we have some crazy chessboard configuration, we feed it
into a hash function and it spits out 172, it says we should remember this chessboard
configuration in the 172nd bucket of this array. So again, given x, which is some
key from this universe, we invoke a hash function to get a position in this array,
to get a bucket. And then that is where we try to store this x and any associated
data with it. So that's the high leveled idea of how you implement a hash
table, but we're quite far from done, And in particular there is a serious issue,
that we're going to have to deal with, that's fundamental to implementing hash
tables, and that's the notion of a collision. So probably many of you may
have already noticed that this problem might occur. Which is well what happens if
we're storing our friend's phone numbers, and you know Alice shows up and we ask our
hash function where to store Alice's phone number, and it says oh bucket number
17, And then our friend Bob shows up, and we ask our hash function where to
store Bob's phone number, and what if the hash function also says bucket number
17 for Bob? What do we put in bucket at 17? Do we put Alice
there, do we put Bob there, do we put them both there? How do we deal with these
so-called collisions? So, the next quiz is meant to give, to get you thinking about
collisions, and in some sense, how truly unavoidable they really are. [sound],
[sound] All right. So the correct answer to this question is the first answer,
believe it or not. All you need is 23 people in a room before you're equally
likely to have two people with the same birthday as not. So if you're looking to,
to skim a little money off of your non-mathematical friends, this is one way
you can do it. Go to cocktail parties with about 40 people and place bets with people
that there are two people in the room with the same birthday. So if you have 367
people, well there's only 366 distinct birthdays, I'm counting February 29th
here as one of them. So by the pigeonhole principle, certainly the
probability is 100%. By the time you get to 367. Now, by the time you're at 57.
You're already at 99%. So you already have overwhelming probability to have a
duplicate birthday with 57 people. So of course, with 184 you're gonna be almost at
100%, 99.99. Who knows? Some large number of 9's, And at 23, you're at 50%. So many
people find this quite counter-intuitive that you only need 23 people to get a
duplicate birthday on average. And so this is a, this is a quite famous example and
it sometimes goes by the birthday paradox. Calling it a paradox is sort of a
misnomer. A paradox, you know, often suggests some kind of logical
inconsistency. There's no logical inconsistency here. It's just that
people's brains are not really wired to have this intuition, for whatever reason.
So, but it's really just math. You can work out the math, and, and, and you can
just solve it. So, more generally, the principle behind the birthday paradox is
the following. So suppose you have a calendar, perhaps on some different
planet, which has K days. Where each, everybody's equally likely to have each of
the K days as their birthday. Then it's about the square root of k people that you
need in a room before you're equally likely to have a duplicate, or not have a
duplicate. Okay, and the reason that you get the square root effect is because if
you think about it. There's a quadratic number of pairs of people in the room, so
that's a quadratic, and the number of people Opportunities to have a duplicate.
Right? So, each pair of people could be a duplicate, there's a quadratic number of
pairs. And so, that's why, once the number of pairs starts reaching about the number
of different days, you're, you're about, you're likely to see a duplicate around
that point. So you might be wondering why I'm telling you about the birthday paradox
in the middle of a lecture about hashing, but really it's quite relevant. So imagine
for example you defined a hash function in the following way. Now to be clear, this
is not a practical hash function, but just for the purposes of discussion, imagine
you have a hash function which randomly assigned every single key to a uniform
bucket. 'Kay, so for each, each of the 1/n buckets equally likely. Then what
the birthday paradox says is, even for a very small dataset, you are already gonna
have a pair of things colliding. All right, So if you have an n buckets, so
maybe your n is like, 10,000, all you need is roughly 100 elements in your data set,
and despite the fact that the table is only going to be one percent full, you're
already going to see a collision, okay? So 99 percent of them are empty, but you're
going to have one bucket that has two, so that's sort of annoying. So the birthday
paradox says, you start getting collisions with the hash function, even with the
really tiny data sets. So in this sense, if you're going to have hash tables,
you've got to deal with collisions. There's going to be a fair number of them,
and you need some method for resolving them So, collisions are a fact of life
when you're talking about hashing. Where again, by collision, what I mean is two
different keys. So two different elements x and y from the universe that hash to the
same bucket, Who have the same hash value, So in general we can think of a hash
function as doing a compression of sorts. So we have a huge universe U and we have
this very modest size array A with the only n buckets. Where n, we're thinking
of as being much, much, much smaller than U. So, of course, this hash function has
to map various elements of U to the same bucket. So what are we gonna do about it?
How are we going to resolve these collisions? Well, there's two different
solutions which are both quite prevalent in practice. So solution number one is
called chaining, or sometimes you'll also see it called separate chaining. And this
is a very natural solution; it's also the one that's relatively easy to analyze
mathematically. What you do is just for elements that hash to the same bucket, you
just revert to the list-based solution that we talked about in a previous slide.
So, each of the n buckets will not necessarily contain just merely 0 or 1 element
, it will contain a list within a principle unbounded number of elements.
Okay, so when we use chaining, it's done quite straight-forward to figure out how
to implement all of the hash table operations, namely, insert, delete and
look-up, you just hash something to the appropriate bucket and then you just do
insert, delete or look-up, as appropriate, in the list that's in that bucket. So just
to make clear that everything is type checking, so here h(x), this is the bucket
for x. That's what's specified by the hash function. And then, in the h(x) position
of this array A, in the h (x), the bucket is where we find the linked list that is
going to contain x. So just to give a cartoon example, if you had, say, four
buckets, Maybe, you know, the first bucket has exactly one record. Corresponding to
Alice, maybe the second bucket just has a null pointer. No one's been inserted in the
second bucket. And then the third bucket we have, let's say, both Bob as well as
Daniel. And then maybe in the fourth bucket we have Carol. Okay, so because we
have a collision between Bob and Daniel, both map to the third bucket, and we
resolve that just by having a linked list, with Bob and Daniel in some order. So the
second solution which is trickier to talk about mathematically but still quite
important practically is called open addressing. And the principal in open
addressing is you're not going to use any space for pointers. You're not gonna
have lists. So you're only gonna have one object per bucket of the array. So another
question is what happens if, you know, you try and insert Daniel and you go, you
invoke the hash function on Daniel and it takes you to a bucket that already
contains Bob? That means there's no room for Daniel. So what you're going to do is
you're gonna probe the hash table in some other position. So a hash function is, is
now gonna be replaced by a hash sequence, where you try, the hash function tells you
the first bucket to try to insert Daniel; failing that, a second bucket in which to
try to insert Daniel; failing that, a third bucket to try to insert Daniel; and
so on. And you just keep trying till you find an open position somewhere in the
array. So there's various strategies for trying to figure out the probe
sequence. One strategy is if you fail and save bucket 17, which is where the
hash function tells you to go first. You just try bucket 18, then 19,
then, 20, then 21 and so on, until you find your first open slot. So that's
called linear probing. And another approach is double hashing. So this is a
solution where you actually have two hash functions, hash function 1 and hash
function 2. And the idea is, suppose you're trying to insert, say, Daniel, into
a hash table with open addressing, and you evaluate both of the hash functions. And
the first one comes up 17, and the fir-, the second one comes up 23. So, as
usual, the has-, first hash function will specify where you look first. So if it
evaluates on Daniel to 17, you look in the seventeenth position of the array,
And if, if it's empty, that's where you insert Daniel. Now, if it's full, what you
do is you use the second Hash value to be an additive shift, so. Unlike linear
probing where after seventeen, you look at eighteen. With double hashing, if the
second hash function gives you 23, that's gonna be your offset. So after seventeen,
you look at bucket 40. If 40 is already full, you look at bucket 63. If bucket 63
is already full then you look at bucket 86. So you keep adding increments of 23
until you finally find a bucket where, that's empty and that's where you insert
Daniel. Now of course, if you try to insert some other name, if you try to
insert Elizabeth, you're gonna get two totally different numbers in general. So
maybe you'll get 42 and 27, and so here the probed sequence will be 42, failing
that 69, failing that 96 failing that 123 and so on, So a question you should have
at this point, is, you know. I've told you two solutions to resolving collisions in a
hash table. And you're probably asking, well, which ones should you use if you
have to implement your own hash table? And, you know, as usual, if I present you
with two different solutions for the same problem. You can probably rest assured
that neither one dominates the other, right? Otherwise I wouldn't waste your
time by presenting both of them to you. So, sometimes chaining's gonna perform
better, and sometimes, open addressing's gonna perform better. And of course, it
also depends on what kind of metric that you care about. So there are a couple of
rules of thumb that I can tell you. So first of all if space is at a real premium
you might want to consider open addressing instead of chaining, and that's cause with
chaining you do have this excess, not huge but you do have this little bit of
space overhead and dealing with all these pointers in this link list. So if you want
to avoid that, you might want to think about open addressing. The second rule of
thumb is deletion is trickier with open addressing than with chaining, but
deletion is clearly not difficult at all, either to code or understand when you use
chaining cause it just reduces chaining to a linked list which of course you all know
how to do. Open Addressing is, it's not impossible to implement deletion but it's
much trickier. So if deletion's a, a crucial operation for you, that might
steer you towards thinking about chaining. But ultimately, if it's really kinda
mission critical code, probably the best thing to do is implement both kinds of
solutions and just see which one works better. It's a little hard to predict how
they're gonna interact with memory hierarchies and that kind of thing.
They're both useful in their own contexts. Alright so we've covered the two most
prevalent ways of handling collisions. And we argued that collisions are inevitable
no matter you design you hash function. You're stuck with collisions and you can
do chaining or linked lists per bucket, or you can do addressing, where you actually
have a probe sequence in order of which you look at buckets until you find an
empty one. And the elephant in the room at this point is, you know, what is this hash
function? I have told you nothing about hash functions. All I told you is there is
some mapping from the set of the universe, so IP addresses, or names, or whatever to
a bucket number. Well what kind of function should you use? Excellent
question, Tons of research on that question, And to this day as much art as
science. But let's start talking about it.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2019 Coursera Inc. Todos los derechos reservados.
