QuestionQuestion

Transcribed TextTranscribed Text

Assignment 2: Hash Tables 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) . 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. 2 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<K,V>[] while for separate chaining the storage is Node<K,V>[]. 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. 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. 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 <Enter> to Continue) ****************************************** Table Size: 1, Capacity: 2 [0]: null [1]: banana:10 ****************************************** (Hit <Enter> 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 <Enter> to Continue) ****************************************** Table Size: 1, Capacity: 2 [0]: null [1]: banana:1 ****************************************** (Hit <Enter> 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 <Enter> to Continue) ****************************************** Table Size: 1, Capacity: 2 [0]: null [1]: banana:1 ****************************************** (Hit <Enter> 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 <Enter> to Continue)  Runs the main method for the demo program, requesting 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. 5 ****************************************** Table Size: 0, Capacity: 2 [0]: null [1]: tombstone ****************************************** (Hit <Enter> 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 <Enter> to Continue) ****************************************** Table Size: 0, Capacity: 2 [0]: null [1]: tombstone ****************************************** (Hit <Enter> 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 <Enter> to Continue) ****************************************** Table Size: 1, Capacity: 2 [0]: null [1]: banana:1 ****************************************** (Hit <Enter> 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 <Enter> to Continue) ****************************************** Table Size: 2, Capacity: 4 [0]: null [1]: null [2]: orange:2 [3]: banana:1 ****************************************** (Hit <Enter> 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… 6 (Hit <Enter> to Continue) ****************************************** Table Size: 3, Capacity: 4 [0]: pear:3 [1]: null [2]: orange:2 [3]: banana:1 ****************************************** (Hit <Enter> 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 <Enter> 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 <Enter> 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 <Enter> 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 <Enter> 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 <Enter> 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! 7 ****************************************** Table Size: 4, Capacity: 5 [0]: orange:2 [1]: null [2]: banana:1 [3]: peach:3 [4]: pear:3 ****************************************** (Hit <Enter> 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 <Enter> to Continue) ****************************************** Table Size: 4, Capacity: 5 [0]: orange:2 [1]: null [2]: banana:1 [3]: peach:3 [4]: pear:3 ****************************************** (Hit <Enter> 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 <Enter> to Continue) ****************************************** Table Size: 4, Capacity: 5 [0]: orange:2 [1]: null [2]: banana:1 [3]: peach:3 [4]: pear:3 ****************************************** (Hit <Enter> 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 <Enter> 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 <Enter> 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. 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. 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 <Enter> to Continue) ****************************************** Table Size: 1, Capacity: 2 [0]: null [1]: [banana:10]->null ****************************************** (Hit <Enter> 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 <Enter> to Continue) ****************************************** Table Size: 1, Capacity: 2 [0]: null [1]: [banana:1]->null ****************************************** (Hit <Enter> 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 <Enter> to Continue) ****************************************** Table Size: 1, Capacity: 2 [0]: null [1]: [banana:1]->null ****************************************** (Hit <Enter> 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 <Enter> 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. 10 ****************************************** Table Size: 0, Capacity: 2 [0]: null [1]: null ****************************************** (Hit <Enter> 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 <Enter> to Continue) ****************************************** Table Size: 0, Capacity: 2 [0]: null [1]: null ****************************************** (Hit <Enter> 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 <Enter> to Continue) ****************************************** Table Size: 1, Capacity: 2 [0]: null [1]: [banana:1]->null ****************************************** (Hit <Enter> 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 <Enter> to Continue) ****************************************** Table Size: 2, Capacity: 4 [0]: null [1]: null [2]: [orange:2]->null [3]: [banana:1]->null ****************************************** (Hit <Enter> 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… 11 (Hit <Enter> to Continue) ****************************************** Table Size: 3, Capacity: 4 [0]: null [1]: null [2]: [orange:2]->[pear:3]->null [3]: [banana:1]->null ****************************************** (Hit <Enter> 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 <Enter> 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]: [pear:3]->null [7]: null ****************************************** (Hit <Enter> 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 <Enter> to Continue) ****************************************** Table Size: 4, Capacity: 10 [0]: [orange:2]->null [1]: null [2]: null [3]: [peach:3]->null [4]: [pear:3]->null [5]: null [6]: null [7]: [banana:1]->null [8]: null [9]: null ****************************************** (Hit <Enter> 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 <Enter> 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!  Manually resize table to a smaller table... 12 ****************************************** Table Size: 4, Capacity: 5 [0]: [orange:2]->null [1]: null [2]: [banana:1]->null [3]: [peach:3]->null [4]: [pear:3]->null ****************************************** (Hit <Enter> 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 <Enter> to Continue) ****************************************** Table Size: 4, Capacity: 4 [0]: null [1]: [peach:3]->null [2]: [orange:2]->[pear:3]->null [3]: [banana:1]->null ****************************************** (Hit <Enter> 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 <Enter> to Continue) ****************************************** Table Size: 4, Capacity: 1 [0]: [peach:3]->[orange:2]->[pear:3]->[banana:1]->null ****************************************** (Hit <Enter> 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 <Enter> 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]: [pear:3]->null [7]: null ****************************************** (Hit <Enter> to Continue)  Works, regardless of how many slots!  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. 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.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

class ThreeTenHashTable1<K,V> {
//you must use this storage for the hash table
//and you may not alter this variable's name, type, etc.
private TableEntry<K,V>[] storage;

/* +++++++++++++++++++ YOUR CODE HERE +++++++++++++++++++ */
//Add additional instance variables here!
//You may also add additional _private_ methods if you'd like.

private int size, capacity;
//private TableEntry<K,V> tombStone = new TableEntry<K, V>(null, null);

@SuppressWarnings("unchecked")
public ThreeTenHashTable1(int size) {
//Create a hash table where the size of the storage is
//the provided size (number of "slots" in the table)
//You may assume size is >= 2

this.storage = new TableEntry[size];
this.size = 0;
this.capacity = size;


//Remember... if you want an array of ClassWithGeneric<V>, the following format ___SHOULD NOT___ be used:
//         ClassWithGeneric<V>[] items = (ClassWithGeneric<V>,[]) Object[10];
//instead, use this format:
//         ClassWithGeneric<V>[] items = (ClassWithGeneric<V>,[]) ClassWithGeneric[10];
}

public int getCapacity() {
//return how many "slots" are in the table
//O(1)
return capacity;
}

public int size() {
//return the number of elements in the table
//O(1)
return size;
}

private int findKey(K k)
{
int pos = Math.abs(k.hashCode()) % capacity, pos0 = pos;


while (storage[pos]!=null)
{
if (storage[pos].getKey().equals(k))
break;

pos = (pos + 1) % capacity;
if (pos == pos0)
return -1;
}

return pos;
}

public void put(K k, V v) {
//Place value v at the location of key k.
//Use linear probing if that location is in use.
//You may assume both k and v will not be null.

//Hint: Make a TableEntry to store in storage
//and use the absolute value of k.hashCode() for
//the probe start.

//If the key already exists in the table
//replace the current value with v.

//If the load on the table is >= 80% _after_ adding
//expand the table to twice the size.

//Worst case: O(n), Average case: O(1)

int pos = this.findKey(k);
if (storage[pos] == null) this.size++;
else if (storage[pos].getValue() == null) size++;

storage[pos] = new TableEntry<K, V>(k, v);

if (size *1.0 / capacity >= 0.8)
rehash(2*capacity);
}

public V remove(K k) {
//Remove the given key (and associated value)
//from the table. Return the value removed.
//If the value is not in the table, return null.

//Hint 1: Remember to leave a tombstone!
//Hint 2: Does it matter what a tombstone is?
//   Yes and no... You need to be able to tell
//   the difference between an empty spot and
//   a tombstone and you also need to be able
//   to tell the difference between a "real"
//   element and a tombstone.

//Worst case: O(n), Average case: O(1)

int pos = this.findKey(k);
if (pos == -1)
return null;

V oldValue = storage[pos].getValue();
storage[pos] = new TableEntry<K, V>(k, null); // tombstone
this.size--;

return oldValue;
}

public V get(K k) {
//Given a key, return the value from the table....

By purchasing this solution you'll be able to access the following files:
Solution.zip.

$38.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats