1 Constructing a Hash Table Create a hash table class: public class HashTable From there, build a hash table of an \"optimal\" length that you choose (around 100, but not more than 150). The hash table should be an array of NGen (recall N Gen is the generic linked list node class; very similar to the Node class used for linked lists in Project 3), and should use \"chaining\" (as discussed in lecture) to handle collided elements. You can use the provided NGen.java le. For the general case: (unknown data, e.g. gettysburgtxt), do not attempt to build a table that specic case? Do even, odd, or prime number table lengths make a difference with the same hash function? 0 You must have a main method in HashTable.java which creates and displays a general hash table with length S 150 that uses the best performing hash function for the general case. This hash table must contain the tokens from gettysburgtxt. The general hash must have the following requirements: Longest length 3 7. In the main method, you must also create and display a specic hash table with length 5 500 that uses the best performing hash function for the specic case. This hash table must contain the tokens from keywordstxt. The specic hash must have the following requirements: Longest length 5 7. Note: While we mention performance details such as average collision length for what is considered a \" good\" hash function for the general and specic cases, grading for this project will be only focused on the above requirements. is large enough to contain all the data. Rather, it will be the goal of your hash function to evenly distribute the chains of collided elements over the length of your table. For the specic case: (known data, e.g. keywordstxt), you will want to minimize the length of the table without creating large numbers of collisions but a few evenly distributed collisions are just ne. Later, you will experiment with different hash functions to nd one that works better with the general case and one that works better for a specic case. It is acceptable if these end up being the same function. In order to decide which hash function to call when we add to the hash table, you should have the following instance variable: public String type = "general"; //"general\" by default, could also be "Specific" This string type may be useful when it comes to showing the user your completed hash table. We want to be able to easily switch between hash functions without having to manually change code. To keep things simple, and since our purpose here is to develop good hash functions, the only public methods required for your HashTable class are: //adds item to the hash table (uses 'type' instance variable to determine which hash function to call) public void addCT item) public void add(T item) //displays the hash table along with stats about the hash public void displayC) //main method. detailed below public static void main() You are free to write the constructor however you see t (you will likely need to pass in an int for the size of the hash table and a String for its type). You Will also write a main() method to run your general and specic case hash. You can add your own helper methods if you feel the need. Note: Your initial hash function(s) can be simplesuch as using the rst letter of each token. 2 Reading Tokens To make testing of your hash table quick and simple, it is best to start with a way to easily read symbols (or tokens) from a le. The le TextScan. java has been provided for you to use (or modify) in order to read tokens from an arbitrary file. The main() driver method in TextScan. java reads (and displays) all tokens found in the file specified on the command line when running TextScan. Try it on some arbitrary file-for example, itself. You may use the code from TextScan.java in your Hash Table.java and modify it to meet the requirements of this project, but if you do, be sure to properly credit the source within your program and your README. 3 Adding to the Hash Table Now that we have at least one hash function, we can take any item and generate an index for it to be added into the hash table. In this step, you will implement one method: public void add(T item) This method adds a given item to the hash table using one of your hash functions. It does not add duplicate items. You are required to use chaining (as described on page 4) to handle collisions. Note: The public void addWordsFromFile (String fileName) method has already been written for you. This method uses the add(T item) method. Once you implement that, the given method can be used to add all words from a file to the hash table. You do not need to change this method. By default, IntelliJ will look for text files outside the src folder, so be sure that your .txt files are located in the project directory but outside of src.4 A General Hash Table In this section, you will implement a better hash function to handle the \" general case\" (when the data being added to the hash table is unknown or extremely large in size). We suggest some creativity try a few different hash functions to see how they compare and then choose one that seems to provide the most even distribution of collided keys. We also suggest keeping your various hash function attempts so that it is easy to compare them on different data sets. For example: 0 private int hash1(T key) 0 private int hash2(T key) 0 private int hash3(T key) Sample les have been provided for you to test your hash table and hash functions (see proverbstxt, canterbury.txt, gettysburg.txt, and that bad.txt). You may also use les of your own. Note that the hash table does not always need to grow to handle larger files, but the hash function should distribute the collided values evenly across even a small hash table. You are NOT expected to create a perfect hash function. However, the goal is to experiment a little to find a hash function that works at least as well as (and hopefully better than) the initial attempt. This hash function is what will be called when adding into the hash table when type is "general". IMPORTANT: For a good hash function, the longest collision length should be