辅导案例-CS310-Assignment 2

欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top
Profs Akhter/Russell Assignment 2: Hash Tables CS310 – Spring 2020

1
Assignment 2: Hash Tables
(replacement for P3c & P4a)

DUE: Apr. 19th at 11:59pm
Extra Credit Available for Early Submissions!

Setup
• Download the assignment2.zip and unzip it.
• This will create a folder section-yourGMUUserName-a2.
• Rename the folder replacing section with the 001, 002, 005, etc. based on the lecture section you are in.
• Rename the folder replacing yourGMUUserName with the first part of your GMU email address.
• After renaming, your folder should be named something like: 001-krusselc-a2.
• Complete the readme.txt file (an example file is included: exampleReadmeFile.txt) .

Submission Instructions
• Make a backup copy of your user folder!
• Remove all test files, jar files, class files, etc.
• You should just submit your java files and your readme.txt
• Zip your user folder (not just the files) and name the zip section-username-a2.zip (no other type of
archive) following the same rules for section and username as described above.
o The submitted file should look something like this:
001-krusselc-a2.zip --> 001-krusselc-a2 --> JavaFile1.java
JavaFile2.java
...
• Submit to blackboard. DOWNLOAD AND VERIFY WHAT YOU HAVE UPLOADED THE RIGHT THING.
Submitting the wrong files will result in a 0 on the assignment!

Basic Procedures
You must:
• Have code that compiles with the command: javac *.java in your user directory without errors or warnings.
• Have code that runs with the command: java ThreeTenHashTable1, and java
ThreeTenHashTable2, and java DemoProgram in your user directory.
• Have a style (indentation, good variable names, etc.) -- you must pass the style checker!
• Comment your code well in JavaDoc style -- you must pass the comments checker!

You may:
• Add additional methods and variables to both provided classes, however these methods must be private.

You may NOT:
• Make your program part of a package.
• Add additional public methods or variables.
• Add any additional libraries/packages which require downloading or use any code from the internet.
• Import any additional libraries/packages or add any additional import statements (or use the “fully qualified
name” to get around adding import statements). THERE SHOULD BE NO IMPORTS IN ANY FILES.
• Alter any method/class signatures defined in this document of the template code. Note: “throws” is part of the
method signature in Java, don’t add/remove these.
• Alter provided classes or methods that are complete (e.g. DemoProgram, toString(), etc.).
• Add @SuppressWarnings to any methods unless they are private helper methods for use with a method we
provided which already has an @SuppressWarnings on it.
Profs Akhter/Russell Assignment 2: Hash Tables CS310 – Spring 2020

2
Grading Rubric

No Credit
• Non submitted assignments
• Assignments submitted after 5pm the Monday after the due date
• Non-compiling assignments
• Non-independent work
• Code that violates and restrictions or “you may not” mandates.
• "Hard coded" solutions
• Code that would win an obfuscated code competition with the rest of CS310 students

How will my assignment be graded?
• Automatic Testing (100%): To assess the correctness of programs.
• You CANNOT get points for code that doesn't compile or for submitting just the files given to you.
• Extra credit for early submissions:
o 1% extra credit rewarded for every 24 hours your submission made before the due time
o Up to 5% extra credit will be rewarded
o Your latest submission before the due time will be used for grading and extra credit checking. You
CANNOT choose which one counts.

Automated Testing Rubric
The JUnit tests used for grading will NOT be provided for you (you need to test your own programs!), but the tests will be
based on what has been specified in the project description and the comments in the code templates. A breakdown of the
point allocations is given below:

50 pts ThreeTenHashTable1 – Open Addressing with Linear Probing
50 pts ThreeTenHashTable2 – Separate Chaining
-5pts (“off the top”) Not following the submission format
Note: This is very, very important for these assignments; the graders need to return grades very
fast. If you do not follow the submission format (the same one you’ve been using for P0, P1,
and P2), then they will manually deduct 5pts from your score. No exceptions.
-5 pts (“off the top”) Not passing code style check
-5 pts (“off the top”) Not passing JavaDoc style check

"Off the top" points (i.e. items that will lose you points rather than earn you points).

Assignment Overview
You will be creating two different types of hash maps (hash tables that “map” unique keys to values). One map
(ThreeTenHashTable1) will use open addressing with linear probing and the other (ThreeTenHashTable2) will use
separate chaining. Both maps will do the same things (i.e. they will have the same operations, such as put(), get(),
rehash(), etc.), but they will do them in different ways (probing vs chaining).

The storage (storage) for each has been setup for you and you cannot change this. For open addressing, the storage is
TableEntry[] while for separate chaining the storage is Node[]. The TableEntry class is defined in
TableEntry.java (it’s a simple key-value pair class) and the Node class (which uses the TableEntry class) is
defined in ThreeTenHashTable2.

DO NOT TRY TO “BLIND CODE” THIS PROJECT! You need to understand exactly the storage you have and how
to use it, if you do this, the project should be very straight forward, but otherwise this will be a very, very difficult.
Profs Akhter/Russell Assignment 2: Hash Tables CS310 – Spring 2020

3
Tasks Breakdown and Sample Schedule
There are 2 tasks in this assignment. It is suggested that you implement these tasks in the given order:
• Task 1: Write a hash table using open addressing with linear probing (50%)
• Task 2: Write a hash table using separate chaining (50%)

Need a schedule?

• You've got 1.5 weeks.
• There are 15 methods to write.
• You have other classes with exams/projects.
• Assume you want to spend the last half week getting EC or seeking additional help.
• Keeping those things in mind, fill in the following:

o 4/06-4/09: ________________________________________ (first week period)
 Suggestions: Finish zyBooks and textbook readings about hash tables, start designing.

o 4/10-4/12: ________________________________________ (first weekend period)
 Suggestions: Tasks 1 and 2 (implement using your design from earlier)

o 4/13-4/16: ________________________________________ (second week period)
 Suggestions: Thorough Testing and Debugging

o 4/17-4/19: ________________________________________ (second weekend period)
 Suggestions: Turn in early for Extra Credit

Examples for Testing
There are 11 “yays” in the main methods of both class tables, but we have also created a DemoProgram which allows you
to interactively add elements to a map

The remainder of this document contains two sample runs of the demo program with annotations. Make sure you get the
exact same output when you do the project. If your maps look different, then something’s wrong in your implementation.

Note: In the example runs on the next few pages, user input is shown in green highlight and underlined.


Profs Akhter/Russell Assignment 2: Hash Tables CS310 – Spring 2020

4
Example Runs of DemoProgram for Table Type 1
>java DemoProgram 1

This is a demo interactive program for your hash table.
Be aware that both the keys and values in the table are
Strings, so if you enter 1 as your key, you get the
string "1" not the integer 1.

Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 1
----------Adding/Updating a Key-Value Pair----------
Enter a key: banana
Enter a value: 10
Added value at key.
(Hit to Continue)

******************************************
Table Size: 1, Capacity: 2
[0]: null
[1]: banana:10
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 1
----------Adding/Updating a Key-Value Pair----------
Enter a key: banana
Enter a value: 1
Updated value at key.
(Hit to Continue)

******************************************
Table Size: 1, Capacity: 2
[0]: null
[1]: banana:1
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 2
----------Getting a Value by Key----------
Enter a key: banana
Associated value is 1
(Hit to Continue)


******************************************
Table Size: 1, Capacity: 2
[0]: null
[1]: banana:1
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 3
----------Removing a Key-Value Pair----------
Enter a key: banana
Removed pair was (banana,1)
(Hit to Continue)

 Runs the main method for
the demo program, requ sting
to use the first type of table.
 Adds a key-value pair to the table.
 Shows the current table.
 Updates the value
associated with the key
if the key is in the table.
 Shows the current table.
 Request the value associated
with the given key.
 Removes the banana, note it
says what was removed.
Profs Akhter/Russell Assignment 2: Hash Tables CS310 – Spring 2020

5
******************************************
Table Size: 0, Capacity: 2
[0]: null
[1]: tombstone
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 2
----------Getting a Value by Key----------
Enter a key: banana
No such key
(Hit to Continue)


******************************************
Table Size: 0, Capacity: 2
[0]: null
[1]: tombstone
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 1
----------Adding/Updating a Key-Value Pair----------
Enter a key: banana
Enter a value: 1
Added value at key.
(Hit to Continue)

******************************************
Table Size: 1, Capacity: 2
[0]: null
[1]: banana:1
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 1
----------Adding/Updating a Key-Value Pair----------
Enter a key: orange
Enter a value: 2
Added value at key.
(Hit to Continue)

******************************************
Table Size: 2, Capacity: 4
[0]: null
[1]: null
[2]: orange:2
[3]: banana:1
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 1
----------Adding/Updating a Key-Value Pair----------
Enter a key: pear
Enter a value: 3
Added value at key.
 Table has a tombstone!
 Confirmed, no banana
in the table.
 Put the banana-1 pair back in.
 Tombstone replaced!
 Add some more fruit…
 Load too high when
adding, table rehashed.
 Add some more fruit…
Profs Akhter/Russell Assignment 2: Hash Tables CS310 – Spring 2020

6
(Hit to Continue)

******************************************
Table Size: 3, Capacity: 4
[0]: pear:3
[1]: null
[2]: orange:2
[3]: banana:1
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 1
----------Adding/Updating a Key-Value Pair----------
Enter a key: peach
Enter a value: 3
Added value at key.
(Hit to Continue)

******************************************
Table Size: 4, Capacity: 8
[0]: null
[1]: peach:3
[2]: orange:2
[3]: banana:1
[4]: null
[5]: null
[6]: pear:3
[7]: null
******************************************
(Hit to Continue)






Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 4
----------Resizing the Table----------
Enter a new size: 10
Resized table
(Hit to Continue)

******************************************
Table Size: 4, Capacity: 10
[0]: orange:2
[1]: null
[2]: null
[3]: peach:3
[4]: pear:3
[5]: null
[6]: null
[7]: banana:1
[8]: null
[9]: null
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 4
----------Resizing the Table----------
Enter a new size: 5
Resized table
(Hit to Continue)



 Load doesn’t require
expanding the table.
 Added more fruit...
 Bigger table...
 Manually resize table
to a larger table.
 Manually resize table
to a smaller table...
 Items moved around!
Profs Akhter/Russell Assignment 2: Hash Tables CS310 – Spring 2020

7
******************************************
Table Size: 4, Capacity: 5
[0]: orange:2
[1]: null
[2]: banana:1
[3]: peach:3
[4]: pear:3
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 4
----------Resizing the Table----------
Enter a new size: 4
Unable to resize table to requested size
(Hit to Continue)

******************************************
Table Size: 4, Capacity: 5
[0]: orange:2
[1]: null
[2]: banana:1
[3]: peach:3
[4]: pear:3
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 4

----------Resizing the Table----------
Enter a new size: 1
Unable to resize table to requested size
(Hit to Continue)

******************************************
Table Size: 4, Capacity: 5
[0]: orange:2
[1]: null
[2]: banana:1
[3]: peach:3
[4]: pear:3
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 1
----------Adding/Updating a Key-Value Pair----------
Enter a key: carrot
Enter a value: 3
Added value at key.
(Hit to Continue)

******************************************
Table Size: 5, Capacity: 10
[0]: orange:2
[1]: null
[2]: null
[3]: peach:3
[4]: pear:3
[5]: carrot:3
[6]: null
[7]: banana:1
[8]: null
[9]: null
******************************************
(Hit to Continue)
 Works as long as
there is at least one open
spot in the table.
 Try to resize without
enough room… does not
alter the table.
 Same problem.
 Add another food.
 Load too high,
table expands.
Profs Akhter/Russell Assignment 2: Hash Tables CS310 – Spring 2020

8


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 6
 Exit program.
Profs Akhter/Russell Assignment 2: Hash Tables CS310 – Spring 2020

9
Example Runs of DemoProgram for Table Type 2

>java DemoProgram 2

This is a demo interactive program for your hash table.
Be aware that both the keys and values in the table are
Strings, so if you enter 1 as your key, you get the
string "1" not the integer 1.

Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 1
----------Adding/Updating a Key-Value Pair----------
Enter a key: banana
Enter a value: 10
Added value at key.
(Hit to Continue)

******************************************
Table Size: 1, Capacity: 2
[0]: null
[1]: [banana:10]->null
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 1
----------Adding/Updating a Key-Value Pair----------
Enter a key: banana
Enter a value: 1
Updated value at key.
(Hit to Continue)
******************************************
Table Size: 1, Capacity: 2
[0]: null
[1]: [banana:1]->null
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 2
----------Getting a Value by Key----------
Enter a key: banana
Associated value is 1
(Hit to Continue)

******************************************
Table Size: 1, Capacity: 2
[0]: null
[1]: [banana:1]->null
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 3
----------Removing a Key-Value Pair----------
Enter a key: banana
Removed pair was (banana,1)
(Hit to Continue)


 Runs the main method for
the demo program, requesting
to use the second type of table.
 Adds a key-value pair to the table.
 Shows the current table, this
one is an array of linked lists!
 Updates the value
associated with the key
if the key is in the table.
 Updated table.
 Request the value.
 Removes the banana.
Profs Akhter/Russell Assignment 2: Hash Tables CS310 – Spring 2020

10
******************************************
Table Size: 0, Capacity: 2
[0]: null
[1]: null
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 2
----------Getting a Value by Key----------
Enter a key: banana
No such key
(Hit to Continue)

******************************************
Table Size: 0, Capacity: 2
[0]: null
[1]: null
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 1
----------Adding/Updating a Key-Value Pair----------
Enter a key: banana
Enter a value: 1
Added value at key.
(Hit to Continue)


******************************************
Table Size: 1, Capacity: 2
[0]: null
[1]: [banana:1]->null
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 1
----------Adding/Updating a Key-Value Pair----------
Enter a key: orange
Enter a value: 2
Added value at key.
(Hit to Continue)

******************************************
Table Size: 2, Capacity: 4
[0]: null
[1]: null
[2]: [orange:2]->null
[3]: [banana:1]->null
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 1
----------Adding/Updating a Key-Value Pair----------
Enter a key: pear
Enter a value: 3
Added value at key.
 No tombstones in
separate chaining!
 Confirmed, no banana.
 Put the banana-1 pair back in.
 Add some more fruit…
 Load too high, rehashed.
 Add some more fruit…
Profs Akhter/Russell Assignment 2: Hash Tables CS310 – Spring 2020

11
(Hit to Continue)

******************************************
Table Size: 3, Capacity: 4
[0]: null
[1]: null
[2]: [orange:2]->null
[3]: [banana:1]->[pear:3]->null
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 1
----------Adding/Updating a Key-Value Pair----------
Enter a key: peach
Enter a value: 3
Added value at key.
(Hit to Continue)

******************************************
Table Size: 4, Capacity: 8
[0]: null
[1]: [peach:3]->null
[2]: [orange:2]->null
[3]: [banana:1]->null
[4]: null
[5]: null
[6]: null
[7]: [pear:3]->null
******************************************
(Hit to Continue)






Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 4
----------Resizing the Table----------
Enter a new size: 10
Resized table
(Hit to Continue)

******************************************
Table Size: 4, Capacity: 10
[0]: [orange:2]->null
[1]: null
[2]: null
[3]: [peach:3]->[pear:3]->null
[4]: null
[5]: null
[6]: null
[7]: [banana:1]->null
[8]: null
[9]: null
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 4
----------Resizing the Table----------
Enter a new size: 5
Resized table
(Hit to Continue)



 Load doesn’t require
expanding the table, but some
“chains” are now forming!
 Add more fruit...
 Bigger table,
shorter chains.
 Manually resize table
to a larger table.
 Items moved
around, and some
chains occurred even
with the bigger table!
 Manually resize table
to a smaller table...
Profs Akhter/Russell Assignment 2: Hash Tables CS310 – Spring 2020

12
******************************************
Table Size: 4, Capacity: 5
[0]: [orange:2]->null
[1]: null
[2]: [banana:1]->null
[3]: [peach:3]->[pear:3]->null
[4]: null
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 4
----------Resizing the Table----------
Enter a new size: 4
Resized table
(Hit to Continue)

******************************************
Table Size: 4, Capacity: 4
[0]: null
[1]: [peach:3]->null
[2]: [orange:2]->null
[3]: [banana:1]->[pear:3]->null
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 4


----------Resizing the Table----------
Enter a new size: 1
Resized table
(Hit to Continue)

******************************************
Table Size: 4, Capacity: 1
[0]: [peach:3]->[orange:2]->[banana:1]->[pear:3]->null
******************************************
(Hit to Continue)


Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 1
----------Adding/Updating a Key-Value Pair----------
Enter a key: carrot
Enter a value: 3
Added value at key.
(Hit to Continue)

******************************************
Table Size: 5, Capacity: 8
[0]: null
[1]: [peach:3]->null
[2]: [orange:2]->null
[3]: [banana:1]->null
[4]: null
[5]: [carrot:3]->null
[6]: null
[7]: [pear:3]->null
******************************************
(Hit to Continue)






 Works as long as there
is at least one slot!
 Resizing smaller, still works!
 Even smaller, still works!
⬉ All in one chain. Note the order
of items here! Very important
that it comes out the same for
you! If it doesn’t, you’re not
following the instructions in the
rehash method properly.
 Add another food.
 Load too high after adding,
table does a “double in size and
rehash” until the load is below
80%! If the items are in the
wrong order, you may be trying
to expand all at once instead of
rehashing repeatedly.
Profs Akhter/Russell Assignment 2: Hash Tables CS310 – Spring 2020

13
Options:
1. Add/Replace a Key-Value Pair
2. Get the value associated with a key
3. Remove a key
4. Resize the table
5. Display the table
6. Quit
Enter a menu choice: 6
 Exit program.
51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: abby12468