CSE 373, Winter 2018: Project 2: ChainingHashMap and ChainingHashSet

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.

This is a team assignment. This entire project is due on Wed, Jan 31 at 11:30pm.

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:

  • 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 0: Initial Setup

  1. Download the project from this link and open it in your IDE. See the instructions from project 1 if you need a reminder on how to do this.

  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 TestDoubleLinkedList.java to the new one.

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

Task: complete the ChainingHashDictionary class.

Notes:

  • You may implement any resizing strategy covered in lecture.
  • Use ArrayDictionarys as your internal chains/buckets.
  • If your ChainingHashDictionary 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 ChainingHashDictionary as soon as possible so you can move on to implementing iterator().

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

Part 3: Implement ChainingHashSet

Task: complete the ChainingHashSet 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 (skip if you worked solo):
    1. Which parts of the project did you work on, and which parts did your partner program?
    2. How was your partnership? Do you feel you and your partner contributed equally to this project?

Deliverables

The following deliverables are due on Wed, Jan 31 at 11:30pm.

A single person from your partnership should submit a zip file conaining the entire contents of your src folder on Canvas.

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.

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 at the same time as the rest of your project.