Hash Table Project

For this project, you must implement a hash table with chaining that uses arrays to store the chains rather than linked lists. This is not necessarily a sensible approach, but it is included to test your ability to manipulate array based data structures. You must implement the hash table with arrays, not with the ArrayList class. You can include class variables and methods not specified. You may, if you wish, adapt the abstract class, but please keep the methods that are already in there. Please note I do not want you to implement rehashing for this hash table. The capacity should remain constant.

1.Basic structure and constructor.

Implement a class ArrayHashTable that extends the abstract class HashTable and uses chaining. The data should be stored in a two dimensional array called table. In addition to the inherited variables, the class should have an integer variable chainSize (the initial size of each array to store the chain, default to 5). These variables should be updated when items are added or removed from the table. The default capacity should be 10 and the constructor should initialise table to an array of arrays size capacity, with each value set to null.

table=new Object[capacity][];

the number of elements at each location of the hash table should be stored in an array of integers called counts, all initialised to zero.

2.Implement the method add.

Use the method hashCode to find the hash value for the location in the hash table. If the entry is empty (e.g. if the hash value is 5 and table[5] == null), create a new array of size chainSize. If the entry is not empty, insert the item at the correct location, if it is not already present. If this means the current array is now full, double the size of the current array and copy over the values. This method should return true if the item is added to the table, false if not (i.e. if it is already present).

3.Implement the method contains.

This should be simple once you have implemented add.

4.Implement the method remove.

Use the method hashCode to find the hash value for the location in the hash table. If the entry is empty, or the array for that entry does not include the object passed, return false. Otherwise, remove the item, adjusting the hash table variables and remaining hash table objects accordingly.

5.Design an experiment to test the run time of your hash table and of the Java class HashSet for inserting n randomly generated Integer objects into a hash table with initial capacity 10, then removing the same n integers. Use n =< 1000, 2000, . . . , 10000, 15000, 20000, 25000, . . . , 50000 >, although you can reduce the maximum if it is too slow to run. You can generate an array of numbers to add then remove with the following code (or use your own technique).

int[] numbers=new int[n];
Random r=new Random();
for(int j=0;jnumbers[j]=Math.abs(r.nextInt());
}

Using Microsoft Excel or otherwise, plot a graph of these results and explain what the graph demonstrates and why there are observed differences.