Lab #8

Due: Friday, January 28, noon

In this project, you will implement a spell checker program in Java. As part of the program, you will implement and use a hash table data structure to store a dictionary of English words. For your hash table, you will need to construct a hash function that operates on strings. Your hash table data structure should allocate and use a hash table of size 51,059. (51,059 is a prime number). You may use the cyclic shift hash code described on page 364 of your text. You will then need a compression map to get a number within the desired range. Your hashing scheme should resolve collisions using open addressing. You should implement all three schemes we discussed in class: Your code should be designed so that you re-use as much code as possible in implementing the three different policies. The chosen policy should be set by a constant which you initialize early on in your code.

On startup, your program should read an English dictionary file, called words.txt. For those of you who may not be familiar with file I/O in Java, I have provided a class FileReader which has a method called readFile. The method takes a String as a parameter. The method will open the file with that name and read its contents. The method will place the strings into an array and return the array. If the file has an incorrect format, it will return a null array.

Below are the files:

Once your program has read the entire English dictionary, it should insert the dictionary into the hash table data structure. Then, your program should prompt the user for a word, lookup the word in the hash table, and return correct or incorrect if the word is spelled correct or incorrectly. Then your program should issue the prompt again for the next round, and so on. Your program should exit when the special word exit is entered.

Experiment with each of the different collision resolution policies. Evaluate each by calculating the average number of probes it takes to add each word into your table.

Turning in Your Code

Turn in your code as usual to the electronic drop boxes. You should also turn in a brief write-up with a description of the hash function you used as well as the results of your comparison of the different collision resolution schemes.