Task
Implement the basic ArrayMap, as described in lecture, and its associated iterator class.
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:
- We’ve updated the old entry for “a” to store the new value.
- 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:
Signature | Description |
---|---|
ArrayMap() | Constructs a new ArrayMap with default initial capacity. |
ArrayMap(int initialCapacity) | Constructs a new ArrayMap with the given initial capacity. |
Implementation Details¶
Requirements¶
- All methods must run in time, where is the size of the map.
size()
anditerator()
must run in 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 atSimpleEntry.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)
underjava.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 theChainedHashMap
! SimpleEntry<K, V>
implementsEntry<K, V>
, so you can simply return your map’sSimpleEntry
objects when implementingIterator.next
.