1
00:00:00,012 --> 00:00:06,728
I just want to briefly discuss hash
tables, because, they're quite, closely

2
00:00:06,728 --> 00:00:10,727
related to, words an balls and urns
problems.

3
00:00:10,728 --> 00:00:15,446
But, won't, won't spend a lot of time and
lecture on it.

4
00:00:15,446 --> 00:00:22,573
There's more information, in the book.
So we, we talked, just briefly about the

5
00:00:22,573 --> 00:00:26,815
balls and urns model.
Of course, this is very heavily studied in

6
00:00:26,815 --> 00:00:31,219
classical, combinatorics.
And so we talked about, well what's

7
00:00:31,219 --> 00:00:36,251
probability that no urn has more than one
ball, what's the probability that no urn

8
00:00:36,251 --> 00:00:40,808
is empty, you might want to know how many
empty urns there are...

9
00:00:40,808 --> 00:00:47,447
How many urns have K balls and so forth
These so called occupancy problems are,

10
00:00:47,447 --> 00:00:51,943
are well studied dating back many, many
decades.

11
00:00:51,944 --> 00:00:59,026
So in, in the classical result is simply
from the binomial distribution.

12
00:00:59,027 --> 00:01:04,018
And the probability, and we looked at
this, before, when we talked about

13
00:01:04,018 --> 00:01:07,430
asymptotics.
The probability that a value occurs K

14
00:01:07,430 --> 00:01:12,656
times, a given value occurs K times in a
random M word of length N, is N choose K,

15
00:01:12,656 --> 00:01:16,248
one over M to the K, one minus one over M
to the N minus K.

16
00:01:16,249 --> 00:01:22,676
That is you get your value, k times the
probability of 1 over n and the other

17
00:01:22,676 --> 00:01:28,744
values are not yours with probability of 1
minus over m to the n minus k.

18
00:01:28,744 --> 00:01:33,704
So that's, given[UNKNOWN] probability
given sk balls.

19
00:01:33,705 --> 00:01:39,619
Now we looked ed at the Poisson
approximation that, works for the

20
00:01:39,619 --> 00:01:47,446
situation where, n over n is, is alpha and
it's fixed, and k is a, a small constant,

21
00:01:47,447 --> 00:01:51,643
that's the so called Poisson
approximation.

22
00:01:51,644 --> 00:01:56,783
And we showed how to come up with that
approximation in.

23
00:01:56,783 --> 00:02:03,085
When we talked about asymptotics.
So, And this is a very good,

24
00:02:03,086 --> 00:02:09,119
approximation.
So, for example, this, plot gives for,

25
00:02:09,120 --> 00:02:13,648
This is for alpha equals 10.
So n equals 10,000.

26
00:02:13,648 --> 00:02:18,206
M equals 1,000.
Some, that's, a plot of the binomial

27
00:02:18,206 --> 00:02:21,478
distribution.
So, it's centered at ten.

28
00:02:21,478 --> 00:02:27,651
And, that's, that's where the peak is.
And this is the Poisson approximation, for

29
00:02:27,651 --> 00:02:33,530
that same case, that alpha equals to ten.
And the curves here are nearly identical.

30
00:02:33,531 --> 00:02:39,245
And so that, the Poisson approximations
are a little bit easier to work with.

31
00:02:39,246 --> 00:02:45,306
So, that's why so, often used.
So they, an application, is in hashing

32
00:02:45,306 --> 00:02:49,132
algorithms.
So people in computer science are very

33
00:02:49,132 --> 00:02:54,160
familiar with these algorithms.
I'll just briefly describe them for,

34
00:02:54,161 --> 00:02:57,574
people.
The in, in math that may be you haven't

35
00:02:57,574 --> 00:03:01,145
seen them.
They're very well covered in books on

36
00:03:01,145 --> 00:03:07,131
algorithm like our book or[UNKNOWN] book,
the ideas we want any efficient way to put

37
00:03:07,131 --> 00:03:12,100
key value pairs in a simple table.
And we talked about this for binary search

38
00:03:12,100 --> 00:03:15,317
strings.
Drives, and we want to search for the

39
00:03:15,317 --> 00:03:18,560
table for the pair corresponding to a
given key.

40
00:03:18,561 --> 00:03:24,226
So the scratching, hashing strategy is to
come up with a function that maps each key

41
00:03:24,226 --> 00:03:27,483
onto a random value between zero and N
minus one.

42
00:03:27,483 --> 00:03:33,568
And then develop a collision strategy to
figure out what to do when two keys hash

43
00:03:33,568 --> 00:03:38,430
to the same value.
And the basic algorithm of that we'll talk

44
00:03:38,430 --> 00:03:42,166
about.
One's called separate channing where we.

45
00:03:42,166 --> 00:03:45,171
And essentially represent the urn with a
length list.

46
00:03:45,171 --> 00:03:49,934
And another one's called linear probing
where we just use an array and we never

47
00:03:49,934 --> 00:03:54,088
let two get in the same place where we
scan through the empty spots on the

48
00:03:54,088 --> 00:03:57,317
collision.
And I'll talk about briefly about both of

49
00:03:57,317 --> 00:04:01,754
those algorithms.
And the model that we use is this idea

50
00:04:01,754 --> 00:04:06,732
that the hash function.
We assume what's called the uniform

51
00:04:06,732 --> 00:04:13,335
hashing assumption, that the hash function
maps each key into a random value between

52
00:04:13,335 --> 00:04:18,240
0 and N minus 1.
And it's been shown to be not so difficult

53
00:04:18,240 --> 00:04:25,760
for typical types of keys to get hash
functions that reasonably approximate this

54
00:04:25,760 --> 00:04:29,642
uniform assumption.
So that's the set up.

55
00:04:29,643 --> 00:04:35,463
So hashing with separate chaining is
really easy to implement.

56
00:04:35,463 --> 00:04:42,378
And this is just a diagram from our
algorithms book that shows a hash table of

57
00:04:42,378 --> 00:04:46,217
size five.
And so the keys are letters and then the

58
00:04:46,217 --> 00:04:51,778
hash values are supposed to be random
values between zero and five it's just a

59
00:04:51,778 --> 00:04:55,241
word.
So the sequence of hash values is just a

60
00:04:55,241 --> 00:04:59,848
random word.
And then we store the letters in lists

61
00:04:59,848 --> 00:05:05,046
indexed by the hash values.
So those are the urns and the keys, and

62
00:05:05,046 --> 00:05:10,879
the associated values are, are the balls.
So that's easy to implement.

63
00:05:10,879 --> 00:05:16,296
And of course we're going to be interested
in how long these lists are.

64
00:05:16,297 --> 00:05:23,000
So again this is the just the balls and
urns model for hashing with separate

65
00:05:23,000 --> 00:05:27,512
chaining.
And, and probably spending too many time,

66
00:05:27,512 --> 00:05:35,007
too much time on animations.
But so it, what we want to know is when

67
00:05:35,007 --> 00:05:42,757
we're going to search for an item in this
we're going to have to go through all the

68
00:05:42,757 --> 00:05:47,801
balls in the urn.
And so we want to know The average number

69
00:05:47,801 --> 00:05:51,723
of balls in each urn, say.
Well that's obvious.

70
00:05:51,723 --> 00:05:53,899
There's n balls.
There's m urns.

71
00:05:53,899 --> 00:05:56,944
On average there's n over m balls in each
urn.

72
00:05:56,944 --> 00:05:59,908
And actually that doesn't depend on
anything.

73
00:05:59,909 --> 00:06:05,298
It's not very helpful at all.
If all the balls fall in one urn, still

74
00:06:05,298 --> 00:06:09,486
your average number of balls per urn is n
over m.

75
00:06:09,486 --> 00:06:15,727
It doesn't have to be random even, so that
observation is not much help.

76
00:06:15,727 --> 00:06:19,566
So, and we know the probability has k
balls.

77
00:06:19,566 --> 00:06:26,000
That's the occupance distribution.
Generally we're going to have, try to keep

78
00:06:26,000 --> 00:06:32,566
the number of urns large enough that our
number of balls per urn is a constant like

79
00:06:32,566 --> 00:06:37,329
alpha so we know that.
But what the programmer wants to know is

80
00:06:37,329 --> 00:06:42,797
something about what's the chances that
they're distributed evenly.

81
00:06:42,798 --> 00:06:47,864
So, we have to do a little more math to,
provide that answer.

82
00:06:47,865 --> 00:06:54,077
So here's what a programmer might say.
So if I make sure that, N is big enough so

83
00:06:54,077 --> 00:06:57,659
that N over M is less than some constant
output.

84
00:06:57,660 --> 00:07:00,432
But.
And it turns out to be not difficult to do

85
00:07:00,432 --> 00:07:03,683
that.
And the average number approach for search

86
00:07:03,683 --> 00:07:06,154
is going to be less than alpha.
I know that.

87
00:07:06,154 --> 00:07:11,128
But what's the chance that some search'll
use way to many pro, probes, under the

88
00:07:11,128 --> 00:07:14,017
uniform hashing assumption.
Say five alpha.

89
00:07:14,017 --> 00:07:19,382
Per probes.
Well, that's actually not too difficult to

90
00:07:19,382 --> 00:07:23,748
calculate.
So, what it is, is we know the probability

91
00:07:23,748 --> 00:07:29,054
for k probes, we can sum that for all k
bigger than 5 alpha.

92
00:07:29,054 --> 00:07:36,967
And the trick is to use Stirling's formula
to bound k factorial and then if you do

93
00:07:36,967 --> 00:07:45,634
that then we get something that converges
very rapidly, so it 's something like e to

94
00:07:45,634 --> 00:07:49,802
the minus alpha.
Times E over five to the five alpha.

95
00:07:49,802 --> 00:07:56,760
And, and say for, alpha equals ten,
that's, about, you know, 15 zeroes, ten to

96
00:07:56,760 --> 00:08:00,570
the minus 15.
So you can say to the programmer that if

97
00:08:00,570 --> 00:08:05,542
you take alpha equals ten, this is
extremely, extremely, un.

98
00:08:05,542 --> 00:08:09,903
Unlikely to happen.
And that's the kind of information the

99
00:08:09,903 --> 00:08:14,821
programmer needs.
So that's hashing with separate chaining.

100
00:08:14,821 --> 00:08:20,623
That's a typical calculation using classic
occupancy distribution in some of

101
00:08:20,623 --> 00:08:24,640
the[UNKNOWN] that we did in, in lecture
four.

102
00:08:24,641 --> 00:08:28,666
The other hashing method is called linear
probing.

103
00:08:28,667 --> 00:08:36,879
In this method we throw the balls into the
urns but we only leave room for one ball.

104
00:08:36,879 --> 00:08:45,973
And evrything is fine, until we get, a
collision where, And Erin would take two

105
00:08:45,973 --> 00:08:52,025
balls and, we know from the birthday
problem, that's going to happen relatively

106
00:08:52,025 --> 00:08:56,110
soon usually.
And when it happens, we just scan to the

107
00:08:56,110 --> 00:09:01,766
right till we find an empty urn.
Now you don't want to do this if the table

108
00:09:01,766 --> 00:09:08,482
starts to get full, as we'll see, but,
still, we're going to want to know, Have

109
00:09:08,482 --> 00:09:14,278
analysis that tell us the, the average
number of collisions when we use this

110
00:09:14,278 --> 00:09:18,167
algorithm.
And it's a relatively easy algorithm to

111
00:09:18,167 --> 00:09:23,502
implement as well, and found in standard
algorithms books as well.

112
00:09:23,502 --> 00:09:29,042
So, so that's the key question.
What's the average number of probes to

113
00:09:29,042 --> 00:09:35,081
find one of the keys if you use this
algorithm, hashing with linear probing.

114
00:09:35,082 --> 00:09:46,170
Well this was proven over 50 years ago by
Kanuf to be this sum, from k bigger than

115
00:09:46,170 --> 00:09:49,601
0.
Of n over m, then minus 1 over m down to n

116
00:09:49,601 --> 00:09:56,572
minus k, plus 1, over m.
Which, is, really, well, the proof is

117
00:09:56,572 --> 00:10:03,148
given, in ten pages, in the textbook, it
really was a landmark result.

118
00:10:03,148 --> 00:10:10,089
People who are thinkin this is too
dificult a problem, to really address, and

119
00:10:10,090 --> 00:10:17,489
Knuth was able to show this result.
And if he let the table get full, he let n

120
00:10:17,489 --> 00:10:21,408
and get to n and it's a Ramanujan
function.

121
00:10:21,408 --> 00:10:28,068
And if you don't let the table get full
Which, if we don't in practice say don't

122
00:10:28,068 --> 00:10:33,641
let it get more than half full, then it's
going to be one over one minus alpha.

123
00:10:33,641 --> 00:10:38,307
Then we let it get more than half full,
then it's about two probes.

124
00:10:38,307 --> 00:10:41,664
So in practice that's a very important
result.

125
00:10:41,665 --> 00:10:46,948
Now.
Just want to tell a little bit of story.

126
00:10:46,948 --> 00:10:54,260
So Knuth has, Knuth smokes four volumes
now and more planned.

127
00:10:54,260 --> 00:11:02,756
And in volume three there is one footnote.
And Knuth taught that good writers don't

128
00:11:02,756 --> 00:11:08,320
use footnotes in technical writing.
But he said he couldn't resist putting in

129
00:11:08,320 --> 00:11:12,808
this one footnote that said that he
formulated this derivation.

130
00:11:12,808 --> 00:11:17,859
It was the first non trivial algorithm he
had ever analyzed satisfactorily.

131
00:11:17,860 --> 00:11:23,061
And he says it had a strong influence on
this structure of these books.

132
00:11:23,062 --> 00:11:30,274
And it really is, the analysis of
algorithms began, was when, Canute solved

133
00:11:30,274 --> 00:11:35,173
this problem.
Now when Philippe and I, wrote the,

134
00:11:35,173 --> 00:11:39,829
introduction to analysis of algorithms
textbook.

135
00:11:39,830 --> 00:11:45,948
And we're learning about, Analytic
Commonatorics, it, it seemed reasonable

136
00:11:45,948 --> 00:11:51,673
that we should be able to, analyze linear
probing with the symbolic method.

137
00:11:51,674 --> 00:11:57,814
So we couldn't, resist putting in one
footnote in are book either, And that one

138
00:11:57,814 --> 00:12:01,594
said, that we don't know the answer to
this exercise.

139
00:12:01,594 --> 00:12:06,054
And we couldn't figure out how to do use
the symbolic method to analyze linear

140
00:12:06,054 --> 00:12:09,610
programming.
It seemed like the answer was so simple

141
00:12:09,610 --> 00:12:14,440
and so similar to birthday and coupon
collector that we should be able to get

142
00:12:14,440 --> 00:12:17,604
it.
And really we put this in as a challenge

143
00:12:17,604 --> 00:12:23,201
to students and researchers.
Really you know, we should be able to do

144
00:12:23,201 --> 00:12:28,153
this one.
And it took some years, but eventually and

145
00:12:28,153 --> 00:12:32,550
you can read about this on.
In the 2nd addition of the book.

146
00:12:32,550 --> 00:12:38,540
Turns out this problem has very deep
connections to properties of combinatorial

147
00:12:38,540 --> 00:12:44,022
objects, like random graphs.
The gambler ruined problem, path links and

148
00:12:44,022 --> 00:12:49,854
trees and many other classic algorithms.
And it's explained by a distribution

149
00:12:49,854 --> 00:12:56,057
called an aerie law a very fascinating
Amount of mathematics to ex, explain this.

150
00:12:56,057 --> 00:13:01,895
Uh,[cough] and, and this Knuth was one of
the people who solved it and Felipe and

151
00:13:01,895 --> 00:13:07,131
some co-authors solved it as well.
Although actually still we don't quite

152
00:13:07,131 --> 00:13:11,499
exactly precisely know the answer to this
exercise we know.

153
00:13:11,499 --> 00:13:17,579
Quite a bit so there's actually still a
footnote left in the second edition.

154
00:13:17,579 --> 00:13:23,705
But linear programming is worth studying
to see both the, the potential and the

155
00:13:23,705 --> 00:13:29,150
limitations of what we know about analysis
of algorithms at this point.

156
00:13:29,151 --> 00:13:40,113
One of the foundations mentioned here is
properties of mappings and that's what

157
00:13:40,113 --> 00:13:44,033
we're going to talk about next.