Description
Overview: For this project, you will be implementing a hash table, testing its functionality with black-box JUnit tests, and writing a small program to analyze the performance of your hash table against Java’s builtin TreeMap. TreeMap (https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/TreeMap.html) is a known and inbuilt data structure of Java. To analyze the performance, you need to write a small program that performs the same operations on both your custom HashTable class and Java’s TreeMap class. You will be using a program profile class, and Java Mission Control to analyze the profile information. For this assignment, you are required to: 1. implement a generic HashTable class 2. implement HashTableTest class to test the generic HashTable class 3. test the performance of HashTable by 1. writing MyProfiler.java, a program that will be profiled to compare your HashTable and Java’s TreeMap 2. running your program MyProfiler to generate the jfr file 3. using Oracle Java Mission Control (https://canvas.wisc.edu/courses/202692/pages/oraclejava-mission-control) (jmc) to analyze the generated my_profile.jfr data 4. answering the questions in conclusions.txt (https://canvas.wisc.edu/courses/202692/files/13057031/download?wrap=1) (https://canvas.wisc.edu/courses/202692/files/13057031/download?wrap=1) file 5. taking screenshots of the relevant parts of your profile data as viewed from Java Mission Control All files must be named correctly (case-sensitive). You may define and submit other package-level (not public) classes as needed and you may add and edit any private members to your classes. The goal for your HashTable is to build a searchable data structure that achieves constant time O(1) for lookup, insert, and delete operations. 2020/12/2 p4 Hash Table: COMPSCI400: Programming III (002) DHH SU20 https://canvas.wisc.edu/courses/202692/pages/p4-hash-table 2/6 Duplicate keys are allowed. If key is already in the HashTable, replace associated value with the new value. Use what you have learned about writing tests and the JUnit testing framework to ensure that your hash table implementation works correctly prior to analyzing its performance. Files Note: updates to these files are possible, and will be posted in announcements on this page. In the p4.zip (https://canvas.wisc.edu/courses/202692/files/13057041/download?wrap=1) file: conclusions.txt (https://canvas.wisc.edu/courses/202692/files/13057031/download?wrap=1) (https://canvas.wisc.edu/courses/202692/files/13057031/download?wrap=1) (do answer the questions after profiling and analyzing, do SUBMIT) DataStructureADT.java (https://canvas.wisc.edu/courses/202692/files/13057032/download?wrap=1) (https://canvas.wisc.edu/courses/202692/files/13057032/download?wrap=1) (provided interface – do NOT EDIT or SUBMIT) HashTableADT.java (https://canvas.wisc.edu/courses/202692/files/13057034/download?wrap=1) (https://canvas.wisc.edu/courses/202692/files/13057034/download?wrap=1) (provided interface – do NOT EDIT or SUBMIT) HashTableTest.java (https://canvas.wisc.edu/courses/202692/files/13057035/download?wrap=1) (https://canvas.wisc.edu/courses/202692/files/13057035/download?wrap=1) (starter for JUnit test class – write your tests in here and SUBMIT this file) HashTable.java (https://canvas.wisc.edu/courses/202692/files/13057033/download?wrap=1) (https://canvas.wisc.edu/courses/202692/files/13057033/download?wrap=1) (starter class – do EDIT and SUBMIT – define your hash table here) IllegalNullKeyException.java (https://canvas.wisc.edu/courses/202692/files/13057036/download? wrap=1) (https://canvas.wisc.edu/courses/202692/files/13057036/download?wrap=1) (provided class – do NOT EDIT or SUBMIT) junit-platform-console-standalone-1.5.2.jar (https://canvas.wisc.edu/courses/202692/files/13057037/download?wrap=1) (for running JUnit5 tests — do not submit) KeyNotFoundException.java (https://canvas.wisc.edu/courses/202692/files/13057038/download? wrap=1) (https://canvas.wisc.edu/courses/202692/files/13057038/download?wrap=1) (provided class – do NOT EDIT or SUBMIT) MyProfiler.java (https://canvas.wisc.edu/courses/202692/files/13057039/download?wrap=1) (https://canvas.wisc.edu/courses/202692/files/13057039/download?wrap=1) (starter class – do write your own profiling code and do SUBMIT) SampleProfilerApplication.java (https://canvas.wisc.edu/courses/202692/files/13057040/download?wrap=1) 2020/12/2 p4 Hash Table: COMPSCI400: Programming III (002) DHH SU20 https://canvas.wisc.edu/courses/202692/pages/p4-hash-table 3/6 (https://canvas.wisc.edu/courses/202692/files/13057040/download?wrap=1) (provided to help you complete MyProfiler.java – do NOT SUBMIT) Other files you will need to create and submit with your code: screenshot_001.png (screenshot relevant parts of java mission control – DO SUBMIT) screenshot_002.png (screenshot relevant parts of java mission control – DO SUBMIT) Hints: You can create the headers for all unimplemented methods specified in the interface, by clicking ‘add unimplemented methods’ in the suggestion given by eclipse. Also, remember to add appropriate private variables that are necessary for implementing the required methods MyProfiler This is the program that you will profile to determine relative performance between your HashTable and Java’s TreeMap structures. The program must perform a “bunch” of inserts, lookups, and removes to the data structures. Keep in mind, you are trying to figure out which data structure performs best. Because modern computers are so fast, you will likely need to add a lot of items to see enough difference. Given the complexity analysis of different lookups (single item vs range of values) for the two data structures is different, you will also want to experiment with different lookup operations. Consider too how to lookup many individual values, and many different ranges of values from each structure. Be scientific and iterative https://www.sciencebuddies.org/science-fair-projects/science-fair/steps-of-the-scientificmethod (https://www.sciencebuddies.org/science-fair-projects/science-fair/steps-of-the-scientificmethod) 1. Make a hypothesis. 2. Design an experiment (a.k.a. write code, a single test, or set of tests). 3. Run your experiment (code) and record the results. 4. Learn how to interpret your results. 5. Compare your results against your predictions. 6. How well do you understand your data? your results? Can you predict results? 7. Repeat above to collect more data and refine your hypotheses and come to some conclusions. 8. Record your conclusions. 2020/12/2 p4 Hash Table: COMPSCI400: Programming III (002) DHH SU20 https://canvas.wisc.edu/courses/202692/pages/p4-hash-table 4/6 Java Flight Recorder Read Oracle Java Flight Recorder (https://canvas.wisc.edu/courses/202692/pages/oracle-java-flightrecorder) To run the sample profiler (SampleProfileApplication.java), make sure to edit the run configurations of this class in Eclipse as described in Oracle Java Flight Recorder (https://canvas.wisc.edu/courses/202692/pages/oracle-java-flight-recorder) . Java Mission Control Now, you are ready to view and start analyzing the results of your program. Read about and use Oracle Java Mission Control (https://canvas.wisc.edu/courses/202692/pages/oracle-java-missioncontrol) to do this. Specifications Define (code) the HashTableTest class add your own tests in addition to ours to get you started start small get the easy tests and implementation working first Define (code) the HashTable class should be able to instantiate with generic Key, Value pairs must implement operations described in the provided DataStructureADT interface in an efficient way (O(1)). may use any of the following for internal data structure(s) as you like: arrays, ArrayList, LinkedList, a new node type, etc must NOT USE Java’s HashTable, HashMap, or TreeMap types to implement your HashTable (ask if you are not sure) must handle edge or corner cases (first, last, empty, full – must expand) must handle collisions (you can choose how, but must be one of the ways presented in lecture) must handle resizing (we will set the initial capacity “table size” and add enough to cause resizing) must document design choices that you make for hashing and collision resolution in your HashTable implementation (see comments and document there) [Recommended] Try Test-Driven Development (TDD) 1. get all classes to compile (hint: add stubs for unimplemented methods to HashTable class) 2020/12/2 p4 Hash Table: COMPSCI400: Programming III (002) DHH SU20 https://canvas.wisc.edu/courses/202692/pages/p4-hash-table 5/6 2. choose a feature or method of DataStructureADT or HashTableADT to implement in your HashTable class. 3. write a test for it in HashTableTest 4. run the test (from a Linux command line: make junit5 ) 5. see that your test fails as expected 6. add code to your HashTable class to implement the feature so that it passes the test 7. run the test(s) again 8. see that your tests pass as expected 9. repeat steps 1-8 for all required functionality of your class (https://canvas.wisc.edu/courses/202692/pages/professional-source-code) Write the MyProfiler class The MyProfiler class contains methods for inserting and retrieving data from the hashtable and tree map You are required to instantiate MyProfiler class in the main method with the appropriate data type In the insert method, you will need to insert into both the hash table and tree map Similarly in the retrieve method, you need to get from both the hash table and the tree map The profile class takes one argument , you need to insert and retrieve these many numbers of elements from both hash table and tree map Instructions to perform the profiling are provided here: Oracle Java Flight Recorder (https://canvas.wisc.edu/courses/202692/pages/oracle-java-flight-recorder) Instructions to view and analyze results are provided here: Oracle Java Mission Control (https://canvas.wisc.edu/courses/202692/pages/oracle-java-mission-control) Once, you complete the profiling, answer the questions asked in the file: conclusions.txt Focus on the Memory usage and Method profiling options in the drop down for “Java Application” in the left menu of Java mission control. You should be able to determine which classes and then which methods are using the most resources whether that is space (bytes) or CPU cycles (counts). Then, try to answer the questions. You may need to edit your My_Profiler and HashTable classes re-profile to see understand your results better. Consider how changes that you make in your code affects the results. ProTip: Save each jfr file with new names and document your experiments so that you can compare the usage for each configuration or profiler code you try. Based on your figures, you can tell if the time being spent in HashTable.insert is less than, similar to, or greater than the time spent in TreeMap. put. Does that make sense from what you know about HashTables and TreeMap (Red-Black Tree). If so, you should be able to explain why. If it doesn’t make sense, you may wish to investigate that and see if you can improve the performance of your HashTable. (You can not improve the TreeMap). 2020/12/2 p4 Hash Table: COMPSCI400: Programming III (002) DHH SU20 https://canvas.wisc.edu/courses/202692/pages/p4-hash-table 6/6 Generate images to support your conclusions. You can get points for conclusions based on your results even if those results are not consistent with what we should expect when profiling HashTables against TreeMap. To get full credit, you must also pass GradeScope performance tests and have an efficient HashTable. Steps 1. Read the entire assignment. 2. Review the grading rubric. Note: the rubric is subject to some changes. 3. Use Development Environment of your choice (https://canvas.wisc.edu/courses/202692/pages/development-environment-of-your-choice) 4. Create a p4 project folder for your work. 5. Copy the provided source files into your project folder and refresh it. 6. Get the file HashTable.java to compile (add unimplemented methods). 7. Run the SampleProfilerApplication from Eclipse as instructed above 8. Complete MyProfiler.java the code and complete the testing assignment (review Specifications and assignment for more details) Submit your work to: p4 Hash Table (https://canvas.wisc.edu/courses/202692/assignments/833517)