- [Instructor] Okay. Now we've seen separate chaining.
We've seen two collision resolution policies,
linear probing, and quadratic probing.
Now we're gonna look at one more collision
resolution policy called double hashing.
And double hashing is another approach
to resolving hash collisions.
We've seen that linear probing
is prone to primary clustering.
And while quadratic probing
is designed to eliminate primary clustering,
we've seen that it's prone
to what's called secondary clustering,
where the clusters are distributed
throughout the table, but they exist nonetheless.
Double hashing is designed to address
both of these problems.
So let's go back to our comparison of linear probing
and quadratic probing.
As you recall with linear probing,
we have a fixed stride.
Typically one.
And if we have a collision,
we step from position to position
until we find an open place to make our insert.
In the case of quadratic probing, we vary our stride
with each step using the square of the number of steps.
So the first step is one.
The second step is four.
The third step is nine.
The fourth step is 16 and so on.
Now, in the case of double hashing, we have a fixed stride
for any given key, but the stride is calculated separately
for each key using a second independent hash function.
So two different keys that yield the same index
is calculated from the primary hash function,
should have a different stride
as calculated from the secondary hash function.
And that's how we prevent clustering.
Now, what should the secondary hash function look like?
Well, it clearly has to be different
from the hash function used to get the index.
And ideally, the output of the primary hash function
and the secondary hash function
should be what's called pairwise independent,
meaning that they're uncorrelated.
The secondary hash function,
unlike the primary hash function should return values
in the range of one to table size minus one.
Those would be valid step sizes.
Obviously, we don't want it to return zero
because then it wouldn't probe.
So that's why we have this slightly different range.
And again, as with our primary hash function,
the secondary hash function should distribute values
as uniformly as possible within that range.
So for example, we could calculate some number, h,
and we could use Horner's method or some other method.
And we would return p minus h mod p,
where p is some prime number less than the table size.
And that's a minimal example
of a secondary hash function.
The primary hash function gives us the starting point
for our probe sequence.
And the secondary hash function gives us the stride
if we need to probe.
So here we have a table showing our minimal
primary hash function.
This is f of x equals x mod 17.
And we have a secondary hash function, g of x
which is a smaller prime number, 13 minus x mod 13.
And we see here that for each different key,
I have shown here in the table, the primary hash function
and the secondary hash function yield different values.
They're are pairwise independent.
Okay. And that's an ideal.
Now let's look at what happens when we have a collision.
Now here, I have all these keys, zero, 17, 34, 51, 68.
They're all multiples of 17.
So when we apply that to the primary hash function,
we're always gonna get zero.
So each one of these keys is going to have a hash collision
in its primary hash function.
But look at what's happening
in the case of the secondary hash function.
We get different values from our secondary hash function.
Zero mod 13 is zero.
And so our secondary hash gives us a stride of 13
when the key is zero.
When the key is 17, we get a stride of nine.
17 mod 13 is four.
And 13 minus four is nine.
When the key is 34, we got a stride of five
because 34 mod 13 is eight,
and 13 minus eight is five, and so on.
So you see, even though we have collisions
in the primary key,
we're getting different values for the secondary key.
So you see,
even when we have a collision on the insert index
calculated from the primary hash function,
we get a different stride from the secondary hash function.
And so these probe sequences will all be different.
Let's take a look at an example.
Here again, we have our primary hash function,
f of x equals x mod 17,
and our secondary hash function,
g of x equals 13 minus x mod 13.
And it's important that this prime number
be less than the table size.
Okay?
So let's make our first insert.
Let's say we want to insert five.
F of x which is this function here is gonna give us five,
but g of x is going to give us eight.
Now we don't have anything in our table,
so we're not gonna have a collision.
We're just gonna insert five at the specified index.
So there we have five.
Now on the next insert, let's say we want to insert 56.
56 is gonna give us the same primary hash result.
F of x equals five.
Now g of x,
the secondary hash function gives us a stride of nine.
So when we insert, we're going to take a stride of nine,
one, two, three, four,
five, six, seven, eight, nine.
And 56 is gonna go here.
Now let's insert 39.
Again, 39, I've set it up this way,
is gonna cause a collision
because f of x 39 mod 17 is five.
But g of x gives us a different value
than we got before, before it was nine.
Now it's 13.
So our probe is gonna be one, two,
three, four, five, six, seven,
eight, nine, 10, 11, 12.
'Cause we wrap around 13.
And so 39 is gonna go here.
Let's do one more.
Here's 22.
Again, f of x gives us five.
That's our primary hash function.
22 mod 17 is five.
But g of x gives us four.
Because 13 minus 22 mod 13 is four.
And so our stride is going to be four,
one, two, three, four.
And 22 goes there.
So what just happened?
Well, we had these keys.
This was the result of our primary hash function, all five.
And then our secondary hash function gave us
these values eight, nine, 13, four.
And so each of these inserts
follows a different probe sequence.
That's the idea behind double hashing.
Now what's the probability of hash collisions
having the same stride?
In order for hash collisions to have the same stride
for their probe sequence, both the primary hash function
and the secondary hash function
would have to return the same value for two different keys.
Now in an ideal world with perfect hash functions,
the outputs would be distributed uniformly,
just as if the hash functions were random.
And we'd have something like a one over n
for the likelihood of any given value
from our primary hash function,
times one over n,
the likelihood of any value
from our secondary hash function.
And then the probability of both
of those yielding the same values would be one
over n squared.
Now, of course, this is a lower limit on the probability
that hash collisions have the same stride
because in the real world,
our hash functions won't be perfect.
That is, they won't distribute the values
with perfect uniformity, but we want them to be close.
So in the real world, this probability will be greater
than one over n squared, but hopefully not too much greater.
So if we have a hash table
of around a thousand elements, the probability
of hash collisions having the same probe sequence
would be around one in a million.
And that's not bad.
So again, to compare our CRPs,
our collision resolution policies,
we see that all of these probing approaches probe
on a collision.
Linear probing, quadratic, probing,
and double hashing, whereas separate chaining,
we extend the chain.
Again, all three of these probing approaches
have a fixed upper limit on the number
of objects that we can insert into our hash table.
Whereas again, primary chaining is limited only
by the memory and system constraints.
Linear probing has a fixed stride, typically one.
And that's always the same stride
whenever we have a hash collision.
Quadratic probing varies the stride on each step.
We take the square of the step to get our stride
for any given step.
And double hashing has a fixed stride,
but it's calculated by a second hash.
Linear probing is prone to primary clustering.
Quadratic probing is prone to secondary clustering.
Double hashing reduces clustering substantially.
And of course, in the case of separate chaining,
clustering does not occur.
So in summary, with double hashing,
like other open addressing techniques we've seen,
we only allow a single object at a given index.
When we have a hash collision,
we probe our hash table one step at a time,
but with a stride that's been calculated
by a second independent hash function.
And because we use a second hash function,
the stride depends on the data
and this makes it very unlikely
that two insertions with the same hash value
for the first index would follow the same probe sequence.
Again, they'd have to have in effect,
two concurrent hash collisions.
And finally, double hashing, as you might expect,
has a fixed limit on the number
of objects that we can insert into our hash table.
So as with linear probing,
and quadratic probing, rehashing is gonna be a thing
when we're doing double hashing as well.
So now I'll leave you with some questions.
We have two basic strategies
for hash collision, chaining and probing.
Where probing methods are linear probing,
quadratic probing, and double hashing.
Which do you think uses more memory?
Which of these do you think is faster?
And how would you calculate their complexities?
Give these questions some thought
and we'll see you in a later video.
That's all for now.
Thanks.