辅导案例-CS310-Assignment 2
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.