Using an Array to Implement a Map

ArrayMap stores the pairs in a backing array with a size counter, as in ArrayList. Each filled slot holds an Entry object with a key and its value. We could instead keep two parallel arrays, one for keys and one for values. One array of entries is simpler: moving an entry moves the key and its value together, and there is only one array to grow.

Operations and Complexity

As in LinkedMap, size() is $O (1)$ . Every other operation starts with a linear search for the key over the filled part of the array, so every other operation is $O (n)$ .

put(key, value): After the search, a new key is appended at the end of the array, $O (1)$ amortized. As with ArraySet’s add, the $O (n)$ search on every call means the whole put is not marked amortized.

remove(key): A map has no order among its entries, so after the search we use the swap-with-last removal from ArraySet instead of shifting. That step is $O (1)$ .

The two implementations differ in memory the same way LinkedSet and ArraySet did: the array carries spare capacity, and the linked list carries a next reference on every node.

You might be thinking that we could do better. Keeping the array sorted by key lets binary search find a key in $O (lo g n)$ . Move-to-front for LinkedMap and transpose for ArrayMap can speed up skewed lookups. All three work for a map the same way they did for a set, so I will not repeat them here.