Homework 5

CMP 338: Data Structures & Algorithms
Lehman College, City University of New York
Spring 2021

This Homework Is Due By 11:59 PM on Tuesday April 20, 2021

Overview

In this assignment you will developing a HashTable that handles collisions using chaining.

To provide the necessary collision chaining, you will be modifying your implementation of LinkedList from Homework 3   to provide the necessary funtionality.

Details

1. TestTimes Class

   You will copy TestTimes.java and the TestTimesInterface,java from Homework 4 to the project you are using for this assignment.

2. LinkedList Class

   You will create a new LinkedList.java class to implement the modified List Interface. This interface provides the functionality needed to handle collision chaining. The interface may be downloaded from ListInterface.java.

3. LinkedlistNode Class

   Your will write the LinkedListNode class. Please see the Linked List Node Documentation for all the methods you will need.

4. HashTable Class

   You will create the HashTable.java class to implement the HashTable Interface. The interface may be downloaded from HashTableInterface.java.

   Your HashTable class must have the following definitions:

   public static final int NUMBER_OF_BUCKETS = 1_069;

   You may choose a different constant, but make sure that it is a prime number greater that 1,000.

   
   

   private LinkedList<E, K>[] buckets;

   See the Hints section below on how to initialize this instance variable.

   
   

   private int size = 0;

   An int coresponding to the number of elements in the HashTable, initially set to 0.

   
   

   In addition, Your HashTable class must have the following constructor:

   public HashTable(LinkedList<E, K>[] buckets) throws InstantiationException

   The constructor will have to verify that the array being passed into the constructor is of the correct size by making sure it has NUMBER_OF_BUCKETS. If not, your constructor must throw an InstantiationException. If the size is correct, your constructor will do:
   
   this.buckets = buckets.clone();
   

5. KeyedElement Interface

   This is the interface that all elements to be inserted into a hash table or a list must implement. The Person class implements this interface. The interface may be downloaded from KeyedElementInterface.java.

6. Person Class

   You will use the provided Person.java class as the element that will be inserted into our HashTable. The class may be downloaded from Peson.java.

   For this assignment, the Key type will be Integer, so you will be creating instances of the Person class as follows:
   
   Person<Integer> person = new Person(new Integer(x));
   
   Where x is a unique int for each Person instance.

7. Driver Class

   You will write the Driver.java class which will implement the Driver Interface. The interface may be downloaded from DriverInterface.java.

8. Test Cases

   You will be creating 100,000 instances of the Person<Integer> class for insertion into the HashTable<Person<Integer>, Integer>. Save all your generated Person<Integer> objects in a Vector<Person<Integer>>. Your test cases will be:

   1. Create an empty HashTable<Person<Integer>, Integer> and insert all the Person objects into your HashTable.
   
   
   2. Create a fully populated HashTable<Person<Integer>, Integer> with all 100,000 Person<Integer> objects and use the get method to find all the Person objects in your HashTable.
   
   
   3. Create a fully populated HashTable<Person<Integer>, Integer> with all 100,000 Person<Integer> objects and use the remove method to remove all the Person objects from your HashTable one at a time.

9. Output From Driver Main Method

   Please note that, in addition to implementing the DriverInterface, you are also required to write your own public static main(String[] args) method in Driver.java.

   Your main() method will have to call the runTestCase() method for each of test cases listed above a total of ten times for each test case:

   For each call to the runTestCase() method your main() method will output a table with the following output:

   	 Run 1   Run 2   Run 3   Run 4   Run 5   Run 6   Run 7   Run 8   Run 9  Run 10 Average
            Micro   Micro   Micro   Micro   Micro   Micro   Micro   Micro   Micro   Micro   Micro
   	Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds
   	------- -------	------- -------	------- -------	------- -------	------- -------	-------
   Insert
   Get
   Remove
   	

   	   Run 1      Run 2      Run 3      Run 4      Run 5      Run 6      Run 7      Run 8      Run 9     Run 10     Average
   	Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes
   	---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
   Insert
   Get
   Remove
   	

   Please note that the test times are in Micro Seconds and the memory usages are in Kilo Bytes.

Hints

1. HashTable & Driver

   1. Your Driver will create an Array for LinkedList<Person<Integer>, Integer> objects (See the Person class below) like this:
      
      LinkedList<Person<Integer>, Integer>[] myBuckets = new LinkedList[HashTable.NUMBER_OF_BUCKETS];
      
   
   
   2. You will then have to populate this new array with LinkedList<Person<Integer>, Integer> objects that you create.
      
   
   
   3. Your Driver will then instantiate the HashTable as follows:
      
      HashTable<Person<Integer>, Integer> hashTable = new HashTable<Person<Integer>, Integer>(myBuckets);
      

Please submit the completed assignment on the Mimir Platform Website .

You must submit your .java files as a zip file of only the classes and interfaces specified above.