I just want to briefly discuss hash
tables, because, they're quite, closely
related to, words an balls and urns
problems.
But, won't, won't spend a lot of time and
lecture on it.
There's more information, in the book.
So we, we talked, just briefly about the
balls and urns model.
Of course, this is very heavily studied in
classical, combinatorics.
And so we talked about, well what's
probability that no urn has more than one
ball, what's the probability that no urn
is empty, you might want to know how many
empty urns there are...
How many urns have K balls and so forth
These so called occupancy problems are,
are well studied dating back many, many
decades.
So in, in the classical result is simply
from the binomial distribution.
And the probability, and we looked at
this, before, when we talked about
asymptotics.
The probability that a value occurs K
times, a given value occurs K times in a
random M word of length N, is N choose K,
one over M to the K, one minus one over M
to the N minus K.
That is you get your value, k times the
probability of 1 over n and the other
values are not yours with probability of 1
minus over m to the n minus k.
So that's, given[UNKNOWN] probability
given sk balls.
Now we looked ed at the Poisson
approximation that, works for the
situation where, n over n is, is alpha and
it's fixed, and k is a, a small constant,
that's the so called Poisson
approximation.
And we showed how to come up with that
approximation in.
When we talked about asymptotics.
So, And this is a very good,
approximation.
So, for example, this, plot gives for,
This is for alpha equals 10.
So n equals 10,000.
M equals 1,000.
Some, that's, a plot of the binomial
distribution.
So, it's centered at ten.
And, that's, that's where the peak is.
And this is the Poisson approximation, for
that same case, that alpha equals to ten.
And the curves here are nearly identical.
And so that, the Poisson approximations
are a little bit easier to work with.
So, that's why so, often used.
So they, an application, is in hashing
algorithms.
So people in computer science are very
familiar with these algorithms.
I'll just briefly describe them for,
people.
The in, in math that may be you haven't
seen them.
They're very well covered in books on
algorithm like our book or[UNKNOWN] book,
the ideas we want any efficient way to put
key value pairs in a simple table.
And we talked about this for binary search
strings.
Drives, and we want to search for the
table for the pair corresponding to a
given key.
So the scratching, hashing strategy is to
come up with a function that maps each key
onto a random value between zero and N
minus one.
And then develop a collision strategy to
figure out what to do when two keys hash
to the same value.
And the basic algorithm of that we'll talk
about.
One's called separate channing where we.
And essentially represent the urn with a
length list.
And another one's called linear probing
where we just use an array and we never
let two get in the same place where we
scan through the empty spots on the
collision.
And I'll talk about briefly about both of
those algorithms.
And the model that we use is this idea
that the hash function.
We assume what's called the uniform
hashing assumption, that the hash function
maps each key into a random value between
0 and N minus 1.
And it's been shown to be not so difficult
for typical types of keys to get hash
functions that reasonably approximate this
uniform assumption.
So that's the set up.
So hashing with separate chaining is
really easy to implement.
And this is just a diagram from our
algorithms book that shows a hash table of
size five.
And so the keys are letters and then the
hash values are supposed to be random
values between zero and five it's just a
word.
So the sequence of hash values is just a
random word.
And then we store the letters in lists
indexed by the hash values.
So those are the urns and the keys, and
the associated values are, are the balls.
So that's easy to implement.
And of course we're going to be interested
in how long these lists are.
So again this is the just the balls and
urns model for hashing with separate
chaining.
And, and probably spending too many time,
too much time on animations.
But so it, what we want to know is when
we're going to search for an item in this
we're going to have to go through all the
balls in the urn.
And so we want to know The average number
of balls in each urn, say.
Well that's obvious.
There's n balls.
There's m urns.
On average there's n over m balls in each
urn.
And actually that doesn't depend on
anything.
It's not very helpful at all.
If all the balls fall in one urn, still
your average number of balls per urn is n
over m.
It doesn't have to be random even, so that
observation is not much help.
So, and we know the probability has k
balls.
That's the occupance distribution.
Generally we're going to have, try to keep
the number of urns large enough that our
number of balls per urn is a constant like
alpha so we know that.
But what the programmer wants to know is
something about what's the chances that
they're distributed evenly.
So, we have to do a little more math to,
provide that answer.
So here's what a programmer might say.
So if I make sure that, N is big enough so
that N over M is less than some constant
output.
But.
And it turns out to be not difficult to do
that.
And the average number approach for search
is going to be less than alpha.
I know that.
But what's the chance that some search'll
use way to many pro, probes, under the
uniform hashing assumption.
Say five alpha.
Per probes.
Well, that's actually not too difficult to
calculate.
So, what it is, is we know the probability
for k probes, we can sum that for all k
bigger than 5 alpha.
And the trick is to use Stirling's formula
to bound k factorial and then if you do
that then we get something that converges
very rapidly, so it 's something like e to
the minus alpha.
Times E over five to the five alpha.
And, and say for, alpha equals ten,
that's, about, you know, 15 zeroes, ten to
the minus 15.
So you can say to the programmer that if
you take alpha equals ten, this is
extremely, extremely, un.
Unlikely to happen.
And that's the kind of information the
programmer needs.
So that's hashing with separate chaining.
That's a typical calculation using classic
occupancy distribution in some of
the[UNKNOWN] that we did in, in lecture
four.
The other hashing method is called linear
probing.
In this method we throw the balls into the
urns but we only leave room for one ball.
And evrything is fine, until we get, a
collision where, And Erin would take two
balls and, we know from the birthday
problem, that's going to happen relatively
soon usually.
And when it happens, we just scan to the
right till we find an empty urn.
Now you don't want to do this if the table
starts to get full, as we'll see, but,
still, we're going to want to know, Have
analysis that tell us the, the average
number of collisions when we use this
algorithm.
And it's a relatively easy algorithm to
implement as well, and found in standard
algorithms books as well.
So, so that's the key question.
What's the average number of probes to
find one of the keys if you use this
algorithm, hashing with linear probing.
Well this was proven over 50 years ago by
Kanuf to be this sum, from k bigger than
0.
Of n over m, then minus 1 over m down to n
minus k, plus 1, over m.
Which, is, really, well, the proof is
given, in ten pages, in the textbook, it
really was a landmark result.
People who are thinkin this is too
dificult a problem, to really address, and
Knuth was able to show this result.
And if he let the table get full, he let n
and get to n and it's a Ramanujan
function.
And if you don't let the table get full
Which, if we don't in practice say don't
let it get more than half full, then it's
going to be one over one minus alpha.
Then we let it get more than half full,
then it's about two probes.
So in practice that's a very important
result.
Now.
Just want to tell a little bit of story.
So Knuth has, Knuth smokes four volumes
now and more planned.
And in volume three there is one footnote.
And Knuth taught that good writers don't
use footnotes in technical writing.
But he said he couldn't resist putting in
this one footnote that said that he
formulated this derivation.
It was the first non trivial algorithm he
had ever analyzed satisfactorily.
And he says it had a strong influence on
this structure of these books.
And it really is, the analysis of
algorithms began, was when, Canute solved
this problem.
Now when Philippe and I, wrote the,
introduction to analysis of algorithms
textbook.
And we're learning about, Analytic
Commonatorics, it, it seemed reasonable
that we should be able to, analyze linear
probing with the symbolic method.
So we couldn't, resist putting in one
footnote in are book either, And that one
said, that we don't know the answer to
this exercise.
And we couldn't figure out how to do use
the symbolic method to analyze linear
programming.
It seemed like the answer was so simple
and so similar to birthday and coupon
collector that we should be able to get
it.
And really we put this in as a challenge
to students and researchers.
Really you know, we should be able to do
this one.
And it took some years, but eventually and
you can read about this on.
In the 2nd addition of the book.
Turns out this problem has very deep
connections to properties of combinatorial
objects, like random graphs.
The gambler ruined problem, path links and
trees and many other classic algorithms.
And it's explained by a distribution
called an aerie law a very fascinating
Amount of mathematics to ex, explain this.
Uh,[cough] and, and this Knuth was one of
the people who solved it and Felipe and
some co-authors solved it as well.
Although actually still we don't quite
exactly precisely know the answer to this
exercise we know.
Quite a bit so there's actually still a
footnote left in the second edition.
But linear programming is worth studying
to see both the, the potential and the
limitations of what we know about analysis
of algorithms at this point.
One of the foundations mentioned here is
properties of mappings and that's what
we're going to talk about next.