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 .

Expectations

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

• Your team MUST follow our course collaboration policies. In short, we expect you to pair program and write code with your partner. You may discuss this assignment with other teams on only a high level.
• You MAY NOT use any classes from java.util.* unless explicitly 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, ArrayDictionary.java, and TestDoubleLinkedList.java files from project 1 to this new one. These files should be copied into the same packages.

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

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
}

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

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 may be tricky — don't leave it to the last minute! The comments in ChainingHashDictionary will contain a few hints for 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 .

A single person in your group should submit the entire contents of your src folder on Canvas.

Please follow the above instructions EXACTLY. In particular, DO NOT rename your "src" folder before zipping it or modify the folder structure in any way.

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 (using the CSE 373 style ruleset) and fixed all style errors it reports. You may ignore any 'IndentationCheck' warnings but must fix all other errors.

Furthermore, both partners should turn in a .txt or .pdf file containing their answers to part 4 at this canvas link, if you haven't already. This is due at the same time as the rest of your project.