Programming

Complete the programming portion of the assignment.

Table of contents

1. Java’s Map Interface
   1. Iterator
2. ArrayMap
3. ChainedHashMap
4. Submission

Java’s Map Interface

Background

Understand Java’s Map interface, which you’ll be implementing in this assignment.

Although our map implementations will include essentially all the functionality of Java’s Map interface, you will only need to implement a few of its methods—all the others will have default implementations that use the methods you implement.

See the method documentation in AbstractIterableMap or Java’s Map interface for more details.

Note

The get, remove, and containsKey methods accept any Object parameters, rather than restricting the key type to K. This should not cause any issues in your map implementations, since you’ll only ever need to call methods on these keys that are defined in the base Object class, but Java’s decision to not restrict these types is debatable from a client perspective.

Note

You might notice that the iterator method is not actually a part of the standard Map interface. Those of you who are very familiar with Java’s maps may also realize that the functionality of this iterator overlaps with Map.entrySet. While this is definitely a little strange, we feel that the iterator interface is easier and cleaner to implement than entrySet, so we’re having you implement an iterator and providing an entrySet implementation that simply uses your iterator.

Iterator

Background

Review the iterator design pattern and the implementation notes and requirements below.

In Java, an iterator is a type of object that lets a client efficiently iterate over a data structure using a foreach loop. Whenever we write code like:

for (String item : something) {
    // ...etc...
}

Java will internally convert that code into the following:

Iterator<String> iter = something.iterator();
while (iter.hasNext()) {
    String item = iter.next();
    // ...etc...
}

When you call iter.next for the first time, the iterator will return the first item of something. If you call it again, it’ll return the second item. If the user calls iter.next after the iterator has gone through all items of something, the method will throw a NoSuchElementException.

To help avoid this, we can use iter.hasNext, which will return true if calling iter.next will safely return a value, and false otherwise.

You can see an example of this expected behavior within your tests.

In practice, iterators can also be used to safely modify the object they’re iterating over. We will not be implementing this functionality in this class: you should assume the client will never modify a data structure while they’re iterating over it.

Notes and Requirements

• You may NOT create any new temporary data structures inside of your iterators. We want our iterators to be efficient, and having to copy the contents of our map to some other data structure at any point is suboptimal.
• Your iterator methods must run in constant time with respect to the size of the data structure.
• Your iterators may return entries in any order you wish. The easiest approach would likely be to return them in the same order as your map’s internal representation.
• You may assume that the user will not modify your maps while your iterators are in use. For example, the following will never happen:

    Iterator<Entry<String, Integer>> itr = map.iterator();
    itr.next();
    // the following line should never happen if the same
    // iterator instance is used later
    map.put("hi", "373");
    itr.next();
  

  Note that it is completely valid to modify the dictionary in between creating iterator objects:

    Iterator<Entry<String, Integer>> itr = map.iterator();
    itr.next();
    map.put("hi", "373");
    itr = map.iterator();
    itr.next();
  

ArrayMap

Task

Implement the basic ArrayMap, as described in lecture.

Your ArrayMap class will internally keep track of its key-value pairs by using an array of Map.Entry<K, V> objects. For example, after running the following code:

Map<String, Integer> map = new ArrayMap<>();
map.put("a", 11);
map.put("b", 22);
map.put("c", 33);

Your map’s internal array should look like this:

And if we add a few more entries:

map.put("d", 44);
map.remove("b");
map.put("a", 55);

Your internal array should now look like the image below.

There are two particularly noteworthy points to make about the image above:

1. We’ve updated the old entry for “a” to store the new value.
2. We’ve replaced the entry for “b” with the one for “d”. Because maps are inherently unordered, when removing an entry, we can simply replace it with the last entry in the array, rather than shifting over all the elements as you might normally do in an array list. For example, this is what the call to map.remove("b") would do in the example above:

Your implementation should include the following constructors:

Notes

• The second constructor includes a parameter to specify the initial capacity of the internal array. For the first constructor, you’ll need to set some default value in the field at the top of the class. Choose something that seems reasonable and adjust if it seems necessary.
• If your array is full and the user inserts a new key, create a new array that is double the size of the old one and copy over the old elements.
• Your internal array will store elements of type SimpleEntry<K, V>, so it will probably be worth looking at the SimpleEntry class defined in AbstractMap. The easiest way to get there in IntelliJ will be to middle-click or control/command-click on any SimpleEntry type in the editor.
  • SimpleEntry<K, V> implements Entry<K, V>, so you can simply return your map’s SimpleEntry objects when implementing Iterator.next.

Requirements

• All methods must run in $\mathcal{O}(n)$ time, where $n$ is the size of the map.
• size and iterator must run in $\mathcal{O}(1)$ time.
• See also the iterator notes and requirements above.

ChainedHashMap

Task

Implement ChainedHashMap, a map with a hash-table using separate chaining to resolve collisions.

Warning

Correctly implementing your iterator will be tricky—don’t leave it to the last minute!

When we covered separate chaining in lecture, we used a list as the chaining data structure. In this assignment, instead of a list, you will use your ArrayMap.

When you first create your array of chains, it will contain only null references. As entries are inserted into the table, you need to create the chains (ArrayMaps) as required. Let’s say you created a chains array of size 5 (you can choose any initial size), and you inserted the key “a” with the value 11.

Map<String, Integer> map = new ChainedHashMap<>();
map.put("a", 11);

Your hash table should something like the following figure.

In this example, the key “a” lands in index 2, but if might be in a different index depending on your table size. Also, in this example, the ArrayMap (chain) has size 3, but you can choose a different initial size for your ArrayMap.

Now suppose you insert a few more keys:

map.put("f", 13);
map.put("c", 12);

Your internal hash table should now look like the figure below. In this example, keys “a” and “f” both hash to the same index (2).

Notes

• The second constructor has some parameters to configure the behavior of the map:
  • resizingLoadFactorThreshold: when the load factor exceeds this value, the map resizes
  • initialChainCount: the initial number of chains for your map
  • chainInitialCapacity: the initial capacity of each ArrayMap chain created by the map
• For the other, 0-argument constructor, you’ll need to define some reasonable defaults in the final fields at the top of the class.
• If your ChainedHashMap receives a null key, use a hashcode of 0 for that key.
• You may implement any resizing strategy covered in lecture—we recommend doubling the number of chains on every resize since it’s the simplest to implement, though.
• Do not try to implement your own hash function. Use Java’s Object.hashCode() method instead—e.g., int hashCode = key.hashCode().
  • Note: The integers returned by this method may be negative or greater than chains.length. How would you handle this?
• Use the provided createChain method to instantiate your ArrayMap, rather than calling the ArrayMap constructor directly. The grader will override createChain during grading to instantiate our solution version of ArrayMap instead, preventing any possible bugs in your ArrayMap from affecting your ChainedHashMap.

Requirements

• All methods should run in $\mathcal{O}(1)$ time in practice (except when resizing, in which case put may run in $\Theta(n)$ time, where $n$ is the size of the data structure).
• See also the iterator notes and requirements above.

Tips

• You may (and probably should) call the iterator method on each ArrayMap inside your chains array, since instantiating an iterator of an existing data structure has low cost in both space and time.
• You may and should add as many extra fields as you need to track your iterator’s state. For reference, our solution implementation uses three (including the one we gave you).
• Before you write any iterator code:
  • Try designing an algorithm using pencil and paper, and run through a few examples by hand. This means you should draw the chains array that has some varying number of ArrayMap objects scattered throughout, and you should try simulate what your algorithm does.

  • Think about the invariants of your ChainedHashMap.

    Good use of invariants can greatly reduce your code complexity by reducing the number of cases you need to consider. For example, you hopefully found in the previous assignment, ensuring that a certain field is never null allows you to omit null checks.

    In this assignment as well, and in general, much of the complexity in your code execution will arise from handling edge cases—the empties and nulls and such. Think about what invariants you should uphold in both your main ChainedHashMap code and in your iterator. Obviously, this might involve tweaking the way your ChainedHashMap stores data, but it’s certainly worthwhile if you can reduce the overall complexity of your code.

    For reference, our ChainedHashMap iterator solution uses about 20 lines of code (ignoring blank lines, but including braces), but we often see students needing to write upwards of 50 lines’ worth of special casing if-branches to handle all their cases.

    For example, here are a couple invariants that you might include:

    • Each index in the array of chains is null iff that chain has no entries.
    • The currentChain field of the iterator always references the current chain being iterated through (the chain which contains the next entry that next will return).
    • The currentChain field is null after the iterator has been exhausted of all entries.

    Make sure to write down your invariants (perhaps in a comment somewhere in the class?) so that you don’t forget them, and make sure that you actually uphold your invariants before and after every method! Having them explicitly written out will also help in case you decide to change your invariants while implementing your code—a very real possibility, since it may not be entirely clear what invariants provide useful restrictions on your data structure’s state.

Submission

Task

Commit and push your changes to GitLab before submitting to Gradescope.

If you’re working in a group, the partner who submits must add the other partner as a group member on Gradescope. Here’s a video demonstrating that process. You’ll also need to re-add group members whenever you resubmit to the same assignment, even if you already did so on a previous submission.

Note

Submitting the same code as another student without using Gradescope’s group feature is considered plagiarism, and may have consequences.

After you’ve made sure that you’re passing all tests on Gradescope, you can start running the experiments.