Requirements:

1.  [35 points] Make the size of the hash table’s array dynamic.

The starter code in the file HashSeparateChaining .java contains a functional implementation of a hash table where collisions are resolved by separate chaining.  Each key-value pair in the table is contained in an Entry object, defined in the Entry .java file and has the following properties:

– The key is a String.

– The value is an Integer.

However, the size of the array that is used to store the entries is static (fixed) in the starter code. From lecture, we know that this is not ideal because as more and more entries are added to the table, the average length of the chains will become longer and longer. Long chains destroy the efficiency of searching in the hash table, so we would like to avoid this by resizing the hash table’s array when appropriate.

Your first task is to implement the resize method. You must also modify the put and delete methods to call the resize method at the appropriate times! Read through each method carefully before you make the modifications so that you understand exactly what it is doing and how it is doing it.  Note that the constructor contains parameter variables that specify when you should double the size of your table (doubleFactor) and when you want to halve your array (halveFactor) based on the average length of the chains.

2.  [15 points] Complete the method getMap in class HashTableApp .java.  The main method of this program will take in one parameter, the name of a text file. It will read in the contents of the text file one word at a time and maintains an entry in the hash table for each word where:

– The key is the word from the text.

– The value is the number of times that the word has appeared in the text so far.

To test your program, you should start by generating a few small text files where you can directly control the frequencies. The A5 folder has a small test file hamlet .txt and a large file WarAndPeace .txt, which contains the full text of the novel War and Peace.

Tip: You may want to start by implementing getMap in class HashTableApp .java and testing the hash         table on a small text file without resizing. Then, implement resize in class HashSeparateChaining .java    and make sure put and delete are calling it at proper times. Now, re-run the tester class HashTableApp .java and observe the changes to the hash table’s size and chain lengths.

Note: There is a toString method included in HashSeparateChaining that will create a text rep- resentation of the hash table. You can use this to print out your hash table and look at its structure.