«
»
▶
Lecture Copilot
Lectures
Ask
Exam prep
Help
Sign in
← Introduction to Algorithms (MIT 6.006)
L4
Hashing
Ask the lectures
Every answer cites the moment it comes from. Click a citation to jump there.
Your question
Ask
00:00
Introduction to Hashing and Set Structures
04:11
Lower Bound for Find Operations
16:09
Direct Access Array
38:46
Universal Hash Functions
45:11
Analyzing Expected Chain Lengths
Transcript
00:00
Welcome to the fourth lecture of 6006.
00:16
Today, we are going to be talking about hashing.
00:20
Last lecture on Tuesday,
00:23
Professor Solomon was talking about set data structures,
00:28
right, storing things so that you can query items by their key,
00:34
right, by what they intrinsically are,
00:37
versus what Professor Domain was talking about last week,
00:40
which was sequence data structures,
00:41
where we impose an external order on these items,
00:45
and we want you to maintain those.
00:48
But I'm not supporting operations
00:51
where I'm looking stuff up based on what they are.
00:54
That's what the set interface is for.
00:56
So we're going to be talking a little bit more
00:58
about the set interface today.
01:00
So last, on Tuesday,
01:02
you saw two ways of implementing the set interface,
01:06
right, one using just an unsorted array,
01:09
just I threw these things in an array,
01:12
and I could do a linear scan of my items
01:14
to support basically any of these operations.
01:17
It's a little exercise you can go through.
01:19
I think they show it to you in the recitation notes,
01:21
but if you'd like to implement it for yourself, that's fine.
01:26
And then we saw a slightly better data structure,
01:29
at least for the find operations.
01:31
Can I look something up,
01:33
whether this key is in my set interface?
01:38
We can do that faster.
01:39
We can do that in log n time
01:41
with a build overhead that's about n log n, right?
01:46
Because we showed you three ways to sort.
01:49
Two of them were n squared.
01:50
One of them was n log n,
01:53
which is as good as we showed you how to do yesterday.
01:57
So the question then becomes,
01:58
can I build that data structure faster?
02:01
That'll be a subject of next week's Thursday lecture.
02:04
But this week, we're going to concentrate
02:05
on this static find, right?
02:09
We got log n,
02:10
which is an exponential improvement over linear, right?
02:15
But the question here now becomes,
02:18
can I do faster than log n time?
02:22
And what we're going to do
02:23
at the first part of this lecture
02:24
is show you that no.
02:27
What's up?
02:28
What? No? Okay.
02:31
That you can't do faster than log n time
02:34
in the caveat that we are in a slightly more
02:37
restricted model of computation.
02:40
That we were,
02:41
than what we introduced to you a couple weeks ago.
02:46
And then show if we're not in that,
02:48
that more constrained model of computation,
02:50
we can actually do faster, right?
02:53
And doing faster,
02:55
I mean, log n's already pretty good, right?
02:57
Log n is not going to be larger than like 30
03:01
for any problem that you're going to be talking about
03:06
in the real world on real computers.
03:09
But a factor of 30 is still bad, right?
03:13
I would prefer to do faster with those constant factors
03:17
when I can.
03:18
It's not a constant factor.
03:19
It's a logarithmic factor.
03:20
But you get what I'm saying.
03:22
Okay.
03:22
So what we're going to do is first prove that
03:25
you can't do faster for find.
03:27
Does everyone understand,
03:29
remember what find key meant, right?
03:31
I have a key.
03:33
I have a bunch of items that have keys associated with them.
03:36
And I want to see if one of the items that I'm storing
03:39
contains a key that is the same as the one that I searched for, right?
03:43
The item might contain other things.
03:46
But in particular, it has a search key that I'm maintaining the set on
03:50
so that it supports find operations, search operations,
03:54
based on that key quickly.
03:56
Does that make sense?
03:58
So there's the find one that we want to improve.
04:00
And we also want to improve this insert, delete.
04:03
We want to make this data structure dynamic, right?
04:06
Because we might do those operations quite a bit.
04:11
And so this lecture is about optimizing those three things.
04:15
Okay.
04:15
So first I'm going to show you that we can't do faster than log n
04:20
for find, which is a little weird.
04:23
Okay.
04:24
The model of computation I'm going to be proving this lower bound on,
04:29
right?
04:29
I'm saying that how I'm going to approach this is I'm going to say
04:32
that any way that I store these, the items that I'm storing
04:38
in this data structure, for any way I store these things,
04:44
any algorithm of this certain type is going to require
04:48
at least logarithmic time.
04:50
That's what we're going to try to prove.
04:52
And the model of computation that's weaker than what we've been
04:56
talking about previously is what I'm going to call
04:59
the comparison model.
05:03
And a comparison model means is that the items,
05:07
the objects I'm storing, I can kind of think of them as black boxes.
05:12
I don't get to touch these things, except the only way that I can
05:15
distinguish between them is to say, given a key and an item or two items,
05:25
I can do a comparison on those keys, right?
05:28
Are these keys the same?
05:31
Is this key bigger than this one?
05:33
Is it smaller than this one?
05:35
Those are kind of the only operations I get to do with them.
05:38
I don't get to look at what the, say, if the keys are numbers,
05:41
I don't get to look at what number that is, right?
05:44
I just get to take two keys and compare them.
05:46
And actually, all of the search algorithms that we saw on Tuesday
05:51
were comparison sort algorithms, right?
05:53
What you did was you stepped through the program.
05:56
At some point, you came to a branch, and you looked at two keys,
06:01
and you branched based on whether one key was bigger than another, right?
06:06
That was a comparison.
06:07
And then you moved some stuff around, but that was the general paradigm.
06:11
Those three sorting operations lived in this comparison model, right?
06:17
You've got comparison operations like, are they equal, less than, greater than,
06:25
maybe greater than or equal, less than or equal, right?
06:28
Generally, you have all these operations that you could do, maybe not equal, right?
06:34
But the key thing here is that there are only two possible outputs
06:39
to each of these comparators, right?
06:42
There's only two things.
06:43
There's only one thing that I can branch on.
06:46
It's going to branch into two different lines, right?
06:49
It's either true, and I do some other computation,
06:52
or it's false, and I'll do a different set of computation, right?
06:56
Does that make sense?
06:58
So what I'm going to do is I'm going to view an algorithm in the comparison model
07:04
as what I like to call a decision tree, right?
07:08
So if I specify an algorithm to you, the first thing it's going to do,
07:11
if I don't compare items at all, I'm kind of screwed,
07:15
because I'll never be able to tell if my key is in there or not.
07:17
So I have to do some comparisons.
07:19
So, you know, I'll do some computation, you know,
07:23
maybe I find out the length of the array, and I do some constant time stuff.
07:27
But at some point, I'll do a comparison, and I'll branch, right?
07:31
I'll come to this node, and if the comparison, like maybe a less than, right?
07:37
If it's true, I'm going to go this way in my computation,
07:41
and if it's false, I'm going to go this way in my computation, right?
07:44
And I'm going to keep doing that with various comparisons, sure,
07:53
until I get down here to some leaf in which I'm not branching, right?
08:04
The internal nodes here are representing comparisons,
08:07
but the leaves are representing I stopped my computation.
08:11
I'm outputting something.
08:12
Does that make sense, what I'm kind of trying to do?
08:16
I'm kind of changing my algorithm to be put in this kind of graphical way
08:22
where I'm branching what my program could possibly do
08:26
based on the comparisons that I do, right?
08:29
I'm not actually counting the rest of the work that the program does, right?
08:34
I'm really only looking at the comparisons, right?
08:37
Because I know that I'll need to compare some things eventually
08:41
to figure out what my items are,
08:44
and if that's the only way I can distinguish items,
08:47
then I have to do those comparisons to find out, right?
08:50
Does that make sense?
08:51
All right, so what I have is a binary tree
08:55
that's representing the comparisons done by my algorithm.
08:59
Okay, so it starts at one comparison, and then it branches.
09:04
How many leaves must I have in my tree?
09:10
What does that question mean, right?
09:12
Like in terms of the program?
09:16
What's that?
09:17
The number of comparisons.
09:18
The number of comparisons.
09:19
No, that's the number of internal nodes that I have in the algorithm,
09:23
and actually the number of comparisons that I do
09:25
in an execution of the algorithm
09:27
is just along a path from here to a leaf, right?
09:32
So what do the leaves actually represent?
09:34
Those that represent outputs, right?
09:36
I'm going to output something here.
09:38
And, yeah?
09:40
The number of items.
09:42
Okay, so I need at least...
09:45
So what is the output to my search algorithm?
09:47
Maybe it's an index of an item that contains this key,
09:52
or maybe I return the item is the output, right?
09:57
The item of the thing I'm storing, and I'm storing n things,
10:00
so I need at least n outputs, right?
10:04
Because I need to be able to return any of the items
10:07
that I'm storing based on a different search key parameter
10:10
if it's going to be correct.
10:12
I actually need one more output.
10:13
Why do I need one more output?
10:17
If it's not in there, right?
10:20
Right, so any correct comparison searching algorithm,
10:26
I'm doing some comparisons to find this thing,
10:29
needs to have at least n plus 1 leaves, right?
10:38
Otherwise, it can't be correct,
10:39
because I could look up the one that I'm not returning in that set,
10:44
and it would never be able to return that value.
10:47
Does that make sense?
10:49
Yeah?
10:51
What's n?
10:52
n is always the number...
10:53
For a data structure,
10:54
n is the number of things stored in that data structure at that time, right?
10:58
So the number of items in the data structure.
11:00
That's what it means in all of these tables.
11:03
Any other questions?
11:03
Okay, so now we get to the fun part.
11:09
How many comparisons does this algorithm have to do?
11:16
Yeah, up there.
11:19
What's up?
11:22
All right, your colleague is jumping ahead for a second,
11:25
but really, I have to do as many comparisons,
11:28
in the worst case,
11:30
as the longest root-to-leaf path in this tree, right?
11:35
Because as I'm executing this algorithm,
11:37
I'll go down this thing, always branching down,
11:42
and at some point I'll get to a leaf,
11:44
and in the worst case,
11:45
if I happen to need to return this particular output,
11:50
then I'll have to walk down the longest thing, right?
11:54
It's the longest path.
11:57
So, and the longest path is the same as the height of the tree.
12:01
Okay?
12:01
So the question then becomes,
12:03
what is the minimum height
12:05
of any binary tree that has at least n plus 1 leaves?
12:14
Do you ever understand why we're asking that question?
12:18
Okay, so in rest...
12:18
Yeah?
12:19
Could you go over again why it needs n plus 1 leaves?
12:22
Why it needs n plus 1 leaves?
12:24
If it's a correct algorithm,
12:25
it needs to return...
12:27
It needs to be able to return
12:28
any of the n items that I'm storing,
12:31
or say that the key that I'm looking for is not there.
12:35
Great question.
12:37
Okay, so what is the minimum height
12:40
of any binary tree
12:41
that has n plus 1...
12:43
at least n plus 1 leaves?
12:46
You can solve that...
12:47
you can actually state a recurrence for that and solve that.
12:50
You're going to do that in your recitation,
12:52
but it's log n, right?
12:53
Like, the best you can do
12:54
is if this is a balanced binary tree, right?
12:57
So the min height
13:00
is going to be at least
13:05
log n height, right?
13:11
Or the min height is logarithmic, right?
13:17
So it's actually theta right here,
13:19
but if I just said height here,
13:21
I would be lower bounding the height, right?
13:24
If I could have a linear height, right?
13:26
If I just chained comparisons down one by one,
13:30
if I was doing a linear search, for example, right?
13:33
All right, so this is saying
13:35
that if I'm just restricting to comparisons,
13:37
I have to spend at least logarithmic time
13:40
to be able to find
13:41
whether this key is in my set, right?
13:46
But I don't want logarithmic time.
13:47
I want faster.
13:49
So how can I do that?
13:51
I have one operation
13:53
in my model of computation
13:54
I presented a couple weeks ago
13:56
that allows me to do faster,
13:58
which allows me to do something stronger
14:01
than comparisons.
14:03
Comparisons have a constant branching factor.
14:06
In particular, if I do this operation,
14:10
this constant time operation,
14:11
I can branch to two different locations, right?
14:17
It's like an if kind of situation,
14:19
if or else, right?
14:21
And in fact, if I had constant branching factor
14:24
for any constant here, right?
14:28
If I had three or four,
14:29
if I was bounded by a constant,
14:31
the height of this tree would still be bounded
14:33
by a log base, the constant,
14:35
of that number of leaves, okay?
14:39
So I need, in some sense,
14:40
to be able to branch a non-constant amount, right?
14:45
So how can I branch a non-constant amount?
14:49
This is a little tricky, right?
14:50
We had this really neat operation
14:54
in the random access machine
14:57
that we could randomly go to any place in memory
15:02
in constant time based on a number, right?
15:07
That was a super powerful thing
15:09
because within a single constant time operation,
15:11
I could go to any space in memory, right?
15:15
That's potentially much larger
15:17
than linear branching factor
15:18
depending on the size of my model
15:20
and the size of my machine, right?
15:22
So that's a very powerful operation.
15:24
Can we use that to find quicker?
15:27
Anyone have any ideas?
15:31
Sure.
15:33
We're going to get to hashing in a second,
15:35
but this is a simpler concept than hashing,
15:40
something you probably are familiar with already.
15:44
We've kind of been using it implicitly
15:46
in some of our sequence data structure things.
15:48
What we're going to do is
15:52
if I have an item that has key 10,
15:56
I'm going to keep an array
15:58
and store that item
16:00
10 spaces away from the front of the array, right?
16:05
At index 9 or the 10th index.
16:09
Does that make sense?
16:11
If I store that item
16:12
at that location in memory,
16:14
I can use this random access to that location
16:19
and see if there's something there.
16:21
If there's something there, I return that item.
16:22
Does that make sense?
16:24
This is what I call a direct access array.
16:29
It's really no different than the arrays
16:32
that we've been talking about earlier in the class.
16:36
We've got an array.
16:40
And if I have an item here with key equals 10,
16:46
I'll stick it here in the 10th place.
16:50
Now, I can only now store one item
16:53
with the key 10 in my thing.
16:57
And that's one of the stipulations
16:58
we had on our set data structures, right?
17:00
If we tried to insert something
17:01
with the same key
17:03
as something already stored there,
17:04
we're going to replace the item, right?
17:06
That's what the semantics
17:07
of our set interface was.
17:09
But that's okay.
17:10
That's satisfying the conditions
17:12
of our set interface.
17:14
So if we store it there,
17:16
that's fantastic.
17:17
How long does it take to find
17:19
if we have an item with the key 10?
17:22
It takes constant time.
17:24
Worst case.
17:25
Great.
17:25
How about inserting or deleting something?
17:30
What's that?
17:32
Again, constant time.
17:34
We've solved all of our problems.
17:36
This is amazing.
17:39
Okay.
17:40
What's not amazing about this?
17:42
Why don't we just do this all the time?
17:47
Yeah?
17:49
Do you mean, like,
17:50
you don't know how high the numbers go?
17:53
I don't know how high the numbers go, right?
17:56
So let's say I'm storing, I don't know,
17:59
a number associated with the 300 or 400 of you
18:03
that are in this classroom, right?
18:07
But I'm storing your MIT IDs.
18:10
How big are those numbers?
18:12
Those are like nine-digit numbers, right?
18:14
Pretty long numbers.
18:16
So what I would need to do in,
18:19
if I was storing your keys as MIT IDs,
18:23
I would need an array that has indices
18:26
that span the entire space
18:28
of nine-digit numbers, right?
18:32
That's like 10 to the nine, or nine to,
18:36
10 to the nine, thank you.
18:38
10 to the nine is the size of a direct access array
18:43
I would have to build to be able to use this,
18:46
this technique to create a direct access array
18:52
to search on your MIT IDs
18:54
when there's only really 300 of you in here, right?
18:57
So 300 or 400 is an N that's much smaller
19:01
than the size of the numbers that I'm trying to store.
19:04
What I'm going to use as a variable
19:05
to talk about the size of the numbers I'm storing,
19:09
I'm going to say U is the maximum size
19:11
of any number that I'm storing.
19:13
Okay?
19:13
It's the size of the universe of space of keys
19:16
that I'm storing.
19:17
Does that make sense?
19:19
Okay, so to instantiate a direct access array
19:23
of that size, I have to allocate that amount of space.
19:26
And so if that is much bigger than N,
19:30
then I'm kind of screwed, right?
19:33
Because I'm using much more space,
19:35
and these order operations are bad also, right?
19:38
Because essentially, if I am storing these things
19:43
non-continuously, I kind of just have to scan down
19:47
the thing to find the next element, for example, right?
19:52
Okay, what's your question?
19:54
Is a direct access array a sequence data structure?
19:56
A direct access array is a set data structure.
19:59
That's why it's a set interface up there.
20:02
So your colleague is asking whether you can use
20:08
a direct access array to implement a set,
20:10
I mean a sequence.
20:11
And actually, I think you'll see in your recitation notes,
20:14
you have code that can take a set data structure
20:18
and implement a sequence data structure
20:20
and take a sequence data structure
20:22
and implement a set data structure.
20:24
They just won't necessarily have very good run time.
20:26
So this direct access array semantics
20:29
is really just good for these specific set operations.
20:34
Does that make sense?
20:35
Yeah.
20:35
What is U?
20:36
U is the size of the largest key
20:39
that I'm allowed to store.
20:40
Does that make sense?
20:41
The direct access array is supporting up to U size keys.
20:47
Does that make sense?
20:48
Okay.
20:49
We're going to move on for a second.
20:50
So that's the problem, right?
20:53
When U, largest key,
21:00
we're assuming integers here, right?
21:04
Integer keys.
21:06
So in the comparison model,
21:10
we could store any arbitrary objects
21:12
that supported a comparison.
21:14
Here, we really need to have integer keys
21:17
or else we're not going to be able to use those as addresses.
21:21
So we're making an assumption on the inputs
21:25
that I can only store integers now.
21:27
I can't store arbitrary objects, items with keys.
21:31
And in particular, I also need to,
21:33
this is a subtlety that's in the WordRAM model,
21:35
how can I be assured that these keys
21:38
can be looked up in constant time?
21:43
How does my CPU, this little CPU, right?
21:46
It's got some number of registers it can act upon.
21:49
How big are those registers?
21:53
What?
21:54
Well, so right now they're 64 bits,
21:57
but in general, they're W.
21:59
They're the size of your word on your machine.
22:02
That's how many,
22:04
two to the W is the number of addresses I can access.
22:07
So implicitly, I'm kind of,
22:09
if I'm going to be able to use this direct access array,
22:11
I need to make sure that the U
22:13
is less than two to the W, right?
22:19
If I want these operations to run in constant time, right?
22:22
If I have keys that are much larger than this,
22:25
I'm going to need to do something else, okay?
22:28
But this is kind of the assumption.
22:30
In this class, when we give you like an array of integers
22:33
or an array of strings or something like that
22:35
on your problem set or on an exam, right?
22:38
The assumption is unless we give you
22:40
bounds on the size of those things, right?
22:45
Like the number of characters in your string
22:47
or the size of the number in the thing,
22:49
you can assume that those things will fit in
22:51
in one word of memory, okay?
22:58
W is the word size of your machine, right?
23:01
The number of bits that your machine
23:04
can do operations on in constant time.
23:08
Any other questions?
23:10
Okay, so we have this problem.
23:12
We're using way too much space, right?
23:15
When we have a large universe of keys.
23:17
So, how do we get around that problem?
23:23
Any ideas?
23:28
Sure.
23:29
Instead of storing some value,
23:31
you might be storing multiple values
23:34
in the areas of one.
23:35
Ah, okay.
23:36
So, what your colleague is saying,
23:39
instead of just storing one value at each place,
23:43
maybe store more than one value?
23:44
If we're using this idea, right,
23:49
where I am storing my key at the index of the key,
23:53
that's getting around us having to have unique keys
23:57
in our data structure.
23:58
It's not getting around this space usage problem.
24:02
Does that make sense?
24:04
We will end up storing multiple things at indices,
24:08
but there's another trick that I'm looking for right now, right?
24:13
We have a lot of space that we would need to allocate
24:17
for this data structure.
24:19
What's an alternative?
24:22
Instead of allocating a lot of space,
24:24
we allocate less space, right?
24:30
Let's allocate less space.
24:31
All right, so we have a really, like,
24:36
this is our space of keys, right, you, right?
24:39
But instead, I want to store those things
24:44
in a direct access array of maybe size n, right?
24:51
Something like the order of the things
24:54
that I'm going to be storing.
24:55
I'm going to relax that and say,
24:56
we're going to make this a length m
24:59
that's, you know, around the size
25:03
of the things I'm storing, okay?
25:05
And what I'm going to do is I'm going to try
25:09
to map this space of keys,
25:12
this large space of keys from, like,
25:14
0 to u minus 1 or something like that, right?
25:18
Down to a range that's 0 to m minus 1, okay?
25:23
Right?
25:24
I'm going to want a function.
25:26
This is what I'm going to call h,
25:28
which maps this range down to a smaller range.
25:40
Does that make sense?
25:41
I'm going to have some function
25:42
that takes that large space of keys,
25:45
sticks them down here, okay?
25:48
And instead of storing at an index of the key,
25:54
I'm going to put the key through this function,
25:57
the key space, into a compressed space
26:00
and store it at that index location.
26:04
Does that make sense?
26:06
Sure.
26:09
Oh, your colleague comes up with the question
26:14
I was going to ask right away,
26:15
which was, what's the problem here?
26:17
The problem is it's the potential
26:19
that we might have to store more than one thing
26:23
at the same index location, right?
26:27
If I have a function that maps this big space
26:30
down to this small space,
26:33
I've got to have multiple of these things
26:37
going to the same places here, right?
26:39
It can't be injective, right?
26:44
Just based on pigeonhole principle,
26:45
I have more of these things.
26:47
At least two of them have to go to something over here.
26:49
In fact, if I have, say,
26:52
u is bigger than n squared, for example, right?
26:57
For any function I give you
26:59
that maps this large space down to the small space,
27:03
n of these things will map to the same place, right?
27:07
So if I choose a bad function here,
27:10
then I'll have to store n things
27:14
at the same index location,
27:15
and if I go there, I have to kind of check to see
27:19
whether any of those are the things
27:21
that I'm looking for.
27:21
I haven't gained anything, right?
27:23
I really want a hash function
27:24
that will evenly distribute keys over this space, right?
27:32
Does that make sense?
27:34
But we have a problem here.
27:35
If we need to store multiple things
27:37
at a given location in memory,
27:41
I can't do that.
27:42
I have one thing I can put there.
27:43
So I have two options on how to deal
27:46
what I call collisions, right?
27:48
If I have two items here, like a and b,
27:52
these are different keys, right,
27:55
in my universe of space.
27:58
But it's possible that they both map down
28:02
to some hash that has the same value, right?
28:08
So where do I store it?
28:10
If I first hashed a, and a is, I put a there,
28:15
where do I put b?
28:21
There are kind of two options.
28:25
Is the second data structure perhaps a linked list
28:28
so that it can store multiple things?
28:31
Okay, so what your colleague was saying,
28:33
can I store this one as a linked list,
28:36
and then I can just insert a guy right next to where it was?
28:40
What's the problem there?
28:42
Are linked lists good with direct accessing by an index?
28:48
No, they're terrible with get at and set at, right?
28:51
They take linear time there, right?
28:53
So really the whole point of direct access array
28:55
is that there is an array underneath,
28:57
and I can do this index from arithmetic
28:59
and go down to the next thing.
29:01
So I really don't want to replace a linked list
29:03
as this data structure.
29:07
Yeah?
29:10
What's up?
29:13
We can make it really unlikely, sure.
29:17
I don't know what likely means
29:18
because I'm giving you a hash function,
29:21
one hash function,
29:22
and I don't know what the inputs are.
29:24
Yeah?
29:25
Go ahead.
29:26
We can instead store the items in the array somewhere
29:29
and hold the address.
29:31
Okay, right.
29:32
So there are actually two solutions here.
29:36
One is,
29:38
maybe if I choose M to be larger than N,
29:42
right,
29:42
there's going to be extra space in here.
29:44
I'll just stick it somewhere else
29:46
in the existing array.
29:48
Right?
29:49
How I find an open space is a little complicated,
29:52
but this is a technique called open addressing,
29:57
which is much more common
29:59
than the technique we're going to be talking about today
30:01
in implementations.
30:04
Python uses an open addressing scheme,
30:06
which is essentially find another place in the array
30:09
to put this collision.
30:11
But open addressing is notoriously difficult to analyze,
30:15
so we're not going to do that in this class.
30:16
There's a much easier technique
30:17
that we have an implementation for you
30:20
in the recitation handouts.
30:23
It's what your colleague up here,
30:26
I can't find him,
30:27
over there was saying
30:29
was instead of storing it somewhere else
30:31
in the existing direct access array down here,
30:35
which we usually call the hash table,
30:38
right,
30:40
instead of storing it somewhere else in that hash table,
30:44
we'll instead, at that key,
30:46
store a pointer to another data structure.
30:49
Right?
30:49
Some other data structure
30:51
that can store a bunch of things,
30:52
just like any sequence data structure,
30:54
like a dynamic array or a linked list or anything,
30:56
right?
30:57
All I need to do is be able to stick
30:59
a bunch of things on there
31:00
when there are collisions,
31:03
and then when I go up to look for that thing,
31:05
I'll just look through all of the things
31:07
in that data structure
31:09
and see if my key exists.
31:11
Does that make sense?
31:13
Now, we want to make sure
31:14
that those additional data structure,
31:16
structures which I'll call chains,
31:19
right,
31:19
we want to make sure
31:20
that those chains are short,
31:23
right?
31:24
I don't want them to be long,
31:26
right?
31:27
So what I'm going to do
31:27
is when I have this collision here,
31:29
instead I'll have a pointer to some,
31:31
I don't know,
31:32
maybe make it a dynamic array
31:33
or a linked list
31:34
or something like that,
31:35
and I'll put a here
31:36
and I'll put b here.
31:38
And then later,
31:39
when I look up key k,
31:42
right,
31:44
or look up key a or b,
31:46
let's look up key b,
31:48
I'll go to this hashed value here,
31:51
I'll put it through the hash function,
31:52
I'll go to this index,
31:53
I'll go to the data structure,
31:55
the chain associated with that index,
31:57
and I'll look at all of these items,
31:59
and I'm just going to do a linear find,
32:01
I'm going to look,
32:01
I could put any data structure here,
32:05
but I'm going to look at this one,
32:07
see if it's b,
32:08
it's not b,
32:09
look at this one,
32:10
it is b,
32:11
I return yes.
32:12
Does that make sense?
32:13
So this is an idea called chaining,
32:15
I can put anything I want there.
32:17
Commonly,
32:17
we talk about putting a linked list there,
32:20
but you can put,
32:21
you know,
32:22
a dynamic array there,
32:24
you can put a sorted array there
32:26
to make it easier to check
32:28
whether the key is there,
32:29
you can put anything you want there.
32:30
The point of this lecture
32:31
is going to try to show that
32:33
there's a choice of hash function I can make
32:36
that makes sure that these chains are small
32:40
so that it really doesn't matter
32:43
how I store them there,
32:44
right?
32:45
Because I can just,
32:46
I have time,
32:46
if there's a constant number of things stored there,
32:48
I can just look at all of them
32:50
and do whatever I want
32:51
and still get constant time.
32:53
Yeah?
32:53
So,
32:54
does that mean that
32:56
when you have a hash table,
32:58
a multiple slot
32:59
is like a data structure
33:01
and like,
33:02
let's just say like,
33:03
for some reason,
33:04
the number of things
33:05
you can store
33:06
is that most of them
33:07
get like multiple
33:09
and if you have just one,
33:11
is it just a data structure
33:12
that only goes along to me?
33:13
Yeah,
33:13
so what your colleague is saying
33:15
is kind of at initialization,
33:17
what is stored here,
33:19
right?
33:19
Initially,
33:20
it points to an empty data structure,
33:21
right?
33:22
I'm just going to initialize
33:23
all of these things to have,
33:25
now,
33:25
we get some overhead here,
33:27
right?
33:27
We're paying something for this,
33:28
some extra space
33:29
and having pointer
33:30
and another data structure
33:31
at all of these things
33:32
or you could have the semantics
33:34
where if I only have one thing here,
33:36
I'm going to store that thing
33:37
at this location
33:38
but if I have multiple,
33:39
it points to a data structure.
33:41
These are kind of complicated,
33:42
you know,
33:43
implementation details
33:43
but you get the basic idea,
33:45
right?
33:46
If I just have a zero size data structure
33:49
at all of these things,
33:50
I'm still going to have
33:51
a constant factor overhead,
33:54
right?
33:54
It's still going to be
33:55
a linear size data structure
33:56
as long as M is linear in N.
33:59
Does that make sense?
34:01
Okay,
34:02
so how do we pick
34:03
a good hash function?
34:04
I already told you
34:05
that any fixed hash function
34:08
I give you
34:09
is going to experience collisions
34:11
and if U is large,
34:15
right?
34:16
then there's the possibility
34:19
that I,
34:20
for some input,
34:22
all of the things in my set
34:23
go directly to the same
34:25
hashed index value.
34:27
So that ain't great.
34:28
Let's ignore that for a second.
34:30
What's the easiest way
34:31
to get down
34:33
from this large space of keys
34:35
down to a small one?
34:36
What's the easiest thing
34:37
you could do?
34:38
Yeah?
34:38
Modulus.
34:39
Great.
34:40
This is called
34:40
the division method.
34:50
And what it's,
34:52
the function is,
34:53
is essentially
34:53
it's going to take a key
34:54
and it's going to set it
34:56
equal to be
34:57
K
34:58
mod
35:00
M.
35:04
Okay?
35:04
I'm going to take something
35:05
of a large space
35:06
and I'm going to mod it
35:07
so that it kind of just
35:08
wraps around.
35:10
Right?
35:13
Perfectly valid thing to do.
35:15
It satisfies what we're
35:16
doing in a hash table
35:18
and if
35:19
my keys are
35:20
completely uniformly
35:22
distributed
35:23
ran,
35:24
like if
35:24
when I use my hash function
35:26
all of the keys here
35:29
are uniformly distributed
35:31
over this
35:32
larger space
35:34
then actually this isn't
35:35
such a bad thing.
35:37
Right?
35:37
But that's imposing
35:39
some
35:39
kind of distribution
35:41
requirements on the type
35:42
of inputs I'm allowed
35:43
to use with this hash function
35:44
for it to have good
35:46
performance.
35:47
Right?
35:47
But
35:48
this
35:49
plus a little bit of
35:50
extra
35:51
mixing and bit
35:53
manipulation
35:53
is essentially
35:55
what Python does.
35:57
Okay?
35:57
It essentially
35:58
all it does
35:59
is kind of jumbles
36:00
up that key
36:01
for some fixed
36:03
amount of jumbling
36:04
and then mods it
36:06
m
36:07
and sticks it there.
36:09
But there are some
36:10
instances,
36:11
it's hard coded
36:12
in the Python library
36:14
what this hash function is.
36:16
And so there exist
36:17
some
36:18
sequences
36:20
of inserts
36:21
into a hash table
36:22
in Python
36:23
which
36:24
will be really bad
36:25
in terms of performance
36:26
because these
36:27
chain lengths
36:28
or the amount
36:28
number of collisions
36:29
that I'll get
36:30
at a single hash
36:31
is going to be large.
36:34
Right?
36:34
But they do that
36:35
for other reasons.
36:36
They want a deterministic
36:37
hash function.
36:38
They want something
36:39
that I do the program
36:40
again,
36:41
it's going to do
36:42
the same thing
36:42
underneath.
36:43
Right?
36:45
But
36:45
sometimes Python
36:46
gets it wrong.
36:47
But if your data
36:48
that you're storing
36:49
is sufficiently
36:50
uncorrelated
36:51
to the hash function
36:53
that they've chosen
36:53
which usually it is
36:55
this is a pretty
36:56
good performance.
36:57
Okay?
36:58
But this is
36:59
not a
37:00
practical class.
37:03
Well,
37:03
it is a practical class
37:04
but
37:04
one of the things
37:05
that we are
37:06
that's the emphasis
37:08
of this class
37:09
is making sure
37:09
we can prove
37:10
that this is good
37:11
in theory as well.
37:13
Right?
37:13
I don't want to know
37:14
that sometimes
37:15
this will be good.
37:17
I really want to know
37:18
that
37:18
if I choose
37:20
if I make
37:22
this data structure
37:23
and I
37:24
put some inputs
37:25
on it
37:26
I want
37:27
running time
37:28
that is independent
37:29
on what inputs
37:31
I decided to use.
37:32
Independent of
37:33
what keys
37:34
I decided to store.
37:36
Does that make sense?
37:37
Right?
37:38
In some sense
37:38
I want
37:39
but it's impossible
37:41
for me to pick
37:42
a fixed hash function
37:43
that will achieve this.
37:45
Right?
37:45
Because I just told you
37:46
that if u is large
37:47
right?
37:48
This is u.
37:49
If u is large
37:50
then
37:51
there exists inputs
37:53
that map everything
37:54
to one place.
37:56
So I feel
37:57
I'm screwed.
37:58
Right?
37:58
I can't
37:59
there's no way
37:59
to solve this problem.
38:02
That's true
38:03
if I want
38:04
a deterministic hash function.
38:05
Right?
38:06
I want the thing
38:06
to be repeatable
38:07
to do the same thing
38:08
over and over again
38:09
for any set of inputs.
38:12
What can I do instead
38:13
weaken my notion
38:15
of what constant time is
38:17
to do better?
38:18
use a non-deterministic
38:21
Okay.
38:22
Use a non-deterministic
38:23
What does non-deterministic
38:25
mean?
38:26
Right?
38:26
It means don't choose
38:27
a hash function
38:29
up front
38:30
choose one
38:32
randomly later.
38:33
Right?
38:34
So have the user
38:35
they pick
38:36
whatever inputs
38:37
they're going to do
38:38
and then I'm going
38:39
to pick a hash function
38:40
randomly.
38:41
They don't know
38:41
which hash function
38:42
I'm going to pick
38:42
so it's hard for them
38:43
to give me an input
38:45
that's bad.
38:46
Right?
38:47
Okay.
38:48
So I'm going to choose
38:49
a random hash function.
38:51
How do I choose
38:52
a random hash function?
38:52
Can I choose
38:53
a hash function
38:54
from the space
38:55
of all hash functions?
38:57
What is the space
38:58
of all hash functions
38:59
of this form?
39:02
Right?
39:03
For every one
39:04
of these values
39:05
I give a value
39:06
in here.
39:06
Right?
39:07
That would be
39:08
a completely
39:09
like I choose
39:10
for each one
39:11
of these independently
39:12
random number
39:12
between this range.
39:14
How many such
39:14
hash functions
39:15
are there?
39:19
M to the
39:21
this number.
39:22
That's a lot
39:23
of things.
39:24
Right?
39:24
So I can't do that.
39:26
What I can do
39:27
is fix a family
39:28
of hash functions
39:28
where if I choose
39:29
one from randomly
39:31
I get good performance.
39:33
And so the hash function
39:34
I'm going to use
39:35
and we're going to
39:37
spend the rest
39:38
of the time on
39:39
is what I call
39:40
a universal
39:41
hash function
39:42
it satisfies
39:44
what we call
39:45
a universal
39:45
hash property.
39:47
So
39:47
universal
39:49
hash
39:51
function
39:53
and
39:54
this is a little
39:55
bit of a weird
39:56
nomenclature
39:56
because
39:57
I'm defining
39:58
this to you
39:59
as the universal
40:00
hash function
40:01
but actually
40:01
universal is
40:02
a
40:03
descriptor.
40:05
Right?
40:05
There exist
40:06
many universal
40:08
hash functions
40:08
this just happens
40:10
to be an example
40:11
of one of them.
40:12
Okay?
40:13
So the hash function
40:14
or really
40:16
right.
40:20
So we're going to
40:21
so here's
40:24
the hash function
40:25
doesn't look
40:28
actually all
40:29
that different.
40:32
Goodness gracious.
40:33
How many parentheses
40:33
are there?
40:36
Mod
40:37
p
40:38
mod
40:39
m.
40:41
Okay?
40:41
So it's kind of
40:42
doing the same
40:43
thing as what's
40:44
happening up here.
40:45
Right?
40:46
But before
40:48
modding by m
40:49
I'm multiplying
40:51
it by a number
40:52
I'm adding
40:53
a number
40:53
I'm taking it
40:54
mod another number
40:55
and then I'm
40:56
modding by m.
40:57
Okay?
40:57
This is a little
40:58
weird.
40:58
And not only that
40:59
this is still
41:00
a fixed hash function
41:01
I don't want that
41:02
I want to
41:03
generalize this
41:04
to be a family
41:05
of hash functions
41:06
which are
41:11
this
41:12
h
41:12
a
41:13
b
41:14
k
41:15
for some
41:18
random choice
41:19
of
41:20
a
41:21
b
41:21
in this
41:25
larger range.
41:26
All right.
41:30
This is a lot
41:30
of
41:31
notation
41:33
here.
41:34
Essentially what
41:35
this is saying
41:35
is
41:36
I have a
41:37
hash family
41:38
Okay?
41:40
It's parametrized
41:41
by the length
41:42
of my hash function
41:42
and some
41:44
fixed
41:44
large
41:45
random prime
41:46
that's bigger
41:47
than u
41:47
Just I'm going
41:49
to pick some
41:49
large prime
41:50
number
41:50
Okay?
41:52
And that's going
41:52
to be fixed
41:53
when I make
41:54
the hash
41:54
table.
41:56
Okay?
41:56
And then
41:59
when I
42:00
instantiate
42:01
the hash
42:02
table
42:02
I'm going
42:02
to choose
42:03
randomly
42:04
one of
42:04
these
42:04
things
42:05
by choosing
42:06
a random
42:07
a and a
42:08
random
42:08
b from
42:09
this range
42:09
Does that
42:10
make sense?
42:16
This is
42:16
a not
42:17
equal to
42:17
zero
42:18
Right?
42:19
If I had
42:19
zero here
42:20
I kind
42:21
of lose
42:21
the key
42:21
information
42:22
and that's
42:22
no good
42:23
Does this
42:27
make sense?
42:27
So what this
42:28
is doing
42:28
is multiplying
42:29
this key
42:30
by some
42:30
random number
42:31
adding
42:32
some
42:32
random
42:32
number
42:33
modding
42:34
by this
42:35
prime
42:35
and then
42:37
modding
42:37
by the
42:38
size
42:38
of my
42:38
thing
42:38
Okay?
42:39
So it's
42:40
doing a bunch
42:40
of jumbling
42:41
and there's
42:42
some
42:42
randomness
42:42
involved
42:43
here
42:43
I'm
42:43
choosing
42:44
the hash
42:44
function
42:44
by choosing
42:45
an a
42:46
b
42:46
randomly
42:46
from
42:47
this
42:47
thing
42:47
So
42:47
when I
42:48
start up
42:49
my
42:49
program
42:50
Right?
42:52
I'm going
42:53
to instantiate
42:53
this thing
42:54
with some
42:54
random
42:55
a and
42:55
b
42:55
not
42:56
deterministically
42:57
Right?
42:58
The user
42:58
when they're
43:00
using this
43:01
thing
43:01
doesn't know
43:02
which a
43:02
and b
43:03
I picked
43:03
Right?
43:04
So it's
43:04
really hard
43:05
for them
43:05
to give
43:05
me a
43:06
bad
43:06
example
43:06
Right?
43:07
And this
43:08
universal
43:08
hash
43:09
function
43:09
this
43:11
universal
43:11
hash
43:12
family
43:12
shall we
43:13
say
43:13
really
43:13
this is
43:14
a family
43:14
of functions
43:15
and I'm
43:15
choosing
43:15
one
43:16
randomly
43:16
within
43:17
that
43:17
family
43:17
is
43:20
universal
43:20
and
43:21
universality
43:22
says
43:25
that
43:25
what is
43:26
the
43:27
property
43:27
of
43:28
universality
43:28
It means
43:30
that the
43:31
probability
43:31
by choosing
43:33
a hash
43:34
function
43:34
from this
43:35
hash
43:35
family
43:35
that
43:37
a certain
43:40
key
43:41
collides
43:43
with another
43:44
key
43:44
is less
43:47
than or
43:47
equal to
43:48
one over
43:49
m
43:49
for all
43:50
any
43:52
different
43:54
two keys
43:55
in my
43:57
universe
43:57
Does that
44:02
make sense?
44:02
So
44:03
basically this
44:06
thing has
44:06
the property
44:07
that if I
44:07
randomly
44:08
pick
44:09
or if I
44:09
for any
44:10
two keys
44:11
that I
44:13
pick
44:13
in my
44:14
universe
44:14
space
44:15
if I
44:17
randomly
44:17
choose a
44:18
hash
44:18
function
44:18
the
44:19
probability
44:19
that these
44:20
things
44:21
collide
44:21
is less
44:22
than
44:22
one
44:23
over
44:23
m
44:23
Why is
44:24
that
44:24
good?
44:24
This is
44:25
in some
44:25
sense
44:26
a measure
44:26
of how
44:27
well
44:27
distributed
44:28
these
44:29
things
44:29
are
44:29
I
44:30
want
44:30
these
44:30
things
44:31
to
44:31
collide
44:31
with
44:32
one
44:33
over
44:33
m
44:33
probability
44:34
so that
44:36
these
44:36
things
44:37
don't
44:37
collide
44:38
very
44:38
likely
44:38
it's not
44:39
very likely
44:40
for these
44:40
things
44:40
to collide
44:41
Does that
44:41
make sense?
44:42
So we
44:43
won't prove
44:44
that this
44:44
hash
44:45
family
44:45
satisfies
44:46
this
44:47
universality
44:47
property
44:48
you'll do
44:48
that in
44:48
046
44:49
but we
44:50
can use
44:51
this
44:51
result
44:52
to show
44:53
that
44:54
if we
44:54
use
44:55
this
44:56
universal
44:56
hash
44:57
family
44:57
that
44:59
the
44:59
length
44:59
of our
45:00
chains
45:00
is
45:02
expected
45:03
to be
45:03
constant
45:04
length
45:05
So we're
45:06
going to
45:06
use this
45:07
property
45:07
to prove
45:08
that
45:08
How do
45:10
we prove
45:10
that?
45:11
We're going
45:11
to do
45:11
a little
45:12
probability
45:12
So how
45:15
are we
45:15
going to
45:16
prove
45:16
that?
45:16
I'm
45:16
going to
45:17
define
45:17
a
45:18
random
45:18
variable
45:19
an
45:19
indicator
45:19
random
45:20
variable
45:20
Does anyone
45:21
remember
45:21
what an
45:21
indicator
45:22
random
45:22
variable
45:22
is?
45:23
Yeah
45:23
It's a
45:25
variable
45:25
that with
45:26
some
45:27
amount
45:27
of
45:27
probability
45:28
is 1
45:28
and 1
45:29
minus
45:29
that
45:30
probability
45:30
is 0
45:30
So I'm
45:33
going to
45:33
define
45:34
this
45:34
indicator
45:34
random
45:35
variable
45:35
xij
45:37
is a
45:40
random
45:40
variable
45:40
over
45:41
my
45:42
choice
45:42
of
45:47
a
45:47
hash
45:48
function
45:48
in
45:48
hash
45:49
family
45:49
and what
45:50
does this
45:51
mean?
45:51
It means
45:52
xij
45:53
equals
45:54
1
45:55
if
45:56
hash
45:58
ki
45:59
equals
46:02
hkj
46:04
these things
46:05
collide
46:05
and 0
46:09
otherwise
46:09
So I'm
46:14
choosing
46:15
randomly
46:15
over this
46:16
hash
46:16
family
46:16
if
46:18
for
46:19
two
46:20
keys
46:21
i and j
46:22
key i
46:22
and key j
46:23
if these
46:24
things collide
46:25
that's going to be 1
46:27
if they don't
46:28
then it's 0
46:29
okay
46:29
then
46:30
how can we write
46:31
a formula
46:32
for the length
46:33
of a chain
46:35
in this
46:36
model
46:36
right
46:36
so
46:37
the size
46:38
of a chain
46:39
right
46:40
or
46:43
let's put it
46:44
here
46:44
the size
46:47
of the
46:48
chain
46:49
at
46:52
i
46:53
right
46:55
at i
46:55
in my
46:56
hash table
46:57
is going to
46:58
equal
46:59
I'm going to
47:00
call that
47:01
the random
47:01
variable
47:02
xi
47:02
that's going
47:03
to equal
47:03
the sum
47:04
over
47:05
j
47:05
equals 0
47:06
to
47:07
what is it
47:10
over
47:10
I think
47:11
u minus 1
47:12
of
47:14
summation
47:16
or sorry
47:17
of
47:18
x
47:19
i
47:19
j
47:20
right
47:20
so basically
47:21
if I fix
47:23
this
47:24
this location
47:25
i
47:26
right
47:27
if I fix
47:32
this location
47:32
i
47:32
this is
47:33
where
47:34
this
47:34
key
47:34
goes
47:35
right
47:36
so I'm
47:38
looking at
47:38
sorry
47:38
this is
47:39
the size
47:39
of
47:39
chain
47:40
at
47:40
h
47:42
of
47:42
ki
47:43
sorry
47:44
so I look
47:45
at wherever
47:46
ki
47:47
goes
47:47
is hashed
47:48
right
47:48
and I see
47:49
how many
47:50
things collide
47:50
with it
47:51
right
47:51
I'm just
47:52
summing over
47:52
all of
47:53
these things
47:53
right
47:54
because this
47:55
is one
47:55
if there's
47:56
a collision
47:57
and zero
47:57
if there's
47:58
not
47:58
does that
47:58
make sense
47:59
so this
48:00
is the
48:01
size of
48:01
the chain
48:01
at the
48:02
index
48:03
location
48:03
mapped to
48:04
by
48:05
ki
48:06
okay
48:08
so here's
48:10
where your
48:10
probability
48:11
comes in
48:11
what's the
48:13
expected value
48:14
of this
48:14
chain length
48:15
over my
48:16
random choice
48:17
okay
48:17
expected value
48:19
over choosing
48:20
a hash
48:21
function from
48:22
this universal
48:23
hash family
48:23
of this
48:25
chain length
48:25
well that's
48:28
just
48:29
I can
48:29
put in my
48:30
definition
48:30
here
48:30
that's the
48:31
expected value
48:32
of the
48:34
summation
48:34
over j
48:36
of
48:37
x
48:38
i
48:39
j
48:39
what do I
48:46
know
48:46
about
48:46
expectations
48:48
and summations
48:49
if these
48:53
variables are
48:54
independent
48:55
from each
48:55
other
48:55
say
48:59
say what
48:59
linearity
49:03
of expectation
49:04
right
49:04
basically the
49:06
expectation of the
49:07
sum of these
49:07
independent random
49:08
variables is the
49:09
same as the
49:09
summation of
49:10
their
49:10
expectations
49:11
right
49:12
so this is
49:12
equal to the
49:13
summation
49:14
over j
49:15
of the
49:16
expectations
49:17
of these
49:17
individual
49:18
ones
49:18
okay
49:20
one of
49:27
these
49:27
j's
49:29
is the
49:30
same as
49:30
i
49:30
right
49:31
j
49:32
loops over
49:33
all of the
49:34
things from
49:34
0 to
49:35
u
49:35
minus 1
49:36
right
49:37
one of
49:37
them is
49:38
i
49:38
right
49:38
so when
49:39
hi
49:41
is
49:42
h
49:43
j
49:43
what is
49:45
what is the
49:46
expected value
49:47
that they
49:47
collide
49:48
one
49:49
right
49:50
so I'm
49:51
going to
49:51
refactor this
49:52
as being
49:53
this
49:54
where j
49:55
does not
49:55
equal i
49:56
plus
49:57
one
49:58
are people
49:59
okay with
50:00
that
50:00
because
50:01
if i
50:02
equals
50:03
if
50:04
j
50:05
and i
50:05
are equal
50:06
they definitely
50:07
collide
50:07
right
50:07
they're the
50:08
same
50:08
key
50:08
right
50:09
so I'm
50:10
expected to
50:11
have one
50:11
guy there
50:12
which was
50:13
the original
50:14
key
50:14
xi
50:15
right
50:16
but otherwise
50:17
we can use
50:18
this universal
50:19
property
50:20
right
50:21
that says
50:23
if they're
50:24
not equal
50:25
and they
50:26
collide
50:27
which is
50:27
exactly this
50:28
case
50:28
right
50:29
the probability
50:30
that that
50:31
happens
50:31
is 1
50:33
over m
50:33
right
50:34
and since
50:35
it's
50:36
an indicator
50:37
random variable
50:38
the expectation
50:38
is
50:39
their outcomes
50:41
times their
50:41
probability
50:42
probabilities
50:42
right
50:42
so 1
50:43
times that
50:43
probability
50:44
plus 0
50:45
times 1
50:47
minus that
50:47
probability
50:48
right
50:48
which is
50:48
just
50:48
1
50:49
over m
50:49
right
50:50
so now
50:51
we get
50:52
the summation
50:55
of 1
50:56
over m
50:57
for
50:58
j
50:58
not equal
50:59
to i
50:59
plus 1
51:02
n
51:07
oh
51:08
and this
51:08
sorry
51:09
i did this
51:11
wrong
51:11
this isn't
51:12
u
51:12
this is n
51:13
we're storing
51:14
n keys
51:15
right
51:16
okay
51:17
so now
51:18
i'm looping
51:19
over j
51:20
this over all
51:21
of those
51:21
things
51:21
how many
51:22
things are
51:22
there
51:23
n minus
51:23
1 things
51:24
right
51:25
so this
51:26
should
51:26
equal
51:27
1
51:27
plus
51:28
n
51:28
minus
51:29
1
51:30
over m
51:31
okay
51:32
so that's
51:33
what
51:33
universality
51:34
gives us
51:35
so as long
51:36
as we choose
51:37
m
51:37
to be like
51:40
larger than n
51:41
or at least
51:42
linear in n
51:43
then we're
51:44
expected
51:45
to have our
51:46
chain lengths
51:47
be constant
51:48
right
51:49
because this
51:50
thing
51:50
becomes a
51:52
constant
51:52
if m
51:53
is at least
51:54
order n
51:55
does that make
51:55
sense
51:56
okay
51:58
the last thing
51:59
i'm going to leave you
52:00
with is how do we
52:00
make this thing
52:01
dynamic
52:01
if we're
52:02
growing the
52:04
number of things
52:05
we're storing
52:05
in this thing
52:06
it's possible
52:07
that as we
52:08
grow n
52:09
for a fixed
52:09
m
52:10
this thing
52:11
will stop
52:12
being
52:12
m
52:13
will stop
52:13
being
52:14
linear in n
52:14
right
52:15
well then all we have to do
52:17
is if we get
52:18
too far
52:18
we
52:20
rebuild the entire thing
52:22
the entire hash table
52:23
with the new m
52:24
right
52:24
just like we did
52:25
with the
52:25
dynamic array
52:26
and
52:27
you can prove
52:28
we're not going to do that here
52:30
but you can prove
52:31
that
52:32
you won't do that
52:33
operation too often
52:34
if you're
52:35
resizing in the right way
52:37
and so you just
52:38
rebuild completely
52:39
after
52:40
a certain number of operations
52:42
okay
52:42
so that's hashing
52:43
next week
52:44
we're going to be talking about
52:45
doing a faster sort
52:47
blast