Java代写：CSE12HashTable

代写数据结构中的 Hash Table , 并通过自动测试。
![Hash Table](https://open4tech.com/wp-content/uploads/2019/03/hash-
table-200x133.png)

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.

Overview

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.

Example

$ 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.

Student

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.

Course

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:

• PublicTester.java
  • Contains all the public test cases we will use to grade your HashSet and HashMap application (visible on Gradescope).
• CustomTester.java
  • 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.
• DO NOT CHANGE THE TEST METHOD NAMES OR REMOVE ANY OF THE GIVEN 10 METHODS.
• 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:. PublicTester.java
$ java -cp libs/junit-4.12.jar:libs/hamcrest-core-1.3.jar:.org.junit.runner.JUnitCore PublicTester
on Windows systems:
$ javac -cp “.;libs\junit-4.12.jar;libs\hamcrest-core-1.3.jar” PublicTester.java
$ 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.