Four Maps, Side by Side

We now have four implementations of the Map contract: the linked list and the unsorted array from the map chapter, the sorted array from that chapter’s practice, and the tree from this chapter. Here are their costs side by side:

Operation	`LinkedMap`	`ArrayMap`	`SortedArrayMap`	`TreeMap`
`size`	$O (1)$	$O (1)$	$O (1)$	$O (1)$
`get`	$O (n)$	$O (n)$	$O (lo g n)$	$O (lo g n)$
`containsKey`	$O (n)$	$O (n)$	$O (lo g n)$	$O (lo g n)$
`put`	$O (n)$	$O (n)$	$O (n)$	$O (lo g n)$
`remove`	$O (n)$	$O (n)$	$O (n)$	$O (lo g n)$

TreeMap is the only column with every operation at $O (lo g n)$ or better. The sorted array and the tree both keep their keys in order, but only the tree keeps that order without shifting entries when the map changes.

The overhead of TreeMap

Each TreeMap node stores a key, a value, two child references, and a cached height. A LinkedMap node stores only a key, a value, and one next reference. So a TreeMap node takes more memory.

Every put and remove also does bookkeeping that the other maps skip: refreshing heights, checking balance factors, and rotating. This bookkeeping does not change the $O (lo g n)$ bound, but it adds work to every change.

Choosing among them

Looked up far more often than changed: a SortedArrayMap. Its lookups are $O (lo g n)$ . Its changes are $O (n)$ , but they are rare.
Both looked up and changed often: TreeMap.
Keys with no natural order, or a map that stays small: LinkedMap or ArrayMap. They ask only for equals on keys, not a Comparable ordering, and when $n$ is small the difference between $O (n)$ and $O (lo g n)$ does not matter.