This problem uses a HashTable class to store a dictionary.

File HashTable.java is available on First Class. It is the same hashtable class studied in lecture with the addition of a parameterized constructor so the client can set the initial capacity.

Add methods getCapacity and getClusterLength to the class to get the capacity of the hashtable and the length of the cluster at an index. Two hash functions are included using two different algorithms,

Text file jumbledwords.txt contains about 20,000 words.

Write a main method to load the words from the text file into the hash table of capacity 1009. Code should use the File, BufferedReader and StringTokenizer classes versus Scanner class to practice with these new classes. If the file does not exist, the program should report the problem and end. Otherwise do the input and report the input completed successfully.

Write the length of each cluster to a text file using the File class. Complete the analysis below two times. There are two hash functions listed in the class for you to compare and you will find a third one. Your goal is to note differences in performance and compare results.

• Import the output file of cluster length data into Excel and compute the standard deviation. (STDEV.S)

• Produce a line chart in Excel that plots the cluster sizes. Include a chart title stating which hash function was used (1, 2, or 3 and the standard deviation). If anyone needs help with Excel, stop by to see me; it will take only a few minutes to show you.

• Print the Excel chart.

• Write a paragraph on the chart describing the distribution that you see. What does the standard deviation tell you?Do you think this is an adequate hash function for this data set? Why or why not?

• Research a different hash function and write a short report listing the algorithm, cite its source, and hand-trace the algorithm on a sample word. Repeat the process above on your new hash function.