- [Instructor] Okay, so now that we have
a working basic Hash Table,
we're going to modify that Hash table class
to handle objects that have a key field.
So in the first iteration
that I showed in the previous video,
we were just passing in strings
and putting strings into a Hash table.
But for your projects, and for a more realistic example,
we want to be able to pass in an object
that we want to insert into our Hash table.
And so in order to do that, our Hash table needs to be able
to find the appropriate key.
And so just like we passed in a Hash function,
so that the Hash table could use that function,
we're going to allow for passing in of a get key function.
That's going to be used by the Hash table
to retrieve the key from objects
of the type that I defined here.
And when it comes time to be your turn,
you'll use objects of your custom class.
So, first what I did,'
was I created a very simple dictionary class.
It has two private members.
Your objects obviously will have five or more
but this has two, a word and a definition,
those are the private members.
This is called dictionary item.
There's a constructor that takes the word and the definition
and assigns the appropriate values to the private members.
There are getters and setters, get word, get definition.
There are setters, set word and set definition.
And then these should look familiar
because you've done these in your classes.
This is a function that overrides
the stream insertion operator for pretty printing objects,
just prints the word and the definition.
And then we also have this function.
Which is used to compare two dictionary items.
Are they the same?
And the method that it uses is,
it checks this key value word and if they're the same,
then the objects are equal.
And again, you've done something very similar to this
in your own custom class.
And so now we'll modify our Hash table accordingly.
So what do we need to do?
Well, we're going to need a new private member
that's gonna be a function.
And that function is going to return a string,
when provided with a Hashable.
And we'll call that, get key.
And then we need to add this exact same thing to our,
function signature for our constructor, we'll do that here.
And so now, when we want to instantiate a Hash table object
we pass it the table size,
we pass it that get key function,
and we pass it the Hash function.
And we also need to assign
the get key function that we passed in to the constructor.
Get key, to the get key member.
Alright, so that's our modified constructor.
Now we have to modify, insert, find and remove.
And the modifications are very simple.
So in our earlier example, we were passing in a string
as a Hashable, and it was just that value, just the string.
We were inserting strings into a Hash table.
So, now the only thing that's really gonna be a Hashable
is what we're passing into insert.
And we'll call that item.
And then insert needs to know how to find the key.
So we just get that key.
So standard string key,
equals get key item.
So now we passed in an object,
we call get key to get the key from that object,
and then we passed that key to the Hash function
along with the table size to get the index.
And then we insert the item, okay?
So far so good.
Now let's modify, find and remove.
Now, as you recall, before we were just passing in a string
we were adding strings to our Hash table.
Now we're passing in objects, but when we find and remove
we don't know if that object exists.
So we're going to pass a string,
to find,
that will serve as the key.
We don't need to use get key here
because we're just looking to see
does this key exist in the table?
We don't know if there's an object there yet.
But if we do find an object,
if there is something here at table index,
whatever that index is that calculated index from the key,
then we need to perform a comparison, get key,
to see if we found a match.
And if we do we return the D referenced pointer
to the object and if we don't find it
then we return all up, that's all the same.
But we need to make the same modification for remove,
so this becomes standard string.
And then if we find an object
we wanna perform the comparison on the keys so we get key
on this object,
that we get from the D referenced pointer,
and everything else is the same.
So now we've completed our modifications
of our Hash table class so that it can handle objects.
Print table doesn't change that's all the same.
Everything else is the same, all right.
So I prepared a little demo here to test this
and to show you how we implement the get key function.
So here's the get key function.
And you'll recall that we're working
with this class of dictionary items.
And recall also that each dictionary item
had a word and a definition, and the word is the key value.
Okay, that's our unique field
in our collection of dictionary items.
So we write this function that returns a standard string
we call it get key.
It takes a dictionary item D, and then calls the getter
get word on that dictionary item and returns that word.
So that's how we get key.
And that's what we pass in to our Hash table.
So we have here a constant
that's our table size 17, 17 is prime.
And then when we instantiate our Hash table,
our Hashable is a dictionary item.
We'll call this Hash table, we're passing in the table size.
Now we're also passing in the get key function.
That's this function here and our Hashing function.
So we're passing in two functions as required.
And then what we're doing,
is we're creating eight different dictionary items.
And again, the dictionary entry is just a word
that's our key and the definitions.
A dentist is a person who takes care of teeth.
Then we insert that object into our Hash table.
Giggle is a high pitched laugh,
and we insert that item into our Hash table.
Then we do the same thing for potato,
shoe, yak, axle, cone, and fish.
And then we print our table.
Now there's something funny going on in here.
And you'll see when we print the table, what that is.
And by way of explanation, I've also printed out here
the key value, the word, and the output
of our Horner Hash for each one of those words.
So we can see what the result is there.
Then, finally, we do a find on giggle
to make sure that that works and we do a remove
on giggle to make sure that works.
And then we print our table again to verify.
So let's run that and see what happens.
Okay, so here's our output, just expand this.
Okay, so,
here's our Hash table, we have 17 entries,
with entries C0-16.
Fish, shoe, cone, potato, yak, axle, giggle.
Now wait a minute, what happened to dentist?
We had eight objects that we inserted,
one, two, three, four, five, six, seven, eight,
but there's only seven here.
One, two, three, four, five, six, seven.
What happened to dentist, did it not work?
Well, here's what happened.
Take a look at the values that Horner Hash returns
for each of these strings.
Dentist gives us a zero, giggle gives us 12,
potato seven, shoe four, yak eight, axle 10,
cone six, fish zero.
So we have, what's called a Hash collision.
We have two values here,
two keys that give us the same Hash.
So when we inserted fish,
it overwrote the value for dentist and that's why dentist
does not appear in our Hash table, and that's not good.
And we'll get to that in a minute.
And then we wanted to verify that deletion
does actually work, removal actually works so,
we remove giggle and we see giggle is no longer
in our Hash table, it was at index 12,
and now when we look at index 12
we see there's nothing there, so that works as expected.
So what happened here?
We had a collision.
We had dentist and fish gave us the same index
when we ran it through our Horner Hash function.
And if we go back to our Hash table here,
we'll see here on the insert there's nothing
that checks to see if there's already a value there.
So it just overrode the value.
We had dentist and we overrode it with a fish.
So that's not good, we don't want that to happen.
We'll lose data.
So what we're going to need to do in subsequent videos
we're going to need to demonstrate
what are called collision resolution policies.
There are some that are presented in the book,
and we're going to go over some of these
and build a more sophisticated Hash table
that can handle collisions.
That'll be in future lectures, but that's all for now.