- [Instructor] Okay, now we've got a two for here.
We're gonna make two changes
to our hash table to implement linear probing and rehashing.
And we've seen in previous videos, what these are
as we did with separate training
we're gonna take the hash table class.
We first created
and modify that to suit our new requirements.
So let's open that file.
Okay. And we have our hash table here
and we're gonna add a couple of methods
and then we're gonna modify, insert, find and remove.
So let's put in placeholders
we're gonna need int next Prime
int N.
And that's gonna take some integer
and return the next prime.
Why do we need that?
As you recall, we want our table sizes to be prime.
And when we rehash, what we're gonna do is
we're gonna take the existing table size, double it
and then find the next prime.
Therefore, we're gonna need this method.
That's gonna calculate the next prime on any given N.
So we can use that as our new table size.
And we're also gonna need another function called Rehash.
That'll be a void function.
Sorry.
And what rehash is going to do is it's going to
fetch the existing table size, double it, call next prime
get the new table size, create a new table
rehash all the elements of the old table into the new table
and then delete the old table.
That's what rehash is gonna do.
So let's just put a note to this effect.
Find
next
prime
for use as
new table size.
This is
rehash
when
load
factor
exceeds threshold.
And this will be called by insert.
Okay.
So far so good
As you recall, when we're using linear probing
and we remove an item, we want to mark the item
as deleted or removed, but not actually empty it out.
And that's so we don't break our probe sequence.
Okay. So we can find elements
beyond that and the probe sequence.
So what we're gonna do here is I'm gonna create
a new probably seen something very similar in Java.
I'm gonna create, what's called an enum.
And we'll put that here.
enum is short for enumeration called state.
and it'll take on the values empty,
filled
or removed.
And if you've never seen enum before
an enum is a
user
defined
data type
that can only
take certain
enumerated
values.
Okay so this is, this is a new data type.
We have strings, we have ins.
Now we have something called state
and state can be one of these three
and only one at a time and empty, filled or removed.
So we're gonna attach this essentially
to elements in our hash table.
And so we'll be able to set the state.
Is this element empty?
Is it filled or has it been removed?
Okay.
And in order to put that to use, we're going to create
what's called a struct, which is short for structure
and we're gonna call that our hash item
and it's gonna include a hashable,
we'll call that item.
And it's also gonna include the state
that we just created.
And we'll call that status
because we don't want a collision of names there.
Okay.
So what is the struct?
You can think of it as a super baby minimalist class,
but more accurately.
It's an aggregate, an aggregate
aggregate
data type
that
groups
individual
variables
together.
So a hash item structure includes a hashable item
and a state status
and state can be one of these three values.
Okay.
So we're gonna use that in our implementation now.
And so our table is not going to be
of optional hashable types.
It's gonna be of hash items.
Okay.
And in doing that, we're going to be able to
access the elements in the struct
here
with a dot notation.
So we'll have things like
table
sub I
item to fetch the item
and table.
So by
status
to check whether it's empty, filled or removed.
Table size remains unchanged.
We still are gonna store this, get key function.
We're still gonna store this hash function.
And
you know what?
I put these here among the public methods
I'm gonna move them.
I'm gonna make them private
because they don't need to be called from the outside.
So I've just moved these.
So next, next prime
and rehash will be private methods, not public methods.
So my bad on that one.
All right.
So let's implement those real quick.
This
we're gonna use
kind of a brute force approach.
And so if the
input integer N is
even then,
it's clearly not prime.
And so what we'll do is we'll do a conditional to check
If it's even.
If N mod two
equals zero,
then it's even
We're just gonna to pin on that
So we've received N as a parameter we've checked to see
is it even if it's even
we're just gonna bump it up to the next odd number.
Okay so now we have an odd number N
and that may or may not be prime.
We don't know yet.
Okay. So we'll have a bool prime
and we'll initialize that to false.
And then we're gonna have a while loop while not prime.
And what are we gonna do while not prime?
Well, what we're gonna do is we're gonna
set prime
equal two
and then we're gonna do some stuff.
And if certain conditions are met
we're gonna switch prime back to false
before we end a particular iteration of the while loop.
Okay. So what are we gonna do?
Remember we've got an odd number
and what we're gonna do is we're gonna check to see
if it has any divisors
and we have to check divisors up to a square root event.
Obviously we don't need to check beyond that.
So we'll create a little for-loop here
for
int
I equals three.
I
times I
less than N
so that is, I is less than or equal
to the square root of N we're gonna increment by twos.
I plus equal two.
Why?
We don't need to increment one at a time.
We've made this number odd.
We're gonna increment two at a time.
So we're gonna continue to check odd numbers.
We don't, if we incremented by one, we'd do a useless check
on an even number that we already know is not a divisor.
So we're just gonna skip over the even numbers.
And then we have if
N
mod I
equals zero.
So we have this N we're gonna iterate
through all these I's.
And what happens if N mod I is zero,
then we know it's not prime.
So we switched prime back to false.
All right.
So we're gonna proceed with this for loop checking
for divisors.
And then when we're done with that for loop,
we're going to increment N by two
and see if we can find any divisors there.
N
plus equal two,
if we found a divisor
prime is false plus equals to increment by two
for the next test in our, in our loop.
This is the next odd number.
If we exit this loop,
then we know that the last number N
that we found was prime.
So we need to return
N minus two,
because we added two here, but we found that it's prime.
So that's our next prime function.
Now our rehash function.
First thing we're gonna wanna do on a rehash
is we're gonna want to save
a copy of the hash table,
because remember we're gonna take
all the elements of the old hash table and insert them
into the new hash table.
So we'll have a standard
vector
of hash items.
That's our new struct.
We'll call that old table
And we'll assign to that the value of the current table.
And then we want to get the new table size.
So table size
equal next prime
table size
sorry
times two.
So what's happening here.
We have this, a private member table size.
That's an unsigned long.
We want to update it.
So we multiply by two.
We find the next prime
and we reassign that to the table size member.
Okay.
Now we know our new table size
so we're just gonna empty out our table table clear
and that's fine because we've already made a copy.
So we're good.
And then we're gonna resize our table
table resize,
table size.
And that's just a method that that's just
a standard vector method.
These are both standard vector methods.
I should say, clear
and resize are both standard vector methods.
And so this will resize the table to our news table size
and then we want to re insert all of our items.
So we'll start with num items
equals zero to reset that value.
We have num items?
We'll look at that,
we don't have num items.
I have to fix that.
So we'll make unsigned
long num items
and that's just keeping track of the number
of items that we have in our vector, in our hash table.
Okay so now we're good.
Sorry.
Okay.
So what happens next?
Well, we have to iterate
through old table and when we find a value
we're gonna want to insert it into our new table.
Simple as that.
So for
unsigned
long
I equals zero.
I less than
hold
table
size
plus, plus I
so that's gonna iterate through our old table
and then we're gonna use that status element
in our struct
that enum,
if
old table,
sorry,
old table
I
status
equal filled
then we know we have a value insert
old
table
I
items.
So that's explain what's going on here.
(clearing throat)
Excuse me.
We're looping through the old table
we're gonna ignore anything that has been removed.
So we're only gonna concern ourselves with the elements
in our hash table that have their status set to fill.
Then we know we want to insert those into our new table.
And then what we do is we're fetching.
Remember we have a struct now, so we're fetching old table
at this index item and that's our rehash function.
That's all there is to that.
Now let's move on
and do our modifications to insert,
find and remove.
We'll start with insert.
Now here
in our old insert function
we were just calculating the hash to get an index
and then put that item at the spot in the vector.
Okay.
We don't want to do that anymore.
What we want to do instead is we want to do a linear probe.
Okay.
And that is, we'll use a while loop
while
table
index
status.
Again, we're gonna access that status equal filled.
Then we're gonna increment our index.
Index
equal
index.
Sorry plus one.
Why did I put that in parentheses?
What's missing?
You ask?
We have to module, take the module
of the table size.
Why do we do that?
So that we don't run off the end of our hash table.
So we don't want to keep incrementing this.
We want to wrap around to index zero as needed.
So we take the modules table size.
Okay.
So that's going to probe in a while loop
until it finds a spot that's not filled.
Now that could be an empty or something that's previously
been removed.
Okay.
So then the first thing we're gonna want to do
on the insert is we're going to save a copy of the status
state
temp
equal
table
index
status.
That's the old status.
Okay.
And then
We insert the item
table
index
item
equal item.
That's the item that we passed in here gets assigned
to table index item that we found by probing.
And now we're gonna set that status
to filled
table
index
status
equal filled.
And then what do we need to do?
This is where we check to see if we need to rehash.
And so here's where having saved that state comes in.
The number of objects in our table has only grown.
If we've written to an empty element in our hash table
if we've written to a deleted or removed item
we don't need to rehash because we're just
reusing a spot that had already previously been deleted.
Okay that's why.
So if
temp
equals empty
then we're gonna increase the number of items.
Then we need to check if we need to rehash.
So
if
num items
greater than table size,
divided by two
if our hash table is more than half filled
hash
table
more than one half full,
then we rehash.
And all that's gonna do is gonna call
a rehash method.
It's gonna make a copy of the old table
double the table size, find the next prime,
empty out the table,
resize the table,
reset num items to zero
loop through the old table,
find all the filled items and insert them
into the new table.
That's our rehashing.
Okay.
And we only do that on inserts
Next.
What do we need to do?
Well, you saw that we have this linear probing here.
We're gonna need to add that to our other methods as well.
So let me just, I'm gonna modify this
but leave the code up there
so you can see how it's changing.
So we're gonna have a wild loop again while
sorry
table
index
status
is not empty.
Why are we doing that?
Because we want to step over previously
removed items that have their status set to removed.
So we don't break the probe sequence.
Okay.
So then we check to see if there's an item
and to see if that's the one that we're looking for.
So if
table
index
status
equal filled
and
key
remember we're passing in key here equal
get key
for that item table
index
item.
Then we know we found our object
and we just returned that item
return
table
index
item
otherwise
we do what we just did before.
Remember this probe sequence here
we're gonna do that exact same thing.
We're gonna increment our index.
And we're gonna take the modulates
with the table size to make sure
that we don't run off the end
of our half table that we wrap around back to zero.
And then the last thing we're gonna do is
we're gonna return null up.
So that bit of code that I've just produced here
is gonna replace this bit of code here.
So we'll just take that out now.
Right?
So that's our find method
and we're gonna do something very similar for delete.
So we're gonna probe the same way
while
table
index.
This is pretty much identical
status
not equal empty
All right?
And I'm just gonna copy this code and I don't
see any reason to re-type it here.
So I'm gonna get that
if it's filled and the key matches
then we found our item and what do we want to do here?
Here's where we remove it.
We set
table
index
status
equal remove
removed
and then we return the item
return
table
index
item.
And then we're just gonna borrow this piece
of code again, exactly the same thing.
We're just gonna continue in our while loop, okay.
And increment and take the modules to the table size.
And that bit of code is gonna replace
this bit of code here.
So we'll take this out
And that is our
delete function.
Now let's give it a run.
I think the same demo here is gonna work.
We've run this before.
You've seen this before we have the Horner hash
we have to get key function.
We're using our little dictionary class.
We're creating dictionary items
and
then
printing out the table and then we're removing an item
and I'm printing the table again.
So let's run this now.
Oh gosh I forgot to update the print method.
I'm sorry, my bad.
So this has to change
because we no longer have simple objects.
Now we have those struct.
Okay so let's see here
we print the index.
If
table
I
status
equal filled.
Okay. Then what do we do?
Then we
standard see out
table
I sorry.
I
item.
Okay.
Else
if
table
I
status
equal removed
then we'll print an X to indicate
that it's been
that there's been an item deleted at that position.
And then the rest should be the same.
So that should be okay now let's run it.
Okay. There we go.
So what have we got here?
We have
our hash table.
Let me see.
We have all of our values now.
And you can see that it's been rehashed once
since we initialized it with a size of 17
and now it's size 37,
twice 17 is 34.
Next prime number is 37.
So that's why we have a table of a size 37.
And you see here
this is where we had deleted a giggle that was
at 27 years giggle 27.
But notice also that we have a very nice example here
of some primary clustering.
Okay we have a bunch
of elements that are all right there in a row.
And that is one of the things that can happen
with a linear probing.
So codes on blackboard, have a look, give it a try.
See what you think.
More later.