- [Instructor] Okay, so we're continuing with hash tables.
And now we're gonna look at what's called quadratic probing.
I remember the first time I heard about quadratic probing,
it sounded so exotic.
So scary.
What is quadratic probing?
Oh my gosh. Quadratic probing.
Anyhow, it's no big deal.
So, we'll see what it is
and it's actually very easy to implement.
So when it comes time for us to modify our hash table
to implement quadratic probing,
we'll only have to change a couple of lines of code.
So far we've seen two collision resolution policies;
separate chaining and linear probing.
And quadratic probing is just another approach
to resolving hash collisions.
But of course, with any approach,
there's a problem to be solved.
And what is the problem?
Well, we've seen that linear probing is prone
to what's called primary clustering
and quadratic probing is designed
to eliminate primary cluster.
Let's remind ourselves what primary clustering is.
You'll recall that in the case of linear probing,
we just probe from one element to the next,
with a fixed stride.
When we hit occupied positions in our hash table.
Say we insert an object at position zero,
the hash function returns zero
and it tells us to put it there, so we do.
Now the next time our hash function returns zero,
we're gonna insert at one.
That's our linear probing.
But now what happens is that the next time
our hash function returns a zero or a one,
we're gonna insert at two.
Okay.
And now, if our hash function returns zero one or two,
we're gonna wind up at three.
Any of those values will get us to three,
you can see how this primary cluster builds.
Now, any hash value, zero, one,
two, or three, is gonna land us at four.
Now you can enter the probe sequence at any point.
If we insert now with any value, one through five,
we'll wind up at six, and therein lies the problem.
If we hit any one of these elements
within our primary cluster,
we're gonna have to enter that same chain
and we're gonna wind up at the next empty position.
Okay, and we wanna avoid that.
So, whereas with linear probing,
we have this fixed stride of one typically,
wherever we just step from position to position.
With quadratic probing, our stride varies at each step.
So what's goin' on here?
We've got a little step and then a little bigger step
and then a little bigger step.
And it's very simple.
We just keep track of the number of steps that we're taking.
So on the first, we take one squared that gets us one.
So our stride is one.
On our second step, we take two squared,
which is four and our stride is four.
One, two, three, four.
On our third step, we take three squared, that gets us nine.
So our stride is nine.
One, two, three, four, five,
six, seven, eight, nine.
Our next one would be 16.
You know, what would happen?
We'd wrap around and it turns out
we'd wind up at a position 13,
but that's the idea behind quadratic probing.
So it distributes the probe sequence
throughout the hash table.
So again, to go back to our primary clustering,
this is our primary cluster with linear probing.
And again, we can enter at any point
and we're gonna pick up somewhere along this chain
and we're gonna wind up at the next open position.
In the case of linear probing and primary clustering,
we follow the same probe sequence or some portion thereof,
no matter where we enter the primary cluster.
And in the case of quadratic probing,
a secondary cluster, which is these yellow elements
is actually distributed throughout the table.
And we only follow that same probe sequence
if we start at the same initial point.
So if we were to get a hash value of five,
we wouldn't follow this same probing sequence.
We do six, and then one, two, three, four,
would get us to 10.
And then one, two, three, four, five,
six, seven, eight, nine, would get us to two.
So you see, it avoids the problem of this primary cluster.
Let's take a look at a CRPs.
CRP, what does that stand for?
That's collision resolution policy.
I had to abbreviate it
'cause otherwise it wasn't gonna fit on the slide.
So we have linear probing and quadratic probing,
in both cases, we probe when we hit a collision.
There's a fixed upper limit on the number
of objects that we can insert.
That's the size of our hash table,
which is different from separate chaining as you recall,
which is only limited by
the memory or the system constraints.
Linear probing has a fixed stride, typically one,
and with quadratic probing, the stride changes on each step.
It's the counter for the step, squared.
And whereas linear probing is prone to primary clustering,
secondary clustering happens with quadratic probing,
but again, those clusters are distributed
throughout the tables, so they become less of a problem.
In summary, like linear probing
and unlike separate chaining,
we only allow a single object at a given index.
Upon hash collisions, we probe our hash table,
one step at a time until we find an empty position,
but our stride changes on each step.
And like linear probing and unlike separate chaining,
quadratic probing also has a fixed limit
on the number of objects that we can insert,
so rehashing is gonna be a thing
when we're doing quadratic probing as well.
We'll implement this in C plus plus in project five,
but I think you'll see that this is a pretty simple concept
and it does a good job of
breaking up those primary clusters.
And in general, keeps the probe sequences shorter
than if we were using a linear probing.
And that's the problem it's intended the solve.
Later on, we'll look at another
collision resolution policy called double hashing,
which is designed to avoid the secondary cluster.
But we'll see that in another video, that's all for now.