Due
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 .
When working on this assignment, we expect you meet these baseline expectations at all times:
java.util.*
unless explicitly told otherwise.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.
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.
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:
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.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.DoubleLinkedList
and the stubs in
ChainingHashDictionary
.Task: complete the ChainingHashDictionary
class.
Notes:
ArrayDictionary
s as your internal chains/buckets.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.
Task: complete the ChainingHashSet
class.
Notes:
IDictionary<KeyType, Boolean>
to store
your set values. We will completely ignore the values
in your dictionary: use a placeholder boolean whenever
necessary.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.
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...
ArrayDictionary
class is fully repaired and
passes all tests.
ChainedHashDictionary
class is fully
implemented and passes all tests.ChainedHashSet
class is fully
implemented and passes all tests.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.