Description: In this lab you will implement a hash table with linear probing and perform simulations to observe its performance. The hash table will store integers. The hash function to be used is h(x) = x%M (the remainder after dividing x by M), where M is the size of the hash table. The set of possible keys x is the set of positive integers representable by the int data type. You must write a Java class HashTableLin and a class TestHashTable for testing and for measuring its performance.

Specifications:

Class HashTableLin must contain a field named table, of type Integer[], which is a reference to the array which stores the keys. There must be other fields to store the size of the table, the number of keys stored in the table and the maximum load factor allowed. All fields must be private. Pay attention to update these fields when performing hash table operations (when necessary).

Class HashTableLin must contain at least the following constructor

public HashTableLin(int maxNum, double load) - creates a HashTableLin object representing an empty hash table with maximum allowed load factor equal to load. The amount of memory allocated for the hash table should be large enough so that maxNum keys could be stored without its load factor exceeding the value of parameter load. The size of the table should be the smallest prime number such that the above requirement to be met. For instance, if maxNum=5 and load=0.4, then the size of the table should be at least 5/0.4 = 12.5. The smallest prime number satisfying the requirement is 13.

Class HashTableLin must contain at least the following public methods:

1) public void insert(int n): Inserts the key n in this hash table if the key is not already there. If the insertion will cause the load factor to exceed the maximum limit prescribed for this table, then rehashing should be performed by invoking the method rehash().

2) private void rehash(): Allocates a bigger table of size equal to the smallest prime number at least twice larger than the old size. Then all keys from the old table are hashed into the bigger table with the appropriate hash function and with linear probing.

3) public boolean isIn(int n): Returns true if key n is in this hash table. It returns false otherwise.

4) public void printKeys(): Prints all keys stored in this table, in no particular order.

4) public void printKeysAndIndexes(): Prints all keys stored in this table and the array index were each key is stored, in increasing order of array indexes. The purpose of this method is mainly to be invoked in your test class for verifying that insertions are correct.

6) Accessor public methods (get methods) to allow the user to see the values of the fields relevant to the table (max load factor, number of keys, etc.)

The test class has to be designed to carefully check that all specifications are met. For instance, you need to verify, among other things, that rehashing is performed when needed, that the size of the table is a prime number and it is selected as specified, that no duplicates appear in the table, etc. During testing instructive messages should be printed to clarify what is tested (i.e., your method performing the tests should print such messages). You may write additional methods in your HashTableLin class to aid in testing, if necessary.

Additionally, the test class must contain a static method to perform simulations to measure the average number of probes for successful search. For each (0, 1), S denotes the average number of probes for successful search in a table with load factor and size approaching . Note that the number of probes to find a key which is in the table is the same as the number of probes performed when the key was inserted. Thus the average number of probes for a successful search in a particular table can be determined by computing the average number of probes needed when the elements were inserted (by adding all numbers of probes and dividing by the number of elements in the table).

You need to perform this measurement for load factors = 0.1, 0.2, , 0.9, and output the results. For each load factor allocate a hash table, insert at least 100, 000 randomly generated numbers and compute the average number of probes needed. Repeat the test 100 times for a good average (i.e., have a loop with 100 iterations and then average again over all iterations). In order to perform the test ensure that the initial hash table size is large enough so that no rehashing is needed, and after all 100, 000 keys are inserted the load factor is the required (to do this, when creating the test object pass the number of tests, i.e., 100, 000, and to the constructor). Note that the random number generator may create duplicates, and duplicates should not be inserted, so make sure that you properly count the number of inserted keys.

In order to count the number of probes performed during an insertion (i.e., the number of table slots that are examined, including the one where the key is inserted), write another public method in class HashTableLin called public int insert(int n) which inserts and returns the number of probes required. The method which performs the measurements should also output the theoretical values of S for linear probing, for comparison. Note that the theoretical values are given by S = 1 /2 ( 1 + 1 /(1 )) .