BRAIN YU: When you're loading words into your dictionary
and when you're checking to see if a word is spelled correctly or not,
you're going to need to call on your hash function,
a function that's going to take a word and return
which index into your hash table you should use in order to find that word
or insert the word into your data structure.
So what is the hash function?
Well, the hash function is going to take a char star or a string
as input representing the word that you're going to hash.
And it's going to return an unsigned integer, an integer that
won't be negative, representing which index into the hash table
you should use that corresponds to that particular word.
So what does your hash function need to do?
Well, it needs to take as input a word, and that word
is going to have alphabetical characters,
and it may have apostrophes in it as well.
And the output of your hash function is going to be a numerical index between 0
and N minus 1 inclusive.
Recall that N is defined at the top of the file
and is the total number of buckets in your hash table,
in other words, the length of that array of linked lists.
We've, by default, set N equal to 1.
But you can and should set N to be some larger number
so that you have more buckets in your hash table
and, therefore, can spread your data out a little bit more
making for faster search times.
And importantly, your hash function should be deterministic.
If I give it the same input again and again,
I should get the same output, such that when I'm loading a word like apple
into the dictionary, I'll be able to calculate
the hash value of the word apple and insert apple into that index
into the hash table.
And then when I'm checking to see if the word apple is spelled correctly or not,
I should be able to call the hash function on the word apple,
get the same value as before, and then check
only that particular linked list in the hash table
to see if the word apple is there or not.
So you'll need to decide on a value of N,
the number of buckets that your hash table is going to have,
in other words, the length of your array, and also the possible values
that your hash function can return.
A larger N value means you have more buckets and your hash table
and, therefore, data is spread apart more
and could potentially mean faster search times.
But you'll need to make sure that the output of your hash function
is some value between 0 and n minus 1 inclusive
because those will be the only valid indices into your hash table.
If your function were to end up with a value greater than N
you could always take that value mod N or the remainder
when you divide by N, in other words, to get a value that's
in the appropriate range.
Now what are some examples of some hash functions?
Well, a very simple hash function might just take the first letter of the word.
If the first letter of the word is A, then the hash value is going to be 0.
If the first letter of the word is B, the hash value
is 1, so on and so forth.
If the first letter of the word is Z, the hash value might be 25.
In this case, your value of N is 26 because you'd
have 26 different buckets, one for every letter of the alphabet.
Of course, 26 isn't very many buckets, especially considering the fact
that the large dictionary that we're going to give you
contains more than 143,000 words.
So you might consider using other hash functions,
like looking at the first two or three or more letters
or doing some sort of math using all of the individual values of the letters.
But once you've completed the hash function,
you'll now have the ability to take a word
and determine which of the linked lists inside of your hash table
it should correspond to.