In the last video, we discussed the
performance of hash tables that are
implemented using chaining, using one link
list per bucket. In fact, we proved
mathematically that if you use a hash
function chosen uniformly at random from a
universal family, and if you keep the
buckets, number of buckets, comparable to
the size of your data set, then in fact,
you're guaranteed constant time expected
performance But, recall that chaining is
not the only implementation of hash
tables. There's a second paradigm which is
also very important called open
addressing. This is where you're only
allowed to store one object in each slot,
and you keep searching for an empty slot
When you need to insert a new object into
your hash table. Now it turns out it's
much harder to mathematically analyze hash
tables implemented using open addressing
But, I do want to say a few words about it
to give you the gist of what kind of
performance you might hope to expect from
those sorts of hash tables. So recall how
open addressing works. We're only
permitted to store one object in each slot
So this is unlike the case with chaining
where we can have an arbitrarily long list
in a given bucket of the hash table. With
at most one object per slot, obviously
open addressing only makes sense when the
load factor alpha is less than one. When
the number of objects you're storing in
your table is less than the number of
slots available Because of this
requirement we have at most one object per
slot we need to demand more of our hash
function. Our hash function might ask us
to put a given object, say with some IP
address into say bucket number seventeen
but bucket number seventeen might already
be full, might already be populated. In
that case, we go back to our hash function
and ask it where to look for an empty slot
next. So maybe it tells us to next look in
bucket 41. If 41 is full it tells us to
look in bucket number seven and so on Two
specific strategies for producing a probe
sequence that we mentioned earlier were
double hashing and linear probing. D ouble
hashing is where you use two different
hash functions, h1 and h2. H1 tells you
which slot in which to search first and
then every time you find a full slot you
add an increment which is specified by the
second hash functions h2. Linear probing
is even simpler you just have one hash
function that tells you where to search
first and then you just add one to the
slot until you find an empty slot As I
mentioned at the beginning, it is quite
nontrivial to Mathematically analyze the
performance of hash tables, using these
various open addressing strategies. It's
not impossible. There is some quite
beautiful and quite informative
theoretical work. That does tell us how
hash tables perform But that's well
outside the scope, of this course. So
instead what I wanna do is I want to give
you a quick and dirty calculation. That
suggests, at least in an idealized world.
What kind of performance we should expect
from a hash table with open addressing If
it's well implemented As a function of the
load factor, alpha. Precisely, I'm going
to introduce a heuristic assumption. It's
certainly not true but we'll do it just
for a quick and dirty calculation, that
we're using a hash function in which each
of the n-factorial possible probe
sequences is equally likely. Now, no hash
function you're ever going to use is
actually going to satisfy this assumption,
and if you think about it for a little
bit, you realize that if you use double
hashing or linear programming, you're
certainly not going to be satisfying that
assumption. So this will still give us a
kind of best case scenario against to
which you can compare the performance of
your own hash table implementations. So if
you [inaudible] hash table, and you're
seeing performance as good, as what's
suggested by this idealized [inaudible]
analysis, then you're home free. You know
your hash table is performing great. So
what is the line in the sand that gets
drawn, under this heuristic assumption?
What is this idealized, idealized hash
function performance? As a function of the
lo ad alpha Well here it is. What I'm
gonna argue next is that under this
heuristic assumption, the expected amount
of time to insert a new object into the
hash table, is going to be essentially one
over one minus alpha, where alpha is the
load. Remember the load is the number of
objects in the hash table divided by the
number of available slots. So if the hash
table is half full, then alpha's going to
be.5. If it's 75 percent full then alpha's
going to be three-fourths. So what this
means is that, in this idealized scenario,
if you keep the load pretty under control.
So, say if the load is 50%, then the
insertion time is gonna be great, right?
If alpha's.5 And 1/ (1-alpha) =two, so you
expect just two probes before the
successful insert of the new object And of
course, if you're thinking about lookup,
that's going to be at least as good as
insert, so if you're lucky a lookup might
terminate early if you find what you are
looking for. In the worst case you go all
the way until an empty slot in an
unsuccessful search, and that's gonna be
the same as insertion. So if alpha is
small bounded away from one, you're
getting constant time performance. On the
other hand, as the hash table gets full,
as alpha gets close to one, this operation
time is blowing up; it's such a going to
infinity as alpha gets close to one. So if
you need to have a nice. 90 percent full
hash table with open addressing. You're
gonna start seeing, ten probes. So, you
really wanna keep hash tables with open
addressing. You wanna keep the load under
control Certainly no more than probably.7.
Maybe even less than that To refresh your
memory, with chaining, hash tables are
perfectly well-defined even with loads
factors bigger than one. What we derived
is that under universal hashing, under a
weaker assumption, we had an operation
time of one plus alpha, for a load of
alpha. So with chaining, you just gotta
keep alpha, you know, at most, some
reasonably small constant with open
address, and you really got to keep it
well bounded a way below one. So next
let's understand why this observation is
true. Why under the assumption that every
probe sequence is equally likely do we
expect a one over one minus alpha running
time for hash tables with open addressing?
So, the reason is pretty simple. And we
can derive it by analogy with a simple
coin flipping experiment. So, to motivate
the experiment, think just about the very
first probe that we do. Okay, so we get
some new objects, some new IP address that
we want to insert into our hash table.
Let's say our hash table's currently 70
percent full. Say there's 100 slots, 70
are already taken by objects. Well, when
we look at this first probe, by assumption
it's equally likely to be any one of the
100 slots. 70 of which are full, 30 which
are empty So, with probability of one
minus alpha, or in the case, 30%, our
first Probe will, luckily, find an empty
slot and we'll be done. We'll just insert
the new object into that slot If we get
unlucky with a probability, 70%. We find a
slot that's already occupied and then we
have to try again. So we try a new slot,
drawn at random And we again check is it
full, or is it not full? And again, with
30 percent probability, essentially it's
going to be empty and we can stop And if
it's already full. Then we try, yet again.
So Doing random probes, looking for an
empty slot, is tantamount to flipping a
coin with the probability of heads
1-alpha, or, in this example, 30 Percent
And the number of probes you need until
you successfully insert is just the number
of times you flip this last coin until you
see a heads. In fact this biased coin
flipping experiment slightly overestimates
the expected time for insertions and the
heuristics assumptions and that's because
in the insertion time whenever we're never
going to try the same slot twice. We're
going to try all end buckets in some order
with each of the impact [inaudible]
ordering equally likely So back to our
example, where we have a hash table with
100 slots, 70 of which are full. The first
probe indeed, we have a 30 in 100 chance
of ge tting an empty slot. If that one
fails then we're not going to try the same
slot again. So there is only 99 residual
possibilities. Again, 30 of which are
empty. The one we checked last time was
full. So we actually have a 30 over 99
percent chance of getting an empty slot on
the second try. Like 30 over 98 on the
third try, if the second one fails, and so
on But, a valid upper bond is just to
assume a 30 percent success probability
with every single probe, and that's
precisely, what this coin flipping
experiment will get us. So the next quiz
will ask you to actually compute the
expected value of capital N, the number of
coin flips, needed to get heads when you
have a probability of heads of one minus
alpha. As a hint, we actually analyzed
this exact same coin flipping experiment
when alpha equals a half, back when we
discussed the expected running time of
randomized linear time selection. Alright,
so the correct answer is the first one.
One over 1-alpha So to see why, let's
return to our derivation, where we reduced
analyzing the expected insertion time to
this random variable. The expected number
of coin flips until we see a heads. So,
I'm gonna solve this exactly the same way
that we did it back when we analyzed a
randomized, selection algorithm. And it's
quite a sneaky way, but very effective.
What we're going to do is we're going to
express the expected value of capital N,
in terms of itself, and then solve. So how
do we do that? Well on the left hand side
let's write the expected number of coin
flips, the expected value of capital N,
and then let's just notice that there's
two different cases, either the first coin
flip is a heads or it's not. So in any
case you're certainly going to have one
coin flip so let's separate that out and
count it separately. With probability
alpha, the first coin flip is gonna be
tails and then you start all over again
And because it's a memory less process,
the expected number of further coin flips
one requires, given that the first coin
flip was tails, is just the same as the
expected number of coin flips in the first
place. So now it's a simple matter to
solve this one linear equation for the
expected value of N, and we find that it
is indeed one over one minus alpha, as
claimed. Summarizing, under our idealized
heuristic assumption, that every single
probe sequence is equally likely, the
expected insertion time is upper bounded
by the expected number of coin flips,
which by this argument is, at most, one
over one minus alpha. So, as long as your
load, alpha, is well bounded below one,
you're good. At least in this idealized
analysis, you're hash table will, will
work extremely quickly. Now I hope you're
regarding this idealized analysis with a
bit of skepticism. Right, from a false
hypothesis you can literally derive
anything you want. And we started with
this assumption which is not satisfied, by
hash functions you're actually going to
use in practice. This heuristic
assumption, that all probe sequences are
equally likely. So, should you expect this
one over one minus alpha bound to hold in
practice or not? Well, that depends to
some extent. It depends on what open
addressing strategy you're using. It
depends on, how good a hash function
you're using. It depends on whether the
data is pathological or not. So, just to
give course rules of thumb If you're Using
double hashing and you have
non-pathological data, I would go ahead
and look for this 1/1-alpha bound in
practice. So implement your hash table,
check its performance as a function of the
load factor alpha and shoot for the
1/1-alpha curve. That's really what you'd
like to see. With linear probing, on the
other hand, you should not expect to see
this performance guarantee of 1/1-alpha
even in a totally idealized scenario.
Remember, linear probing is the strategy
where your initial probe, the hash
function, tells you where to look first,
and then you just skim linearly through
the hash table until you find what you're
looking for, an empty slot, the. That
you're looking up or whatever So a linear
probing, even in a best case scenario,
it's going to be subject to clumping.
You're going to have contiguous Groups of
slots which are all full, and that's
because of the linear probing strategy.
Now I encourage you to do some experiments
with implementations to see this for
yourself. So because of clumping with
linear probing, even in the idealized
scenario, you're not going to see one over
one minus alpha. However, you're going to
see something worse, but still in
idealized situations. Quite reasonable so
that's the last thing I want to tell you
about In this video. Now needless to say,
with linear probing the heuristic
assumption is badly false. The heuristic
assumption is pretty much always false to
no matter what hashing strategy you're
using, but with linear programming it's
quote on quote really false. So to see
that, the heuristic assumption, say that
all in factorial probe sequences are
equally likely. So your next probe is
going to be uniform or random amongst
everything you haven't probed so far but
when you're probing, it's totally the
opposite. Right once you know the first
slot that you're looking into say bucket
seventeen, slot a7 is gonna be the first
slot, you know the rest of the sequence
because it's a linear [inaudible] cancel
the table. So it's kind of [inaudible] the
opposite from each successive probe being
independent from the previous ones except
not exploring things twice. So to state a
conjectured or idealized performance
guarantee for hash tables with linear
probing, we're going to place, replace the
blatant false heuristic assumption by a
still false, but more heuristic reasonable
assumption. So what do we know? We know
that the initial probe with linear probing
determines the rest of the sequence. So
let's assume that these initial probes are
uniform at random, and independent for
different keys. Of course, once you have
the initial probe, you know everything
else, but let's assume independence and
uniformity amongst The initial probes.
Now, this is a strong assumption. This is
way stronger than assuming you ha ve a
universal family of hash functions. This
assumption is not satisfied Practice, but
Performance guarantees we can derive under
this assumption are typically satisfied in
practice by well implemented hash tables
that use linear probing. So, the
assumption is still useful for deriving
the correct, idealized performance of this
type of hash table. So what is that
performance? Well this is an utterly
classic result from exactly 50 years ago
From 1962 And this is a result by my
colleague, the living legend, Don Canuth,
author of Art of Computer Programming. At
what can proved is, was that is that under
this weaker [inaudible] assumptions,
suitable for linear probing. The expected
time to insert an object into a hash table
with a load factor alpha, when you're
using linear probing is worse than one
over one minus alpha, but. It is still a
function of the load alpha only and not a
function of the number of objects in the
hash table. That is with linear
programming you will not get as good a
performance guarantee, but it is still the
case that if you keep the load factor
bounded away from one. If you make sure
the hash table doesn't get too full you
will enjoy constant time operations on
average so for example if with linear
probing your hash table is 50 percent full
then you are going to get an expected
insertion time of roughly four probes.
Note however this quantity does approach
does blow up pretty rapidly as the hash
table grows full. If it is 90 percent full
this is already going to be something like
a hundred probes on average. So you really
don't wanna let hash tables get too full
when you are using linear probing. You
might well wonder if it's ever worth,
implementing linear probing, given that it
has the worst performance curve, one over
one minus alpha squared. Then the
performance curve you'd hope from
something like double hashing, one over
one, minus alpha. And it's a tricky cost
benefit analysis between linear probing
and more complicated but better performing
strategies. That really depends on the ap
plication. There are reasons that you do
want to use linear probing sometimes, it
is actually quite Common in practice For
example, it's often interacts very well
with memory hierarchies So again, as with
all of this hash and discussion. You know
the costs and benefits Are, are very
subtle trade-offs between the different
approaches. If you have mission critical
code that's using a hash table and you
really want to optimize it. Try a bunch of
prototypes, and just test. Figure out
which one is the best, for your particular
type of application. Let me conclude the
video with a quote from Canuck himself
where he talks about the rapture of
proving this one of our one man is half a
square theorem and how it was life
changing. He says I first formulated the
following derivation, meaning, the proof
of that last theorem in 1962. Ever since
that day, the analysis of algorithms has,
in fact, been one of the major themes in
my life.