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=O(1) no 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 order and is faster for plain get/put; LinkedHashMap keeps insertion order. TreeMap sorts keys (natural order or a Comparator) and is a bit slower.

solid answer

~40 s

TreeMap is a sorted Map implementation. Unlike HashMap (no 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 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 memory/overhead 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 (effectively random). 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. ## 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 is ~20 comparisons, a HashMap lookup is ~1 bucket probe. ## Null keys HashMap allows one null key. TreeMap **does not** allow a null key with natural ordering, because it must call `compareTo` on the key and that throws `NullPointerException`. (A custom null-tolerant Comparator 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 uniquely 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 — it calls compareTo on the key and throws NullPointerException. 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 log2(1,000,000) ≈ 20, because it descends a balanced tree of depth ~log n.

saying these in an interview costs you the question

  • 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

context

resolving links…