CSE 373, Summer 2018: Project 2: ChainedHashMap and ChainedHashSet

Overview

In this project, you will implement a hashmap and a hashset. We will be using these two data structures extensively in the upcoming project.

You will use these files from your prior assignments

  • main.java.datastructures.concrete.dictionaries.ArrayDictionary.java
  • main.java.datastructures.concrete.DoubleLinkedList.java

If you have chosen a new partner for this assignment, choose either of your submissions from part 1 and verify that these are functioning properly.

You will be modifying the following files:

  • main.java.datastructures.concrete.dictionaries.ArrayDictionary.java
  • main.java.datastructures.concrete.ChainedHashSet.java
  • main.java.datastructures.concrete.dictionaries.ChainedHashDictionary.java

Additionally, here are a few more files that you might want to review while completing the assignment (note that this is just a starting point, not necessarily an exhaustive list):

  • test.java.datastructures.TestChainedHashSet.java
  • test.java.datastructures.dictionaries.TestChainedHashDictionary
  • test.java.datastructures.dictionaries.TestArrayDictionary.java
  • main.java.datastructures.interfaces.IDictionary.java
  • main.java.datastructures.interfaces.ISet.java

This is a team assignment. This entire project is due on Friday, July 27 at 11:59pm.

When working on this assignment, we expect you meet these baseline expectations at all times:

Expectations

Here are some baseline expectations we expect you to meet:

  • You are required to pair program this assignment. Pair programming was discussed in class, but as a reminder, this means that both you and your partner are sitting around one computer coding together at all times. One person is the "driver" who is typing code, the other person is the "navigator" who is looking on, reviewing each line of code as it is typed and checking if the code makes sense, has good logic flow, takes into account edge cases, and doesn't have typos. You and your partner are required to switch roles frequently so that by the end of the project, each partner has had equal time "driving" and "navigating".

  • Follow the course collaboration policies

  • DO NOT use any classes from java.util.*. There are only two exceptions to this rule:

    1. You may import and use java.util.Iterator and java.util.NoSuchElementException.

    2. You may import and use anything from java.util.* within your testing code.

  • DO NOT modify instructor-provided code (unless told otherwise)

  • Part of the objective of the projects is to give you practice reading and understanding code that has already been written. This means that in order to start coding, you will need to spend time reading and understanding what is happening in the skeleton code and all project documentation.

Part 0: Initial Setup

  1. Clone your group's project from https://gitlab.cs.washington.edu/cse373-18su-project2/ and open it in Eclipse. See the instructions from project 1 if you need a reminder on how to do this (remember you must first import the project as a git project, then cancel and import as a gradle project).

  2. Copy your DoubleLinkedList.java and ArrayDictionary.java files from project 1 to this new one.

    The copied code will not immediately compile. This is ok: we modified IDictionary so it requires you to implement one additional method.

  3. Copy any of the delete tests you wrote from TestDeleteFunctionality.java and TestDeleteStress.java to the new TestDoubleLinkedList.java.

    Be sure not to overwrite the entire TestDoubleLinkedList class: we gave you a slightly modified one containing a few extra tests.

  4. Finally, make sure everything works.

    Try running TestDoubleLinkedList and make sure the tests run.

    Try running SanityCheck.java, and try running checkstyle. Checkstyle should still report the same 5 errors with SanityCheck.java as it did with project 1.

Part 1: Repair ArrayDictionary

Task: implement ArrayDictionary.iterator().

Take a look at IDictionary. You may notice that the interface now requires all subclasses to implement one additional method: iterator().

By implementing this method, we can now (efficiently) iterate over all key-value pairs in our dictionaries! For example, we can now do this:

IDictionary<String, Integer> foo = makeTheDictionary();
for (KVPair<String, Integer> pair : foo) {
    String key = pair.getKey();
    Integer value = pair.getValue();
    
    // Do something with key and value
    System.out.println(key + " : " + value);
}

The above program should print out every key-value pair contained within foo.

Notes:

  1. Your iterator() method may return the key value pairs in any order you wish. The easiest approach would likely be to return them in the order your pairs are listed in your internal array.

  2. You may assume the user will not modify the dictionary while you're iterating over it.

  3. You may NOT create any temporary data structures such as a temp IList when implementing your iterator. We want our iterators to be efficient, and having to copy the contents of our dictionary to some other data structure at any point is suboptimal.

    You may, however, create new KVPair objects. (They do not count as "temporary" data structures).

  4. We have provided you with unit tests for your iterators. You can add more tests if you want.

  5. If you need examples on how to implement an iterator, see DoubleLinkedList and the stubs in ChainedHashDictionary. Also see the ArrayList iterator we implemented together at the start of the quarter.

  6. The IDictionary interface requires that dictionaries return KVPair objects. However, your internal dictionary uses private Pair objects. You will need to convert between the two within your iterator – see the method header comments in KVPair to understand how to instantiate new KVPair objects.

  7. When creating the iterator, you will need to create a private static inner class to ArrayDictionary. Your class should look roughly like this:

    private static class ArrayDictionaryIterator<K, V> implements Iterator<KVPair<K, V>> {
    // ...
}

    Make sure to make the class private and static, and make sure you copy how the generics are being defined correctly.

Part 2: Implement ChainedHashDictionary

Task: complete the ChainedHashDictionary class.

Notes:

  • You may implement any resizing strategy covered in lecture.
  • Use ArrayDictionary as your internal chains/buckets.
  • If your ChainedHashDictionary recieves a null key, use a hashcode of 0 for that key.
  • Your iterator() method doesn't need to yield the pairs in any particular order.

Correctly implementing your iterator will be tricky – don't leave it to the last minute! Try and finish the other methods in ChainedHashDictionary as soon as possible so you can move on to implementing iterator().

The comments in ChainedHashDictionary will contain a few hints on how to implement this method.

Part 3: Implement ChainedHashSet

Task: complete the ChainedHashSet class.

Notes:

  • To avoid code duplication, we will use an internal dictionary of type IDictionary<KeyType, Boolean> to store your set values. We will completely ignore the values in your dictionary: use a placeholder boolean whenever necessary.
  • Your code for this class should be very simple: your inner dictionary should be doing most of the work.

Part 4: Complete writeup

Task: submit answers to the following questions.

Each group member should answer and submit these questions independently at this canvas page.

You must submit your answers in either .txt or .pdf form.

  1. Questions about the project:
    1. What is your name and your partner's name?
    2. How was the project? Did you enjoy it?
    3. Do you have any suggestions for improving the project?
  2. Questions about your partner:
    1. How did you feel about pair programming this assignment
    2. How was your partnership?

Deliverables

The following deliverables are due on Friday, July 27 at 11:59pm.

Code submission will be the same as project 1, by pushing and taging your code with the "SUBMIT" tag. When you and your partner are done with your code, commit and push it, then tag that commit as SUBMIT. To tag a commit in Eclipse, right-click your project and select "Team > Advanced > Tag", then write SUBMIT in the "Tag Name" field. The "Tag Message" can be whatever you want - it is like a commit message. Then click Create Tag and Start Push. It is very important that you do this instead of just "Create Tag" so that it gets pushed back to Gitlab instead of staying on your machine. If you forget to push the tag, you can do so via "Team > Remotes > Push Tags..."

Before submitting, be sure to double-check and make sure that...

  • Your ArrayDictionary class is fully repaired and passes all tests.
  • Your ChainedHashDictionary class is fully implemented and passes all tests.
  • Your ChainedHashSet class is fully implemented and passes all tests.
  • You ran the checkstyle plugin within Eclipse and fixed all style errors.
  • The final version of your code is tagged exactly as "SUBMIT"

Both partners should turn in a .txt or .pdf file containing their answers to part 4 on Canvas if you haven't already. This is due on the Monday following the project due date at 11:59pm (3 days later). If you would like to appeal your grade for this assignment, remember to include a write up of your justification in your individual write up. This will be the only form of grade appeal that we will accept.