Homework 6

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

This Homework Is Due By 11:59 PM on Sunday April 10, 2022

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.

You will also be using the TestTimes class with the expanded functionality from Homework 4 .

Finally, you will be analyzing the performance of the test cases.

Details

1. TestTimes zyLab

   You will copy the TestTimes class that you enhanced with added functionality in Homework 4 to the project you are using for this assignment. This TestTimes class implements the expanded TestTimes Interface . Please note that you will also have to re-submit TestTimes.java to zyBooks in the TestTimes zyLab.

2. LinkedList zyLab

   You will create a new LinkedList.java class to implement the modified List Interface. This interface provides the functionality needed to handle collision chaining. You will also be using the KeyedElement Interface . Both of these interfaces may be downloaded from here .

3. HashTable zyLab

   You will create the HashTable.java class to implement the HashTable Interface. You will also be using the KeyedElement Interface . Both of these interfaces may be downloaded from here .

   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. Your constructor must also verify that the buckets array is fully populated with instances of LinkedList<E, K>. If either of these conditions are violated, your constructor must throw an InstantiationException. Otherwise, your constructor will initialize the buckets instance variable as follows:
   
   this.buckets = buckets.clone();
   

4. Node zyLab

   You will write the Node class. Please see the Node Documentation for all the methods you will need.

   Please note that this Node class is similar to the LinkedListNode class that you created in Homework 3 .

5. ElementIterator zyLab

   You will write the ElementIterator.java class which will implement the Iterator Interface.

   Please note, you only need to implement two methods from the Iterator interface: boolean hasNext() and E next()

6. HashTableDriver zyLab

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

   Please note that, in addition to implementing the HashTableDriverInterface, you are also required to write your own public static main(String[] args) method in QueueDriver.java that performs all of the required tests as specified below.

Other Interfaces & Classes

1. 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 here .

2. 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 here .

   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.

Required Tests

Definitions:

You will test your hash table implementation with different tests. The HashTableDriverInterface includes the definitions of one enum:

1. HashTableDriverInterface.TestType

   All the elements being added and removed from the hash table must be instances of the Person<Integer> class.

   This enum defines all the tests that you will be performing. The tests are:

   HashTableDriverInterface.TestType.Insert:

   1. Initialization: Create an empty Hash Table.
   2. Test: You will use the insert(E element) method to insert 100,000 Person objects into the Hash Table.

   HashTableDriverInterface.TestType.Get:

   1. Initialization: Create a HashTable and populate it with 100,000 Person objects.
   2. Test: You will use the get(K key) method to get all the Person objects that were inserted in the initialization

   HashTableDriverInterface.TestType.Remove:

   1. Initialization: Create a HashTable and populate it with 100,000 Person objects.
   2. Test: You will use the remove(K key) method to remove all the Person objects that were inserted in the initialization

Output From Driver Main Method

Please note that, in addition to implementing the HashTableDriverInterface, you are also required to write your own public static main(String[] args) method in HashTableDriver.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 print out a table with the following output:

HashTable Test Times
                   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

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

Please note that the test times and the average are in Micro Seconds and the memory usage is in Kilo Bytes. You will need to make the necessary conversions.

Sample Output

HashTable Test Times
                   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      147412.163 109321.515 150656.446 127454.879  142102.601 143695.866  39020.151 180177.187 160097.307 140867.829 144080.594
       Get      121140.859  99914.242 111248.186 122266.586  133324.626 120699.428 148970.956 124963.425  92647.732 111142.347 118631.839
    Remove        5563.699   4129.869   3932.407   3889.457   13861.585   3675.092   3178.376   3120.072   3191.084   3252.138   4779.378

HashTable Memory Usages
                   Run 1      Run 2      Run 3      Run 4      Run 5      Run 6      Run 7      Run 8      Run 9      Run 10     Average
                   Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo 
                   Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes 
                ---------- ---------- ---------- ---------- ----------- ---------- ---------- ---------- ---------- ----------  ----------
    Insert       29226.898  42334.367  55441.820  55481.352   69755.172  82731.359  95707.563 109981.383 113728.070 126750.000   78113.798
       Get      197459.148  80813.031 127799.492 175176.625  181088.227 228422.422 275756.578 323090.766 287665.680 334552.461  221182.443
    Remove      407487.414 443954.891 480422.359 516889.820  449378.289 487140.703 524903.141 557270.922 595037.500 632799.922  509528.496
  

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);
      

Analysis:

Using the tables you created by running QueueDriver.main(), copy your results and your graphs into a Microsoft Word document and answer the following questions using 1-3 complete sentences for each question:

1. Create graphs from the test times you measured.
2. Discuss the difference in test times between the different test cases. Explain the reason(s) why the test times are different between the test cases. Did the results match your expectations? Why or why not? Be as specific as possible.
3. Discuss the difference in memory usage between the different test case. Explain the reason(s) why the memory usage are different between the implementations. Did the results match your expectations? Why or why not? Be as specific as possible.

Please submit the completed assignment in your zyBooks , in the Homework 6 Chapter.

Please submit your analysis on Blackboard as a typed Microsoft Word file (.docx). No other forms of submission will be accepted. Please include your graphs in the same file as your analysis.