Your task for this program is to fill up a Table with some sample data using hash techniques and count the number of collisions that happen when placing the elements in the table.$$ You will report the average number of collisions that happened in placing all the elements and show a listing of numbers of collisions for each attempted placing in the table.$$ See a sample output at end of project description.

$$

You will then repeat this process using a different Table class that uses Double Hashing techniques.$$ And a Third using Chain Hashing.$$ You will report the averages of each and output a table of collisions. See sample output on end of this document.

$$

Values to input$-$

You will be given an input file which contains $200$ names and $9-$digit numbers.$$ The names will be your elements and the numbers will be your keys $.$

$$

Summary of program:

Your program will start by reading each line in the file and placing the names into the table based on the key given.$$ The table will be created from the given Table class $($which you will be able to alter$).$ As prime numbers work the best for hashing, and we want to force a fair number of collisions, you should use a table size of $241.[$This will cause the finished table to be over $82\%$ full.$$ And because $239$ is also a prime, we will be set up well to use double hashing.$]$ As you place each element, you will need to keep track of how many times you attempted to place the element in a spot that was already used.$$ Each of these is a collision.$($I am not interested in how many collisions each location of the array is having, just the number of collisions per element placed into the table.$)$ Repeat$($or process at the same time$)$ the test for double hashing and for chain hashing.$$ Then report the results for all three tests in a table $($see output example$).$ With the same hash function and input, we should all get the same results.$$

$$

Note:$$ The Table class is already completed for you to use linear hashing without any changes, however you will still need to alter the Table class with just enough code to be able to count and report back on the number of collisions for each time you place an element. You are not allowed to alter the class in a way that no longer makes it a generic class.$$

$$

You will need to create additional versions of the Table class, one with alterations to place data using a double hashing method and the other using a chain hashing method.$$ Call these classes TableDoubleHash and TableChainHash.$$ These classes will have almost all of the same code as the original Table, but you will add just enough alterations on how to handle the collisions for double hashing or chain hashing.$$

$$

Chain hashing means you will need to make some changes on how data is stored within the table as well. $$But it turns out that it is not a lot of difficult updates.$$ Note: You do not need to create a new Node class $($ChainedHashNode$)$ as discussed in the textbook.$$ Instead $$ you will search for the proper location in the array as in linear hashing, and then when you are ready to put in the new element at an index, you will add a new Node $($that contains the element data$)$ to the spot in the array.$$ Remember that with chained hashing the main array will be storing a linked list at each location.$($also the keys will be stored this way in a separate array$)$ It may sound confusing, but there is really not a lot of extra coding.$$

Note: All the methods that exist in the original Table class should work in your altered versions.$$ So$,$ make sure to update all of them, even if you don$$t need all of them to get the output.$($get and remove methods are a couple of examples$)$What classes that you need to hand in:

$$ Table $($template given$)$

$$ TableDoubleHash $($table with a bunch of changes$)$

$$ TableChainHash $($for chain hashing, uses Node class$)$

$$ Node $($unaltered as given$)$

$$ HashTesting$-$ main driver of program.

The sample data file given is called names.txt and will be used as a starting point to test your program.$$ A copy of this file is given in with these program directions.$.$The input file used is data stored in text format $($not binary, so that we can read it$)$ with one name and $9-$digit number on each line and spaces between fields.$$ It is organized like this:

Name$9$DigitNumber

Node class is given and the only pre$-$built class allowed to use and What will the output of this code look like and the other files?

$2$ public class Table$$ K $,$ E $>$

private int nextIndex$($int i$)$

else

return i$+1$;

$\}$

public E put$($K key, E element$)$

$\{$

int index $=$ findIndex$($key$)$;

E answer;

if $($index $!=-1)$

$\{//$ The key is already in the table.

answer $=($E$)$ data$[$index$]$;

data$[$index$]=$ element;

return answer;

$\}$

else if $($manyItems $$ data.length$)$

$\{//$ The key is not yet in this Table.

index $=$ hash$($key$)$;

while $($keys$[$index$]!=$ null$)$

index