- Hey, welcome to week 10 of CS124
online data structures and algorithms.
This week, we'll pick up where we left off
with hash tables, and continue our studies
with what's called linear probing, rehashing,
quadratic probing, and double hashing.
Now in contrast to separate chaining,
which we saw last week,
the so-called open addressing schemes
take a different approach to resolving collisions
and that is probing.
So what happens with these collision resolution policies
is that when a collision occurs,
we probe our table to find an empty place
to put the object we wish to insert.
And if we do this in an orderly fashion,
then we can find and remove objects
in our hash table as well, using the same probing approach.
Now, how we go about probing will vary,
and we'll look at three policies that use probing.
Linear probing, quadratic probing, and double hashing.
They're all different, but they all use probing.
Now, unlike separate chaining,
where we handle hash collisions by extending the chains
that is putting multiple objects in the same bucket,
we don't do this with our open addressing
or probing methods.
In these cases,
there can be only one object at a given location.
And so that means we have capacity to deal with.
So accordingly, we're going to have some method
of growing our table in order to
accommodate new objects when we exceed capacity
or reach a certain threshold as the case may be.
This is what rehashing is all about.
We create a new larger table
and then insert or rehash our objects into the new table.
We'll implement linear probing
and rehashing in C plus plus,
but I'm going to leave the implementation
of quadratic probing and double hashing up to you.
This will be part of what you'll be doing
in project number five.
So let's get down to this week's business
with the video lectures and the demonstrations.
We'll begin with linear probing and as always,
these videos and supplemental materials
are posted here on Blackboard.
And then there's some assigned reading in the textbook.
But most of that reading you should have covered last week,
the chapter on hash tables.
At the end of the week, we'll have another quiz
which will cover this week's material,
and a little bit from last week.
So that's all for now,
and I'll see you on our yellow dig discussion board.
Have fun, good luck.