>> ROB BOWDEN: Hi.
I'm Rob, and let's hash this solution out.
So here we're going to implement a general hash table.
We see that the struct node of our hash table is going to look like this.
So it's going to have a char word array of size length plus 1.
Don't forget the 1 since the maximum word in the dictionary is 45
characters, and then we're going to need one extra character for the
backslash 0.
>> And then our hash table in each bucket is going to store a
linked list of nodes.
We're not doing linear probing here.
And so in order to link to the next element in the bucket, we need a
struct node* next.
So that's what a node looks like.
Now, here is the declaration of our hash table.
It's going to have 16,384 buckets, but that number doesn't really matter.
And finally, we're going to have the global variable hashtable_size, which
is going to start off as 0, and it's going to keep track of how many words
were in our dictionary.
All right.
>> So let's take a look at load.
So notice that load, it returns a bool.
You return true if it was successfully loaded and false otherwise.
And it takes a const char* star dictionary, which is the dictionary
that we want to open.
So that's the first thing we're going to do.
We're going to fopen the dictionary for reading, and we're going to have
to make sure that it succeeded so if it returned NULL, then we did not
successfully open the dictionary and we need to return false.
>> But assuming that it did successfully open, then we want to read the
dictionary.
So keep looping until we find some reason to break out of this
loop which we'll see.
So keep looping, and now we're going to malloc a single node.
And of course, we need to error check again so if mallocing did not succeed
and we want to unload any node that we happened to malloc before, close the
dictionary and return false.
>> But ignoring that, assuming we succeeded, then we want to use fscanf
to read a single word from our dictionary into our node.
So remember that entry->word is the char word buffer of size length plus
one that we're going to store the word in.
So fscanf is going to return 1 as long as it was able to successfully read a
word from the file.
>> If either an error happens or we reach the end of the file, it will not
return 1 in which case if it does not return 1, we're finally going to break
out of this while loop.
So we see that once we have successfully read a word into
entry->word, then we're going to hash that word using our hash function.
Let's take a look at the hash function.
>> So you don't really need to understand this.
And actually, we just pulled this hash function from the internet.
The only thing you need to recognize is that this takes a const char* word,
so it's taking a string as input and returning an unsigned int as output.
So that's all a hash function is, is it takes in an input, it gives you an
index into the hash table.
Notice that we're modding by NUM_BUCKETS so the hash value returned
actually is an index into the hash table and doesn't index beyond the
bounds of the array.
>> So given that hash function, we're going to hash the word that we read
from the dictionary and then we're going to use that has to insert the
entry into the hash table.
Now, hashtable hash is the current linked list in the hash table, and
it's very possible that is just NULL.
We want to insert our entry at the beginning of this linked list, and so
we're going to have our current entry point to what the hash table currently
points to and then we're going to store in the hash table at the hash
the current entry.
>> So these two lines successfully insert the entry at the beginning of the
linked list at that index in the hash table.
Once we're done with that, we know that we found another word in the
dictionary and we increment again.
So we keep doing that until fscanf finally returns something non 1 at
which point remember that we need to free entry, so up here, we malloced an
entry and we tried to read something from the dictionary.
And we did not successfully read something from the dictionary in which
case we need to free the entry that we never actually put into the hash table
and finally break.
>> Once we break out, we need to see, well, did we break out because there
was an error reading from the file, or did we break out because we reached
the end of the file?
If there was an error, then we want to return false because load did not
succeed, and in the process, we want to unload all the words that we read
in and close the dictionary file.
Assuming we did succeed, then we just still need to close the dictionary
file, and finally return true since we've successfully loaded the
dictionary.
And that's it for load.
>> So now check, given a loaded hash table, is going to look like this.
So check, it returns a bool, which is going to indicate whether the
passed-in char* word, whether the passed-in string is in our dictionary.
So if it is in the dictionary, if it is in our hash table, we will return
true, and if it's not, we will return false.
Given this passed-in word, we're going to hash the word.
>> Now, an important thing to recognize is that in load, we knew that all of
the words were going to be lower case, but here, we're not so sure.
If we take a look at our hash function, our hash function actually
is lowercasing each character of the word.
So regardless of the capitalization of word, our hash function is going to
return the same index for whatever the capitalization is as it would have
returned for a completely lowercase version of the word.
All right.
>> So that's our index.
It's the hash table for this word.
Now, this for loop is going to over the linked list
that was at that index.
So notice we are initializing entry to point to that index.
We're going to continue while entry does not equal NULL, and remember that
updating the pointer in our linked list entry equals entry->next, so have
our current entry point to the next item in linked list.
All right.
>> So for each entry in the linked list, we're going to use strcasecmp.
It's not strcmp because once again, we want to do things case insensitively.
So we use strcasecmp to compare the word that was passed to this function
against the word that is in this entry.
If it returns 0, that means there was a match, in which case we want to
return true.
We successfully found the word in our hash table.
>> If there was not a match, then we're going to loop again and look at the
next entry.
And we'll continue looping while there are entries in this linked list.
What happens if we break out of this for loop?
That means we did not find an entry that matched this word, in which case
we return false to indicate that our hash table did not contain this word.
And that's it for check.
All right.
>> So let's take a look at size.
Now, size is going to be pretty simple since remember in load, for each word
we found we incremented a global variable hashtable_size.
So the size function is just going to return that global
variable, and that's it.
>> Now finally, we need to unload the dictionary once everything's done.
So how are we going to do that?
Right here, we're looping over all buckets of our hash table.
So there are NUM_BUCKETS buckets.
And for each linked list in our hash table, we're going to loop over the
entirety of the linked list freeing each element.
Now, we need to be careful, so here we have a temporary variable that's
storing the pointer to the next element in the linked list.
And then we're going to free the current element.
>> We need to be sure we do this since we can't just free the current element
and then try to access the next pointer since once we freed it the
memory becomes invalid.
So we need to keep around a pointer to the next element, then we can free the
current element, and then we can update our current element to point to
the next element.
>> We'll loop while there are elements in this linked list.
We'll do that for all linked lists in the hash table, and once we're done
with that, we've completely unloaded the hash table, and we're done.
So it's impossible for unloads to ever return false, and when we're done, we
just return true.