Task

Implement ChainedHashMap, a map with a hash-table using separate chaining to resolve collisions, and its associated iterator class.

Warning

Correctly implementing your iterator will be tricky. We recommend starting early on it.

Overall Design

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 reuse your own 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 chain 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 look something like the following figure.

ChainedHashMap before

In this example, the key “a” lands in index 2, but the index could change 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).

ChainedHashMap after

Your implementation should include the following constructors:

Signature Description
ChainedHashMap() Constructs a new ChainedHashMap with default parameters.
ChainedHashMap(double resizingLoadFactorThreshold,
int initialChainCount,
int chainInitialCapacity)
Constructs a new ChainedHashMap with the given parameters.

Implementation Details

Requirements

  • All methods should run in O(1)\mathcal{O}(1) time in practice (except when resizing, in which case put may run in Θ(n)\Theta(n) time, where nn is the size of the data structure).
  • The iterator must adhere to all the requirements listed in the Iterator section.

Notes

  • The 0-argument constructor requires you to determine and define some reasonable defaults in the final fields at the top of the class.
  • The second constructor has some parameters to configure the behavior of the map:
    • resizingLoadFactorThreshold: when the load factor exceeds this value, the array of chains resizes.
    • initialChainCount: the initial number of chains for your hash table
    • chainInitialCapacity: the initial capacity of each ArrayMap chain created by the map
  • If your ChainedHashMap receives a null key, use a hashcode of 0 for that key.
  • Do not try to implement your own hash function. Use Java’s Object.hashCode() method instead—e.g., int hashCode = key.hashCode().
  • Use the provided createChain method to instantiate your ArrayMap, rather than calling the ArrayMap constructor.

Tips

  • We recommend doubling the number of chains when resizing.
  • You are NOT required to downsize your hash table if the user removes many elements.
  • You should call the iterator method on each ArrayMap inside your chains array.
  • You may add as many extra fields as you need to track your iterator’s state.

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

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 example, here are a couple of invariants that you might include:

  • Each index in the array of chains is null if and only if 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.

Iterator Implementation

Info

Watch this video by a former TA that provides an overview of the iterator as used in another Map implementation.

As part of ChainedHashMap, you will implement an iterator class (we already wrote a placeholder class for you called ChainedHashMapIterator):

Tip

You can reuse hasNext() in your next() to save time, because these two methods may share common logic. For example, you might put your logic related to advancing chains in hasNext(), and then after next() calls hasNext() to verify if there are more elements, your internal chains’ iterators would have already advanced to the correct state.

Remember that the actual elements of your ChainedHashMap are stored in the internal ArrayMap chains. This mean that you have to use the individual ArrayMap iterators to obtain elements. You also have to keep track of their states and advance to the next chain’s iterator when the current one runs out.

Before you write any iterator code:

  • Try designing an algorithm using pencil and paper, and run through a few examples by hand i.e. draw the chains array that has some varying number of ArrayMap objects scattered throughout, and simulate what your algorithm does.
  • Think about the invariants of your ChainedHashMap.