Overall Design¶

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 a few important things to notice:

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”. Maps are inherently unordered so when removing an entry, we can simply replace it with the last entry in the array. For example, this is what the call to map.remove("b") would do in the example above:

Your implementation should include the following constructors:

Implementation Details¶

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.
• The iterator() function must return an iterator that adheres to all the requirements listed in the Iterator section.

Notes¶

• You are not required to downsize your array if the user removes many elements.
• Your internal array should store elements of type SimpleEntry<K, V> (take a look at SimpleEntry.java for more details).

Tips¶

• If the array is full and a new key is inserted, create a new array and copy over the old elements.
• If you need to check object equality but can’t guarantee that either object is non-null, use Objects.equals(a, b) under java.util—it does all the necessary null checks for you.
• By default, IntelliJ’s debugger may attempt to show the entries of your map instead of its fields. To disable this feature, open the project settings and navigate to Build, Execution, Deployment | Debugger | Data Views | Java, then deselect Enable alternative view for Collection classes.

Iterator Implementation¶

After you finish implementing all required behaviors of the ArrayMap, you may now work on implementing an iterator for the ArrayMap so that your client will be able to iterate over your ArrayMap.

Hints¶

• You might become a client of the ArrayMap when implementing the ChainedHashMap!
• SimpleEntry<K, V> implements Entry<K, V>, so you can simply return your map’s SimpleEntry objects when implementing Iterator.next.

Testing¶

Before moving on to your next task, make sure to write tests for your ArrayMap implementation. There is no number of required tests to write, but the more (and better) tests you write, the more confident you can be in your implementation. Being confident that your ArrayMap works is very important because the next part of the assignment will be using your ArrayMap implementation as a building block for a more complex data structure. If you have bugs in your ArrayMap, it will make your ChainedHashMap implementation more difficult to debug.