When would you choose TreeMap over HashMap? — Cracked Java
// Java Collections Framework · TreeMap, NavigableMap, SortedMap
MidTheory

When would you choose TreeMap over HashMap?

Choose TreeMap when you need ordered iteration, range queries, nearest-match lookups, or a deterministic key order in output. Otherwise stick with HashMap — it's faster (O(1) vs O(log n)) and uses less memory per entry.

The decision matrix

OperationBestAverageWorstNote
get / put / removeHashMap: O(1) avgHashMap winsTreeMap: O(log n)Plain key lookup -> HashMap
iterate in key orderTreeMap: O(n)TreeMap winsHashMap: O(n log n) (sort)Sorted output -> TreeMap
range query [a, b)TreeMap: O(log n + k)TreeMap winsHashMap: O(n)TreeMap.subMap is built for this
nearest-match (floor/ceiling)TreeMap: O(log n)TreeMap winsHashMap: O(n)HashMap has no equivalent
memory per entryHashMap: smallerHashMap winsTreeMap: parent/left/right/colorTree entries are heavier

Pick TreeMap when…

  • You need deterministic iteration order. Logs, reports, JSON serialisation where consumers expect sorted keys. LinkedHashMap is an alternative if you want insertion order; TreeMap is the choice for natural or custom order.
  • You query by range or proximity. Time series, leaderboards, pricing tiers, IP ranges, geometric intervals. The subMap, floorEntry, and ceilingEntry methods are O(log n) and have no HashMap analogue.
  • You need to find the largest/smallest key quickly. firstKey/lastKey are O(log n) (root-to-leaf descent). On a HashMap, the equivalent is an O(n) scan.
  • You want a sorted output without explicitly sorting. treeMap.keySet() is already sorted; you save the O(n log n) sort step.

Stick with HashMap when…

  • You only do lookups by exact key. The constant-factor difference is real — HashMap is often 5-10x faster per operation in tight loops.
  • Keys don't have a natural order (or you don't want to define one). TreeMap requires either Comparable keys or a Comparator. HashMap only needs hashCode/equals.
  • You're optimising memory. TreeMap.Entry carries parent, left, right, color — three pointers and a boolean per entry, plus less array packing. For millions of entries, HashMap wins by a comfortable margin.

A worked example

// HashMap: O(n log n) to print in sorted order
Map<String, Integer> hm = new HashMap<>();
hm.put("banana", 2); hm.put("apple", 5); hm.put("cherry", 1);
hm.entrySet().stream()
    .sorted(Map.Entry.comparingByKey())
    .forEach(e -> System.out.println(e.getKey() + "=" + e.getValue()));

// TreeMap: O(n) — already sorted
Map<String, Integer> tm = new TreeMap<>(hm);
tm.forEach((k, v) -> System.out.println(k + "=" + v));

What about ConcurrentSkipListMap?

If you want TreeMap semantics in a concurrent setting, use ConcurrentSkipListMap. It implements the full NavigableMap API, is lock-free, and offers comparable O(log n) performance — at the cost of higher per-operation constants than TreeMap.

Mark your status