- [Instructor] Now we're gonna continue
our study of hash tables
and look at another collision resolution policy
called linear probing.
Earlier, we saw our first collision resolution policy,
separate chaining.
Now linear probing is another approach
to resolving hash collisions.
Unlike separate chaining,
however, we only allow a single object
at a given index in our hash table.
So how does it work?
Well, the idea behind linear probing is simple.
If a collision occurs,
we probe our hash table taking one step at a time
until we find an empty spot
for the object we wish to insert.
We call the step size the stride
and it's typically set to one,
but basically linear probing is just what you might think
given its name.
On collisions,
we probe in a linear step-wise fashion
until we find a home for our new object.
Let's look at a simple example.
Here's an example similar to the one we saw earlier.
Again, we have a hash table of size seven.
But in this case, unlike separate chaining,
each element in the hash table can hold only one object.
As before,
we're gonna use the simplest possible hash function
for demonstration purposes,
f(x) equals x mod seven.
So let's insert 12,
12 mod seven equals five.
So 12 goes there.
So far so good.
Now we'll insert nine,
nine mod seven is two.
So nine is gonna go here.
But what happens when we want to insert 44?
44 mod seven is also two.
So we have a collision.
Where does 44 go?
Well, we start probing at two.
We found that there's a collision.
So we take one step to the right, to three,
and we insert 44 in the first open position we find.
That's linear probing.
Let's continue.
If we want to insert 30,
30 mod seven is also two.
So we have a collision again.
What do we do?
Well, we start our probe sequence at two,
and we continue until we find an empty position
in which to insert our object.
So 30 goes at index four.
Now we want to insert two.
Again, two mod seven is two,
another collision.
So what do we do?
We probe until we find an empty spot.
Now two goes at index six.
Now we want to insert 16.
Again, we have a collision
because 16 mod seven is two.
Now what do we do?
We've run out of positions in our index.
Do you think?
No, I think we wrap around.
So watch what happens.
We get to the end of the vector
and we wrap around to the beginning.
So 16 is inserted at position zero.
Now this sequence of steps that we take
is called a probe sequence.
So in the case of nine,
our probe sequence was just two.
In the case of 44, we had to probe two and three.
For 30, we had to probe two, three, and four.
For two, we had to probe two, three, four, five, and six.
And for 16, we probed all the way back around to zero again.
So now what happens when we want to find an element?
Well, we just follow the same probe sequence
until we find our target
or we encounter an empty position in our hash table,
at which point we'll know that the target
doesn't exist in the hash table.
So for example, to find 30,
we calculate the hash in two.
We start at index two,
we find that it's not there,
and so we probe until we find 30.
Now 72 is not in this hash table.
So what happens then?
Well, we calculate the hash,
again, we get two,
we start at two,
and we continue our linear probe
until we arrive at an empty position.
Once we hit that empty position,
then we know that 72 is not in the hash table.
So that's how find works.
Now what about removing?
Well, let's say we want to remove 16.
Calculate that hash,
we start at two,
we probe in a linear fashion until we get to 16,
we match that value and then we delete it.
So far so good.
Now what happens if we delete 30?
Well, we start at two,
we take two steps,
we find 30 and we delete it.
But now we got a problem.
Can you see what it is?
What happens if we try to find two now?
If we try to find two,
we're gonna start at index two
because that's the value returned by our hash function.
And then we probe twice and we arrive at an empty position.
And so now we think two's not in our table.
But it is in fact in our table at index six here.
And by deleting 30,
we broke our probe sequence,
and that's not good.
So what we do in cases of deleting
is rather than just remove the item
and return the position to an empty state,
we have another state in our table
that indicates an item has been deleted or removed.
And in this case, it preserves our probe sequence.
So now when we want to find two,
we don't stop at four thinking we haven't found it,
we can continue on our way until we find two.
So you'll see more about how this works
when we implement this in C++.
But be aware that we need to ensure
that our probe sequence isn't broken.
Linear probing is prone to a phenomenon
called primary clustering.
And that's because every time there's a hash collision,
we just look in the next position,
and then the next, and then the next.
And we tend to fill up blocks of contiguous positions
in our hash table.
That's primary clustering.
The downside, when we have primary clustering,
is we have to keep probing again and again
and again and again until we find an empty spot.
So that's the problem that we'll address a little later.
But you should be aware that it occurs with linear probing.
So let's compare linear probing with separate chaining.
In the case of linear probing, on collisions, we probe.
With separate chaining,
on collisions, we just extend the chain.
We add one more to the bucket.
In the case of linear probing,
there's a fixed upper limit
on the number of objects we can insert.
That's the size of our hash table.
We don't have that restriction
in the case of separate chaining,
because we can extend the chains.
Linear probing again is prone to primary clustering
but with separate chaining,
clustering does not occur
since we're not doing that probing.
In summary,
with a linear probing scheme,
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
where we can put our object.
And unlike separate chaining
where we can extend our chains,
linear probing has a fixed upper limit
on the number of objects
we can insert into our hash table.
So before we finish,
I'm gonna leave you with a couple of questions.
Because we have this upper limit,
the size of our hash table,
what can we do when we run out of space in our hash table?
We'll see about that shortly.
And then another question.
If we set our stride to some value greater than one,
say two or three,
why is it a good idea to have a hash table size
that's a prime number?
Give that some thought, too.
I'll see you in the next video.