- [Instructor] Hey there.
I'm assuming that you've already seen
the instructional video
on separate chaining
and so what we're gonna do here
is we're going to implement separate chaining
in a hash table
and rather than start from scratch,
I'm just gonna modify the existing hash table
that we've been working with.
If you'll recall, we first built a very naive version
of hash table that just worked with strings
and then we added to that HashTable class the ability
to handle objects
by including an additional getKey function.
And what we're gonna do
is we're just gonna modify that hash table,
again to support separate chaining.
And I think you'll find
that these are pretty straightforward changes.
Our HashTable class isn't going to change too much,
except now, instead of having just a vector
of optional Hashables,
we're going to have a vector of vectors of Hashables, okay?
So let's make the first change.
We're gonna change this standard vector
of optional Hashables to a vector
of vector of Hashables, okay?
And that's the fundamental change
in the underlying data structure.
Now we have a vector of buckets basically.
And as you might expect,
we're going to have to change our insert,
find and remove functions, okay?
Right now, as you'll recall,
we're just overwriting the value in the insert function.
So if we have a hash collision,
we just overwriting the value.
That we don't want to happen.
So what we're gonna wanna do is we're going to want
to search through the bucket
to see if that value already exists
and if it does not,
then we're going to insert a new object.
So we're gonna leverage,
notice that we have this find function here.
Now, we're gonna modify that next
but we're going to behave as if it were already changed.
So what we're gonna do is we're gonna put in a test.
And that is if we don't find that key,
then
we're going to insert our object
by pushing it onto the vector.
So table index.
Which vector?
The one at that index.
Push_back item.
Okay?
So see what we've done here?
We're still getting the key,
we're still calculating the index where it should go
using our hash function.
But now before we insert,
we're going to look to see
if that key already exists
and if it does, then we're not gonna do anything
and if it doesn't already exists,
we're going to add it to the bucket
and of course, this line goes, let's go.
So that's our insert function.
That's the only change we needed to make.
Now let's do our find function.
So what's going on here?
Let's see here.
We're getting a string that's a key.
We're calculating the index from the key
in the tableSize.
That looks good.
But then we're gonna want to loop through the items
at that index
and check to see if that key exists.
So rather than just what we're doing here
is getting the key of whatever's sitting
at that index, assuming that it's just one element
and not a vector, we're performing this comparison
but here we need to work with the contents
of a bucket, which may be more than one element.
So let's create a for loop.
Int i equals zero.
I, oops, i less than table at this index size.
Now, remember, we're getting the size of a bucket
at this index, okay?
++i.
And then what we're gonna wanna do
is we're going to want to check to see if it's the item
that we're looking for.
So if key,
and this is gonna replace this code that I saved here below
just for comparison purposes.
If key equals, I'm sorry, if key
equals getKey,
now before, we were using optionals here
and de-referencing a pointer
to this value here that's stored at table index,
we're not gonna do that anymore.
We're going to use getKey
but we're gonna use table at this index
and then since we have a loop through the bucket,
which is indexed by i,
this is the ith item in that bucket.
So if this key equals the key
for the ith item in this bucket,
then return
table index
i.
So we're gonna return that item if we find it
and I have a problem here.
Why is that red?
Oh, I see, I'm missing a closing paren.
Okay.
So that replaces this code.
But we're still gonna return a nullopt
if we don't find it
because this is an optional Hashable.
This is the return type, okay?
So we're gonna leave that
and that's our new find function
and that's what being called by insert,
so when we insert,
we're gonna call find with the key.
If it finds the object,
it's gonna return the object
and then this will evaluate to false
and we won't insert the item.
Otherwise it'll return nullopt
and this will evaluate to true
and then will add the item, okay?
Now we have to modify or remove
and the modifications for remove
are going to be very similar
to what we have for find.
So I'm gonna do what I did before.
I'm just gonna leave the old code there,
so you can see what I'm changing and why
and write some new code.
So for int i, this is gonna be exactly the same,
equals zero, i less than table
index size, the size of this bucket.
Size.
There we go.
++i.
Okay.
And now we're gonna do this same thing here.
If getKey, so I'm just gonna copy and paste.
If that key exists,
then we're gonna do this old swaparoo here.
So before we're de-referencing this pointer
that was stored here
to get the return item,
now we're going to just return the value
that we find at the appropriate index
within that bucket, okay?
So Hashable
returnItem
equal table index i.
Just copy and paste this.
Okay?
And then we need to remove the item.
Now, I don't know that we've seen this before.
If we have, forgive me
but if we haven't, then it's all good
and maybe a reminder's okay.
Vectors have an erase function
and what you do is you specify what you wanna erase, okay?
So you have table index
and that is our bucket
and then we're going to erase within that bucket
table index begin,
it's the beginning index,
which is gonna be zero plus i.
And this is how we erase an element
within a vector.
We're just calling that vector's erase method, okay?
And then we return returnItem.
And that replaces this code.
But if we did not find the item,
we're still gonna return nullopt, okay?
Now, we have more thing to change.
What is that?
It's the printTable function
because before, we were assuming
that there was a single value or a nullopt
at each position in our hash table
but now we may have multiple values within a bucket
at a particular index.
So we're gonna have to make a similar kind of a change.
And so let's, I'm just gonna copy this,
'cause this is gonna be the same.
Scroll up so you can see what I'm doing better.
There we go.
Okay, we're still gonna iterate
through our hash table finding the appropriate buckets.
And then we're going to standard,
oh, actually, I'm just gonna borrow this code.
This is the same.
But now we have to look at all the elements
within the bucket.
So we're gonna have an inner loop here.
So for int j equal zero,
j less than table i,
less than the size of that bucket.
++j.
That's our inner loop.
This is iterating through the items in the bucket.
Now we send a standard out.
Std::cout
table i, that's specifying the bucket
and then j specifies the item within the bucket.
And then let's put a separator in here.
Just a comma, that should suffice between records.
And then we need, we'll just borrow this.
Std::cout.
And that replaces this.
So that all goes.
And now we've modified our hash table
so that it supports separate chaining.
Now, let's go back to our demo.
And I don't think we need to change this.
I think we exercise our code the same way
and we'll see that instead of overwriting dentist with fish
when we run printTable,
we will see that dentist and fish
are both in the same bucket, okay?
'Cause if you recall,
dentist and fish both had the same index
when we calculated the hornerHash, that was zero.
So everything else should function fine.
So we don't need to change this code
in order to test our modified class.
So let's run that.
Okay, let's take a look.
So now you'll see we have this hash collision
and now we have two items stored
at index zero where we had overwritten before.
These others don't have hash collisions
and again, recall that both of these fish
and dentist gave us index zero
and then what we did was we deleted giggle
and so we're verifying that this works.
Giggle was at index 12.
Now at index 12, there's nothing.
And so we know that our code works.
And that is a complete implementation now of a hash table
with separate chaining.
Code's on Blackboard, have a look.
Thanks. Bye.