The goal of this project is to explore the insertion performance of a hash table, using linear probing. You will produce a data set that shows the average displacement for the entire data set of size N when it is placed in a hash table of size M for various value of the ratio N/M. (this project is to be done in Java).

1. First, implement the hash table class described in the text book.

2. Next, write a test method (you can use the main() method of your HashTable class) that adds values to the hash table. You can generate random integers, or read words from a file, or anything convenient for you (I generated random numbers using StdRandom.uniform(1000000)). Each time a value is added, you will need to measure and record the displacement (how far each entry had to be shifted from its natural position, due to collision).

3. Generate a data set consisting of the average displacement across the whole data set (all N keys). Actually, you will need to do this a number of times.

4. Run step 3 for a variety of values of N for a given M.

5. Produce a graph: the X values are the different ratios of N/M, and the Y values are the average displacement across a number of data sets. The completeness and accuracy of your graph will be a significant part of your grade (3 or 4 data points won't cut it).