Hash Table with Linked Lists for Chaining
Posted on 2007-12-03
I'm attempting to write a program for class that takes a dictionary file and reads it into a hash table. Then it will prompt the user for their file that they wish to spell check against the dictionary file. It will read that file word by word, and then spit out the words that were not found in the hash table as spelling errors, giving the word that was misspelled, an the line number it was on.
I currently have the file scanner setup so that it eliminates odd characters, and splits up each line into multiple strings. I've never written a hash table, so I'm a bit lost on how to even begin this project.
Here's basically what I understand.
A hash table is an array (obviously). To figure out where to place each word, I'm going to apply the formula given by the assignment specifications, "hashFunction(w) = (c0*73^(0 mod 4) +c1*73^(1 % 4)+&+cn*73n % 4 ) % [TableLength]"
So I understand in theory that if there's a collision, I'll add a node to a linked list on the front of my chain stored in the corresponding array spot. What I don't understand however, is how to implement the code.
Finally, to keep the has function running quickly, I'll start with an array size of 128. When I get 128 words in the array will need to double in size, and when I get to 256, it would double, and then 512, etc.
Thanks ahead of time for any help. If you have a similar program I'd appreciate it, I'm not really looking for the answer, just some code to get me started.