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.