skip to content

What is a TreeMap in Java and how does it differ from HashMap and LinkedHashMap?

level: juniorimportance: must knowfreq 75%

answer

  1. Sorted keys, red-black tree, O(log n)
  2. HashMap=average O(1), no guaranteed order; LinkedHashMap=insertion order; TreeMap=sorted
  3. No null key under natural ordering
  4. Natural ordering (Comparable) OR Comparator
  5. Unlocks range + nearest queries (NavigableMap)

basics

~20 s

A TreeMap is a Map that keeps its keys sorted. HashMap has no guaranteed order and is faster for plain get/put; LinkedHashMap keeps insertion order. TreeMap sorts keys (natural order or a Comparator), with O(log n) get, put and remove.

solid answer

~40 s

TreeMap is a sorted Map implementation. Unlike HashMap (no guaranteed ordering, average O(1) operations) and LinkedHashMap (insertion or access order, O(1)), TreeMap stores keys in sorted order and gives O(log n) get/put/remove because it is backed by a red-black tree. Ordering comes from the keys' natural ordering (Comparable) or a Comparator passed to the constructor. Because it is sorted it implements NavigableMap/SortedMap, so you get range views (headMap/tailMap/subMap) and nearest-key lookups (floorKey/ceilingKey). Choose TreeMap when you need keys iterated in order or need range/nearest queries; choose HashMap when you only need fast key lookups and order does not matter. TreeMap does not allow a null key (it would fail comparison) unless a null-tolerant Comparator is supplied.

go deeper

for a junior

Knows TreeMap keeps keys sorted and HashMap does not, and that TreeMap is backed by a tree.

for a middle

Can state the O(log n) vs average O(1) tradeoff, that ordering comes from Comparable or Comparator, and the null-key restriction.

for a senior

Explains the red-black tree backing, when range/nearest queries justify the cost, and the lookup-cost differences vs HashMap.

for a principal

Frames the choice as a data-access-pattern decision, weighs TreeMap vs alternative ordered structures (skip lists, sorted arrays, external indexes) and concurrency implications at scale.

## What a Map is A **Map** is a data structure storing **key → value** pairs where each key is unique. `get(key)` returns the value, `put(key, value)` inserts or overwrites. Java's `java.util.Map` is the interface; the common implementations differ in *ordering* and *performance*. ## The three implementations - **HashMap**: stores entries in buckets indexed by the key's `hashCode()`. Iteration order is unspecified and may change over time. Average get/put/remove is **O(1)** (constant time). - **LinkedHashMap**: a HashMap that also threads entries on a doubly linked list, so iteration follows **insertion order** (or access order if configured). Still **O(1)**. - **TreeMap**: keeps keys in **sorted order**. Backed by a **red-black tree** (a self-balancing binary search tree), so get/put/remove are **O(log n)** — slower than O(1) but the keys are always ordered. ## What 'sorted' means here Keys are ordered either by their **natural ordering** — the key type implements `Comparable<T>` and defines `compareTo` (e.g. Integer, String) — or by a **Comparator** you pass to the TreeMap constructor. Iterating a TreeMap visits keys ascending. `firstKey()` gives the smallest, `lastKey()` the largest. Since Java 21 `TreeMap` is also a `SequencedMap`, whose methods include `firstEntry()` and `reversed()`. ## Big-O recap 'O(1)' = time does not grow with size. 'O(log n)' = time grows with the logarithm of size (doubling the data adds one extra step). So for 1,000,000 entries a TreeMap lookup averages ~20 comparisons and can never need more than ~40, the red-black height bound, while a HashMap lookup is typically one bucket probe. ## Null keys HashMap allows one null key. TreeMap **does not** allow a null key with natural ordering, because natural ordering cannot compare null, so `put` throws `NullPointerException`, even on an empty map. (A custom null-tolerant Comparator, such as `Comparator.nullsFirst`, can change this.) All three allow null *values*. ## When to pick which - Only need fast lookup, order irrelevant → **HashMap**. - Need to iterate in insertion order → **LinkedHashMap**. - Need keys in sorted order, or range queries (everything between A and B), or nearest-key lookups → **TreeMap**. That last capability — range and nearest-neighbour queries — is what TreeMap alone among these three offers via the NavigableMap interface, and is usually the deciding reason to choose it.

  • Can you put a null key into a TreeMap?
    Not with natural ordering: put throws NullPointerException because null cannot be compared. Only a custom Comparator that tolerates null would allow it. Null values are always fine.
  • Roughly how many comparisons does a TreeMap lookup need for a million entries?
    About 20 on average, since log2(1,000,000) ≈ 20, and at most about 40, because a red-black tree bounds its height by 2·log2(n+1) rather than balancing perfectly.

  • Claiming TreeMap is O(1) like HashMap
  • Saying TreeMap keeps insertion order (that is LinkedHashMap)
  • Thinking TreeMap allows a null key by default
  • Believing TreeMap is always the best Map choice

TreeMap
Java 1.2
NavigableMap
Java 1.6

Assumes JDK 27. TreeMap has been a SequencedMap since Java 21, so 25 LTS matches; TreeMap's only code change from 25 to 27 is a null check on an empty view's key-set spliterator.

context