Navigating Java Maps: TreeMap vs. HashMap vs. Linked HashMap

Computer science should really just be called the art of the tradeoff. For any given task there are always a multitude of solutions, and each may be “right” depending on the given context. That context is what will help determine which tradeoffs are preferable, and which ones to stay away from.

Storing key/value pairs is a common programming task, meaning that it of course involves tradeoffs. Your gut instinct might lead you to choose whichever data structure offers the best performance in terms of time-complexity, but that’s just one piece of the equation. Do you need to keep your data sorted? Will the collection constantly grow and shrink? What about unique values, or duplicate keys? As much as you can, try to map out how you intend to interact with the data you’ll be storing, and choose the data structure that best suits your needs.

To illustrate these differences let’s explore three closely related Java structures for storing key/value pairs: HashMap, Linked HashMap, and TreeMap.

Structure

A TreeMap in Java is implemented as a Red-Black tree, which is a type of self-balancing binary search tree. This means that an extra bit is added to each node which tags the node as black or red. These tags are what allow the tree to balance itself when elements are…