Java代写:CSE12 Hash Table

代写数据结构中的Hash Table, 并通过自动测试。

Hash Table

Learning goals

  • Compare the efficiency of HashTable to Array and LinkedList
  • Use Java’s HashSet and HashMap to solve real-world problems
  • Write JUnit tests to verify proper implementation

Important: You won’t need to implement any hashing algorithms / data structures in this PA. Instead, you’ll need to use Java’s built-in HashSet and HashMap to complete this PA.


There are 4 parts to this assignment. All are required before the deadline and should be submitted on Gradescope:

  • Part 1: Runtime Stimulation
  • Part 2: Coding and Testing
    • HashSet and HashMap Application
    • Testing
    • Coding Style
  • Part 3: Conceptual Quiz
  • Part 4: PA Reflection

Each part corresponds to its own Canvas “assignment” where your grade on that part will be recorded. Please complete all the parts individually; pair programming is not allowed for this PA. More information on submission is given in the Submission Instructions section.

Part 1: Runtime Stimulation

You are given 3 mystery data structures, which are implemented in MysteryClassA, MysteryClassB, and MysteryClassC. Your goal is to analyze the runtimes of their operations in order to help you classify the type of data structure each class has implemented. You will do this using the following steps (more information for each is given below):

  1. Connect to ieng6 and then run and time the methods below on different input sizes.
  2. Copy your timing information into a spreadsheet that will graph your results.
  3. Based on these graphs and your knowledge of Big-O running time of different operations for different data structures, answer questions on gradescope about what data structure each class implements.

Each class has an add method, a find method, and a remove method. Here is the set of operations you will be given.

Data Structure add find remove
ArrayList Add the element to the beginning of the list (index 0). Find the given element. Remove the first element.
LinkedList Add the element to the beginning of the list (index 0). Find the given element. Remove the first element.
HashTable Add the element according to hashing rules. Find the given element. Remove the given element.

Connecting to Your ieng6 Account

The mystery classes are provided as a jar file on ieng6, called simulatior.jar. Look up your course-specific account for CSE 12 here. Your CSE 12 account is different from your CSE 15L account, and it should start with cs12wi22. Then you can connect to ieng6 using ssh. Your command will look like this, but with the zz replaced by the letters in your course-specific account.

Note: Since CSE 15L is a co-requisite of CSE 12, we do expect you to be familiar with working in a Linux machine over SSH. If you don’t know how to do so, please refer to CSE 15L Week 1 Manual. Additionally, you may go to the CSE basement labs to complete this assignment.

Running the Simulation

Use the following line in your terminal in order to run the simulation. You’ll need to provide 5 command line arguments, as specified below.

$ java -jar ../public/bin/simulatior.jar --data-structure [ds] --size [size] --operation [operation] --iteration [iteration] --round [round]
  • –data-structure
    • Select A, B, or C for the version of the method corresponding to MysteryClassA, MysteryClassB, or MysteryClassC.
  • –size
    • This represents the number of elements the data structure has.
  • –operation
    • Select add, find, or remove to run the corresponding method.
  • –iteration
    • This represents the number of times the given operation is run in one trial.
  • –round
    • The number of trials represents the number of times the operation is tested and timed. An average time across all the trials will be reported at the end.


$ java -jar ../public/bin/simulator.jar --data-structure A --size 40000 --operation remove --iteration 500 --round 2

The above command runs MysteryClassA’s remove method and the object has 40000 elements. Each trial calls remove for 500 iterations with randomized arguments, which is then repeated for 2 rounds.

The following is an example of the expected output from running the above command. Your reported time values may vary within a reasonable range.

Warmup rounds (will be ignored in the average)...
    Total time (for 500 operations): 360.2340 us.
    Average (for a single operation): 0.7205 us.
    Total time (for 500 operations): 247.2960 us.
    Average (for a single operation): 0.4946 us.
Round #1 (out of 2)
    Total time (for 500 operations): 210.7010 us.
    Average (for a single operation): 0.4214 us.
Round #2 (out of 2)
    Total time (for 500 operations): 196.7730 us.
    Average (for a single operation): 0.3935 us.
Average (for a single operation over 2 rounds): 0.4075 us (this is what you need for the next section: Collecting Data)

Collecting Data

You will be required to run the simulation for all the mystery data structures A, B, and C, with size of 10000, 20000, 30000, and 40000, calling all the operations add, find, and remove, for 1000 iterations and 5 rounds. (So there are 36 different combinations of simulation in total). Record the average runtime each time and plot the data using a Google spreadsheet template.

Make your own copy of the template in order to enter your data values (“File” > “Make a copy”). Enter your data in the appropriate cells that are colored yellow, and the plots will automatically update. You should enter the average time reported from your 5 trials in microseconds (us) for your data. You should not edit any other part of the spreadsheet. Then upload a PDF (“File” > “Download” > “PDF”) of your sheet in Q2 Collecting Data section on Gradescope.

Identifying the Mystery Classes

In the Gradescope assignment for part 1, categorize each Mystery Class as either a HashTable, ArrayList, or LinkedList. For each choice, you are required to analyze its big-O runtime behavior and justify your answer based upon the data you collected from the simulation.

Part 2: Coding and Testing [7 points] (individual)

In this part of the assignment, you will directly use Java’s built-in data structures and write JUnit tests to ensure that you call the functions correctly.

Make sure to read the entire write-up before you start coding. you may not change any public class/method or variable names given in the write-up or starter code.

Download the starter code from here and put it in a directory in your working environment.

Part 2a: HashSet Application

It’s time to register for classes again, and we need to organize the students and courses during the enrollment period.

You will be using a HashSet to help you track course enrollment. Refer to the Java documentation for more information on HashSet. You are allowed to use any of the methods listed in the documentation for Java’s HashSet directly.


You will first complete the methods to implement the Student class. Student objects will be stored in Course objects.

All variables should be declared as private final. Think about what will happen to the hash code if you allow those elements to be changed after initialization.

Instance Variable Description
String firstName A string representing the first name of the student.
String lastName A string representing the last name of the student.
String PID A string representing the PID of the student.

This is unique for each student.|

You will be required to implement the following methods.

Method Name Description
public Student(String firstName, String lastName, String PID) Initialize the student’s information
public String getFirstName() Return the student’s first name
public String getLastName() Return the student’s last name
public String getPID() Return the student’s PID
public boolean equals(Object o) Returns true if o is also a non-null Student and all the instance variables of o equal the instance variable of the current Student object. Otherwise, return false.
public int hashCode() Return the hash value generated by Object’s hash function. The hash function should generate a hash value in the order of the student’s firstName, lastName, and PID. See an example here.
public int compareTo(Student o) Returns 0 if all the instance variables are equivalent. Returns a negative value if the current object lexicographically comes before Student o. Returns a positive value if the current object lexicographically comes after Student o. The order of precedence for instance variables is lastName, firstName, and PID. You should use .compareTo to compare those strings. Do not implement any char-wise comparison logic.


Our Course class will help us store the students registered for this particular course in the form of a HashSet.

All variables should be declared as private final except for enrolled.

Instance Variable Description
HashSet enrolled This is a collection of students that are enrolled in this course.
int capacity This is the maximum number of students that can be enrolled in this course.
String department This course falls under this department.
String number This is the course number.
String description This is the description of the course.

Part 2b: HashMap Application

A wildlife sanctuary needs your help to efficiently track the animals that are in its care! The sanctuary wants to keep track of how many of each species are currently located on its grounds.

You will be using a HashMap to help you organize all the animals at the sanctuary. Refer to the Java documentation for more information on HashMap. You are allowed to use any of the methods listed in the documentation for Java’s HashMap directly.

Instance Variable Description
HashMap sanctuary Container to store all the animal species in the sanctuary. The String represents the name of the animal species and the Integer represents the number of that species at the sanctuary. If String is null or Integer equals to 0, the species should not be in the sanctuary HashMap.
int maxAnimals The maximum number of animals that the sanctuary can support.
int maxSpecies The maximum number of species that the sanctuary can support.

Part 2c: Testing

We provide two test files:

    • Contains all the public test cases we will use to grade your HashSet and HashMap application (visible on Gradescope).
    • This file contains 10 generic method headers. You will edit this file. Points will be deducted if method header descriptions are not completed.

Your task in this part is to implement the tests that are stubbed out in the custom testers. Here are the rules for how you must follow:

  • Your tests must test the method they are named for, but they may test any aspect of that method’s behavior that is not already covered by a test in the public tester. Points are awarded only if your test cases cover cases that the public tester file does not take into account.
  • There is no restriction on what error message you use as your string input.
  • You MUST NOT copy code from the public tester file.
  • You may add additional test methods, but you are not required to do so.
  • Make sure all the test cases in the custom tester file pass. Otherwise, you would receive 0 points for the test case that fails.

The table below gives the list of public tests that we will run against your solution. We will also test your code on additional hidden tests, but we will not tell you what the hidden tests will do. Note that some methods are not tested in the public tester, but will be tested using the hidden tests. It is your responsibility to write your tests to thoroughly test your code, including all edge cases.

How to compile and run the public tester

on UNIX based systems (including macOS):

$ javac -cp libs/junit-4.12.jar:libs/hamcrest-core-1.3.jar:.
$ java -cp libs/junit-4.12.jar:libs/ PublicTester

on Windows systems:

$ javac -cp ".;libs\junit-4.12.jar;libs\hamcrest-core-1.3.jar"
$ java -cp ".;libs\junit-4.12.jar;libs\hamcrest-core-1.3.jar" org.junit.runner.JUnitCore PublicTester
Student Test Cases Public Cases
constructor Valid argument constructor
equals Evaluate equivalent Student objects
hash check if the hash is deterministic
Course Test Cases Public Cases
constructor Valid argument constructor
enroll Enroll a new non-null student
unenroll Unenroll an existing student
isFull check a full roster
toString Get a descriptive string from a normal course
Sanctuary Test Cases Public Cases
constructor Valid argument constructor
getNum Get the number of animals of a species at the sanctuary
getTotalAnimals Get the total number of animals at the sanctuary with one species
getTotalSpecies get total number of species at a sanctuary with some species
rescue Add a new species of animals to not-full sanctuary
release Remove some animals from the sanctuary

Part 3: Conceptual Quiz

You are required to complete the Conceptual Quiz on Gradescope. There is no time limit on the Quiz but you must submit the Quiz by the PA deadline. You can submit multiple times before the deadline. Your latest submission will be graded.

Part 4: PA Reflection

Complete the PA5 reflection. There is an automatic 36-hour grace period for this part.