- [Instructor] Okay, so let's make a HashTable.
Let's start with a header file
and we'll call that HashTable.
And let's see, what are we gonna need?
Let's use that snippet from the previous video,
one of the previous videos, anyway.
This is the optionals here.
I'll explain again what that is in case you missed that
in the one of the previous videos.
What we're doing here is we want to use C++ optionals,
and they're in different locations depending
on the standard of C++ that you're using.
If your standard is less than 17,
they're to be found in experimental.
And if your standard is 17 or greater,
they're kind of built in and you can just include optional
directly rather than experimental optional.
So, we have these preprocessor directive
with a little if else to handle that.
And what else are we gonna need?
We're gonna need functional.
That was also introduced in an earlier video.
So, let me stop here and say this.
If you haven't watched the videos
for optionals and passing functions,
then please go back and watch those videos
before you continue with this one.
That said, I'm gonna need iostream.
We're gonna need string.
And we're gonna need vector.
What I'm going to do is I'm gonna go through HashTable,
make a very simple HashTable,
and then we'll add features to it as we go.
So, we'll start out with just handling strings
and then we'll set it up so
that it can handle objects of your custom type.
And then later on we'll expand it
to handle collisions and things like that.
But right now, it's just going to be bare bones.
But nevertheless, I'm gonna set this up
as templated planning for the future.
So template,
type name,
HashTable, or Hashable, sorry Hashable,
Hashable type and class HashTable.
And we're gonna have some private members.
And we're gonna have a standard vector.
That's optional HashTable.
I'll explain in a second.
And we'll call that table,
and we're going to have an unsigned long,
just so we can handle very large numbers, table size.
Now, what have I done here?
Standard vector optional Hashable table.
We have a vector of optional Hashables.
And that means that the vector can hold
either a null pointer or a Hashable object.
And again, if you haven't seen the video
for C++ optionals, please, please do so now.
But this allows us to return an indicator
that an element in our vector is empty
and return the object stored in that element,
if there is in fact an object stored there.
So, that's what optionals are doing for us here.
And then again, hearkening, back to a previous video,
we showed how to pass functions around in C++.
Here, we're gonna wanna store our hash function.
And so, we're going to have standard, and this is function.
So, this is a function type.
And it's a function that returns an unsigned long
and takes as parameters, a standard string
which is gonna be our key value, and an unsigned long
which is our table size.
And we'll call that hashFunc.
Here, we're declaring a private member.
That's a function that returns an unsigned long
and takes a string and an unsigned long as parameters.
That's where we'll store our hash function.
And now, our public members, so public.
And we're going to need a constructor
as you might expect, HashTable,
unsigned long
table size.
And we're also gonna pass in that function.
Let's just grab all this good stuff here.
So, that's the signature of our constructor.
And then when we get those parameters,
what are we gonna do with them?
We're going to set this
table size,
equal table size,
and this hash function
equal hashFunc.
So, we're storing a function in this private member here.
And then we're going to call a function here,
table resize,
tableSize.
So, we have this table here
and when we pass in this unsigned long table size,
then we're going to call resize
on table passing in that parameter
so it adjusts the size of our table.
Now, what else are we gonna need?
We're gonna need void insert Hashable key.
So, we're gonna insert some key into our HashTable.
We're going to want a find,
so that's going to be optional Hashable.
So, when we find, we're either gonna return the object
or we're gonna return this null thing,
and that's find
Hashable, sorry, Hashable key.
And we're gonna want a delete method.
Optional
Hashable
remove, we'll call it,
Hashable key.
And so, when we remove an object,
it'll either remove the object and return it,
or it will return that null opt.
And then this will come in handy.
This is a getter for table size.
So, that we can check to see what our table size is.
And you'll see why that's handy
a couple of lectures from now.
So, trust me on this one, we're gonna want that getter.
And then finally, a void function to print the table.
Okay, and that's gonna be a constant function.
So is this.
So, let's knock off the perfunctory ones first.
This one's super easy, return table size.
And then let's do that print table
and have a little loop
through our table for int i equal zero,
i less than table size,
plus plus i, there's our loop.
And while we do that standard c-out
i will give the index there,
and then we'll put a little divider here.
And then recall that we may
or may not have a value at that index.
We may have a pointer to the value, or we may have null opt.
So, we have to deal with that.
So, we'll do a test here, if table sub i.
If there's anything there
then we're going to print that stuff.
And recall that optionals will give us null opt
or a pointer, so we have to dereference that pointer
to get our object.
And then here,
we'll put an end line.
So, that's our print table function.
So now, let's get to the meat of this thing here, insert.
Well, what happens when we insert?
We've got a key.
And so, what do we need to do?
We need to do the calculation that turns
that key into an index.
And that's what our hash function does.
Unsigned long
index equals hash function,
key, table size.
So, when we constructed the object,
we passed in a function that got stored
in this private member here.
And then when we do an insert,
we're gonna call that stored function,
passing in the key and the table size
to get our index where we want to store our object.
And then it's a simple matter, table index equals our key.
Again, I'm keeping this pretty simple.
We're gonna expand on this later.
Now, finding, we're gonna do exactly the same thing.
We're passing in a key.
We wanna know, is there an object that matches or not?
And so, we're gonna get that index again.
And then just as we did here,
where we were testing to see if there was something
in fact stored at that index,
we're gonna do the same thing here.
So, if table index,
if there's something there,
and then we're gonna perform a comparison.
If key equals table index,
that is, we've checked to see
if there's something stored at that index.
And now, we're checking to see if the value stored
at that index does in fact match our key.
And if that's the case. then we're gonna return that thing.
Return, and remember we have to dereference it.
Now, what do we do if we don't find anything?
Well, we return null opt
to indicate that we weren't able
to find that value in our table.
And then finally, we have a method to remove an item,
and this is gonna look very much the same.
So, let me just copy this good stuff here.
That's gonna be very much the same.
We're going to calculate the hash to get the index.
We're gonna look at that index,
see if there's anything in fact stored there.
We're gonna check to see if it matches our key.
And if it does, then what we're going to do is,
what we'll do is we'll call this return item.
That's going to be a Hashable.
And then we're going to set the value
at that index to null opt, to indicate deletion.
Sorry, null opt.
And then we're gonna return this return item.
And that is our HashTable.
Now, let's write some code to run it through its paces.
So, we'll write a little program here to test this.
We'll call this HT, short for HashTable demo.
All right, we're going to need iostream,
and we're gonna need our HashTable.
Now, we're going to need a hash function.
Because remember when we instantiate objects
of the HashTable type, we need to provide it
with a function, a hash function.
That gets passed in and stored and then used as needed
as we've seen in the header file.
So, unsigned long,
and we'll call this hornerHash,
'cause we're going to use that hornerHash function
that we saw on an earlier video.
And that's gonna take us, and our string, call it key,
and a tableSize, unsigned,
long tableSize.
And then we're gonna have main.
And it's gonna return zero,
and we'll fill that out in a little bit.
So, if you'll recall
from the earlier lecture,
what we do with the hornerHash is we start
with an unsigned long.
I'll call it hashValue
equals zero.
And then we're passing in a string.
We're gonna iterate through that string.
So, for constant character,
call it letter.
Nah, I like c better.
C in key,
that's just gonna iterate
through all of the characters in our string.
And yes, we are pretending that Unicode
and multibyte and codings and all that stuff don't exist.
But this will serve for our purposes.
Again, we're just gonna iterate
through the characters in our key.
And then we're gonna calculate hashVal,
using Horner's Method,
equals hashVal.
And it's got to be a prime number here,
or it should be a prime number, 37 plus c.
And then when we're done,
return hashVal modulo,
the table size.
And that is our hornerHash function that we're going to pass
to the constructor when we create our HashTable.
So, let's do that.
HashTable,
and we have to give a type,
standard string HashTable, we'll call it.
And we'll make it of size 53, 53 is prime, hornerHash.
So, we're passing in the size
and we're passing in this function
that will become part of our HashTable object.
Now, let's do some insertions.
HashTable insert,
Hello, World!
And let's just do a few more.
Just gonna copy this and replace the strings here.
Oh, CS, UVM CS 124,
who is Egbert Porcupine?
Doesn't really matter what our strings are here.
We're just testing.
And then UVM stands for in Latin,
Universitas
Viridis
Montis.
That's Latin for University of the Green Mountains.
That's what UVM is all about.
And then we're gonna print our HashTable.
HashTable, print,
sorry, print table.
And let's just run this real quick
to see what that looks like.
Make sure that we're, oops, what have I done wrong?
Oh, functional, sorry.
This should be functional, not function.
Now, let's build it again.
Another typo.
Where's my typo? Here, endl.
Left out an L, sorry.
Okay, there we go.
So, let's just take a quick look here.
We have a HashTable of 53 elements.
So, the indices run from zero to 52, as we expected.
Where's our demo code? There we are.
We inserted these strings, UVM CS 124 wound up
at index five using that hornerHash function.
Hello, World! wound up index 13.
Who is Egbert Porcupine wound up at index 22.
And Universitas Viridis Montis wound up at index 40.
So, that looks like our print table function
and our insertion function are working okay.
So, let's expand our code a little bit
to exercise some of the other parts of our code.
Let's do a find.
And we're gonna get a optional back
because we may or may not have a value, standard string,
S equal HashTable find
and we'll search on Hello, World!
And if we find that, then let's print it.
So, if S, if what's returned is not
that null opt, then standard c-out.
Dereference S
is in the table,
S-T-D, E-N-D-L,
remember the L this time, Clayton.
And then let's do a remove.
S, and it's gonna be the same thing here
except we're gonna make this remove.
And then the same thing here,
if S then we're gonna say,
has been removed.
And we could put in an else clause here.
Let's just do that else,
Hello, World! was not found.
And if everything goes right, that won't print.
And again, we'll do the same thing here.
Add an else clause, Hello, World! was not removed.
And so, when we do this, when we run this code,
it's gonna find Hello, World!
It's gonna call find with the Hello, World! parameter there.
And if we get back a non null value
then it's gonna print the dereferenced value
and say, yes, we found it in the table.
Otherwise, it's going to say it was not found.
And then we're gonna remove it.
And then let's just print that table one more time
to verify that it was in fact removed.
Now, let's run this code again.
Let's take a look.
So, this is the table that we printed
at the beginning running from zero to 52.
And it has all four of the strings that we inserted.
That's good.
We have this output showing that Hello, World! was
in the table, that Hello, World! was in fact removed.
And now, when we print the table
we should see that Hello, World! is not in the table.
What was the index it was at, 13?
13 is empty.
So, it was in fact removed.
So, that completes our bare bones implementation
of a HashTable.
And in the next video, what we'll do is we'll expand
on this so that it can handle objects of your custom type.
And you'll see that we'll have to add another function
and pass in another function
to the HashTable when we construct it.
And we'll go from there.
That's all for now.