ChainedHashMap Implementation

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);

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

Your implementation should include the following constructors:

Implementation Details¶

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).
• 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¶

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

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.