Create the following program using java and post the output as well.

Assignment

In this assignment you are to implement a hash table for use in a simple spell checker. The spell checker should be set up with a GUI for the interface. The hash table MUST be built as specified in this document. The GUI can be built with JavaFX.

You submission must include

A printout of the results from running your program using the two example test sets given at the end of this document. The printout should highlight or mark any words that do not appear in the dictionary.

The results of any other document given as input

The number of collisions in the hash table and the length of the longest chain

A ReadMe file explicitly stating any grounds for extra credit.

There should be multiple sample runs to demonstrate all required functionality.

Hash Table Class

Implement a hash table to store strings (i.e. objects of the Java String class). The Hash Table must be implemented as a data type with the class name "HashTable". The HashTable class will have the following methods:

HashTable ( ) Constructor for a hash table of default size: 1000

HashTable (int n) - Constructor for a hash table of size n.

void Insert (String S) Inserts S into the hash table.

boolean Contains (String S) Return true if S is in the table, false otherwise

int Count ( ) - Returns the number of strings stored in the table

Hash Function

The insertion of a word requires the computation of an array index

array index = HashValue mod array size

The insert function must thus generate a hash value from a given word w. The hash value should be calculated by assigning the values 1 to 26 to the letters a to z (regardless of letter case) and calculating a numerical value based on the letters in the word as follows:

Group the letters of w in chunks of 4. For each four letters, calculate

ch₁ * 31³ + ch₂ * 31² + ch₃ * 31¹ + ch₄ * 31⁰

and add the total value of each chunk to get the hash value. For the actual index of the word, compute

HashValue mod array size

For example the string "cat" has the hash value 90,954:

3*31³ + 1*31² + 20*31¹ = 90,344

and the string table has the hash value 745,810, calculated as follows

tabl = 20*31³ + 1*31² + 2*31¹ + 12*31⁰ = 596,855

e = 5*31³ = 148,955

596,855 + 148,955 = 745,810

For a hash table of size 101, cat maps into the index

90,954 mod 101 = 54

and table maps into the index

745810 mod 101 = 26.

Note: In Java, there is a built-in hashCode function which can be applied to a string object S

S.hashCode()

This built in function computes the hash code for a string S as

S[0]*31^(n-1) + S[1]*31^(n-2) + ... + S[n-1]*31^(n-n)

= ch₁*31^(n-1) + ch₂*31^(n-2) + ... + ch_n

where S[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. This function may NOT be used.

Insertion and Collisions

Your insert function must deal with collisions (a collision occurs when two different strings have the same hash value). You must use linear probing to deal with collisions. You should test your insertion method carefully. In particular you should ensure that insertion still works correctly when the hash table is nearly full.

For one test, consider setting your hash table's size to be smaller than the size of your word list (see below) and attempting to insert the entire word list into the hash table. This may cause errors that you might not encounter with smaller test data sets. When you get your hash function working correctly, and your hash table is an appropriate size you should be able to successfully enter all the words in the word list (see below) into it.

Let N be the number of strings to be stored in the table. Choose an array size that will have a load factor around 1/3. That is, make the size of the array larger than 3*N. You must choose a modulus that is prime (i.e. choose an actual array size that is a prime number just over 3*N) and have your program automatically choose this prime number. Automatically means that your program needs to use the size of the word file as a starting point in your search for a prime; do not hard-code a value that happens to work for this data set.

Spell Checker

Use your hash table to implement a simple spell checker. The spell checker should load a dictionary into a hash table, and then test each word in a given document to see if it is contained in the dictionary. For the dictionary you must use the list of frequently used words given in the text file SpellCheckDictionary.txt posted on the website. Store this file in the project for access by your program in the project.

There are two documents to be spell-checked given at the end of this assignment. Place the first document in a text file called TestFileDogs.txt. Place the second in a file called BillOfRights.txt. Your sample runs should include checking both of these files.

Your spell checker should thus be implemented as a program that reads in the dictionary file and the name of the file to be checked, and then checks the file for possible spelling errors.

Simple test text

This is a test document.

How many dogs can fly?

Do you think this realy works?