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.