- [Instructor] We continue our study of hash tables
with the topic of rehashing.
Now I left you with a couple of questions
from our previous video.
One was what can we do when we run out of space
in our hash table?
And the other if we set our stride
to some value greater than one,
why is it a good idea to have a hash table size
that's a prime number?
Now let's pursue the second question and take a brief detour
before we get into rehashing.
Here we have two hash tables, one of size 11,
which is prime.
That's the one on the top.
And the one below is of size 12.
12 of course, is not prime.
And let's say we're doing linear probing
with a stride of two.
And we have some key value that returns a index of zero
in both cases.
And our first step in linear probing,
we'll take a stride of length two,
and wind up at index two.
At the next step, we'll wind up at index four,
index six, index eight, index 10.
Now I'll bet you can see what's gonna happen next here.
What's going to happen,
is that here in the table that's size 12,
we're gonna take a stride of two, one, two.
It's going to land us back at zero,
and we're just gonna continue
to cycle through these six indices.
We will never ever hit one three, five, seven, nine, or 11.
So here we go in the table that's prime.
We take a stride of two.
We wind up at one,
three, five, seven, nine.
And you see when we have a prime number,
we hit every single value with a stride of two.
Here, because two is a factor of 12,
we kept returning to the same values again
and again and again.
This is one of the reasons why prime numbers
are good sizes for hash tables.
The idea is that if the stride
and the table size are not coprime,
coprime means that two numbers
don't share any common factors other than one,
then you can't probe the entire table
from any given starting point.
That's one reason.
That's it for the detour.
Now let's go on to rehashing.
Now, earlier we had asked the question
what can we do when we run out of space in our hash table?
But it turns out that we get ourselves into trouble
before we exhaust all of the free space in our hash table.
And that's because the more entries we have
in our hash table, the more likely it is
that we have a collision on our next insert.
And the other problem is the more entries we have
in our table, the longer a typical probe sequence
becomes when we're inserting, finding, and removing entries.
And as a result, performance degrades.
So rehashing comes to the rescue.
What do we do?
We set a limit, some maximum value for our load factor
which is also called the fill percentage.
And then on inserts, we check the load factor.
And if it exceeds the limit,
then we create a new, bigger table.
And we insert all the objects
from the old table into the new table.
And then we delete the old table.
And since the table size changes, the index calculated
from our hash function will change for each item,
hence the term rehashing.
All objects will get a new hash value
when we insert them into the new table.
But then the question becomes
how big should we make our new table?
And as a rule of thumb,
we take the old table size, we double it.
And then we find the next prime number
and use this as a size for our new table.
So for example, if our old size was 11,
we'd take two to get 22.
And the next prime is 23.
If we had a table of size 17,
and we hit our threshold and we needed to rehash,
we would multiply that by two to get 34.
The next prime is 37.
So we'd create a new table of size 37
and rehash all of our elements into that new table.
If our old table were size 21,
we double it to get 42.
43 is the next prime.
If we had a table of 103,
we'd double it to get 206, and the next prime would be 211.
So our resulting table would be of size 211.
Let's look at an example.
This should look pretty familiar to you by now.
We have a hash table of size seven.
We're using, again for demonstration purposes,
the simplest possible hash function
which is F of X equals X mod seven.
That's the size of our table.
And we've set a maximum load factor
or fill percentage of 50%.
Okay? And now let's perform some inserts.
We insert 19.
That goes to position five.
The load factor becomes 14.2, that's 1/7.
Okay. We insert eight.
That goes to position one.
Now our load factor becomes 28.6.
We insert a 11.
That goes to index four.
And our load factor becomes 42.9.
And you can see that on the next insert,
we're going to exceed threshold.
So there we go.
We're inserting 17.
That goes at index three.
And it's time to rehash because our load factor
now exceeds the threshold.
57.1 is greater than 50.
Okay. So what do we do?
Well, we have to calculate the size of that table.
So our old table size is seven.
We multiply that by two, we get 14.
And the next prime is 17.
Okay. So now we create a table of size 17,
our hash function,
our minimal hash function changes now.
It's now F of X equals X mod 17
because we have 17 elements in our hash table.
And right, now our load is zero.
But what we're going to do is we're gonna take these items
one at a time and rehash them and insert them
into our new hash table.
So let's do that.
We take eight.
That goes here.
Load factor becomes 5.8%.
Next one's gonna be 17.
You takes 17.
That's gonna land at index zero.
Load factor becomes 11.7%.
We insert 11.
That goes here.
Load factor becomes 17.6%.
And we add 19.
And that goes here.
And our load factor becomes 23.5.
And then when we're done, we just delete that old table.
And now we have a new table that's been rehashed
that now has a load factor well below our threshold.
And we have plenty of room to grow.
So rehashing, the way it works
is that we rehash as needed on inserts
to keep the load factor below a certain threshold.
Typically, we use load factors
of between 50% and 75% as thresholds.
And if we use 50% as our threshold say,
this means that at least half of our hash table
will be empty at any given time.
Now, why is this good?
Well, it solves the problems that we stated
at the very beginning.
It'll reduce the frequency of collisions,
and it'll result in shorter probing sequences.
And so the performance of our hash table will be faster.
Now, what do we need to implement rehashing?
We need a function which when given an integer,
calculates the next prime number.
We need a method to perform rehashing.
And we need to modify the insert function
to check the load factor and to call our rehashing method
as needed whenever we exceed that threshold.
And that's what we'll see in the next video
when we implement a hash table
with linear probing and rehashing.
That's all for now.