skip to content

How do headMap, tailMap, and subMap work, and what does it mean that they return live views with inclusive/exclusive bounds?

level: seniorimportance: should knowfreq 50%

answer

  1. headMap=below, tailMap=at/above, subMap=between
  2. SortedMap overloads: subMap is [from,to), head exclusive, tail inclusive
  3. NavigableMap overloads add explicit inclusive booleans
  4. Live view, not a copy — writes go through both ways
  5. Out-of-range put throws IllegalArgumentException

basics

~20 s

headMap, tailMap and subMap return live views of a TreeMap's key range, not copies: keys below a bound, at or above a bound, or between two bounds. Boolean overloads set each endpoint's inclusivity, and changes flow both ways.

solid answer

~50 s

headMap(toKey), tailMap(fromKey), and subMap(fromKey, toKey) return sorted sub-maps restricted by key range. The original SortedMap overloads are half-open: headMap is exclusive of the bound, tailMap inclusive, subMap [from, to). The NavigableMap overloads add explicit booleans — headMap(to, inclusive), tailMap(from, inclusive), subMap(from, fromIncl, to, toIncl) — so you control each endpoint. Crucially these are **live views** backed by the original map: reads reflect later changes and writes through them update the backing map. Inserting a key outside a view's range throws IllegalArgumentException ('key out of range'). Creating a view is O(1) because it just holds bounds; it keeps no position, so each traversal finds the slice again in O(log n), and size() on a bounded view counts by walking it. Typical uses: paginating sorted data, 'events between two timestamps', or trimming with pollFirstEntry/pollLastEntry. Because they are views, mutating the backing map while iterating a view risks ConcurrentModificationException, same as any TreeMap iteration.

go deeper

for a junior

Knows TreeMap can return a portion of keys by range using headMap/tailMap/subMap.

for a middle

States the half-open default for subMap and that newer overloads take inclusivity booleans.

for a senior

Explains the live-view semantics (write-through, out-of-range IllegalArgumentException), O(1) creation with O(log n + k) size(), and fail-fast iteration.

for a principal

Designs range-query features on these views, weighs view vs snapshot tradeoffs, and chooses ConcurrentSkipListMap for concurrent navigable access.

## The three range operations Because TreeMap is sorted, you can ask for a contiguous **slice** of keys: - **headMap** — entries with keys *before* a bound (the 'head' / low end). - **tailMap** — entries with keys *at or after* a bound (the 'tail' / high end). - **subMap** — entries with keys *between* two bounds. ## Two sets of overloads (inclusivity) There are two flavours, and mixing them up is a classic bug: **SortedMap (older, fixed inclusivity):** - `headMap(toKey)` → keys **< toKey** (toKey *excluded*). - `tailMap(fromKey)` → keys **≥ fromKey** (fromKey *included*). - `subMap(fromKey, toKey)` → keys in **[fromKey, toKey)** — from included, to excluded (half-open, like substring). **NavigableMap (newer, explicit booleans):** - `headMap(toKey, inclusive)` - `tailMap(fromKey, inclusive)` - `subMap(fromKey, fromInclusive, toKey, toInclusive)` Here you state each endpoint's inclusivity yourself, e.g. `subMap(10, true, 20, true)` for [10,20]. ## 'Live view' — the critical concept A **view** is not a copy. The returned sub-map is a thin object holding the original map plus the range bounds; it has **no data of its own**. Consequences: - **Reads are live**: if you later `put` a key into the backing map that falls inside the view's range, it appears in the view. - **Writes write through**: `put`/`remove` on the view modify the **backing** map (and vice-versa). - **Out-of-range inserts throw**: `put`ting a key outside the view's range throws `IllegalArgumentException` ('key out of range'), and so do `putIfAbsent` and `merge`, and `computeIfAbsent` unless its function returns null. `get` and `remove` on such a key just return null. - **Bounds are fixed and checked**: `subMap(40, 20)` throws `IllegalArgumentException` ('fromKey > toKey'), and a view of a view must stay inside its parent's range. - Creating a view is **O(1)**: it stores the bounds, makes a few comparisons at most to check them (one for a view of the whole map), and copies nothing. It keeps no position, so each iterator, `firstKey` or `isEmpty()` call finds its place again in O(log n). - **`size()` on a bounded view is O(log n + k)** for a slice of k entries: it finds the slice's ends, counts by walking between them, and caches the count until the backing map next changes. `isEmpty()` only has to find the first key in range. If you want an independent snapshot, copy it: `new TreeMap<>(map.subMap(...))`. ## Iteration and ConcurrentModificationException Views iterate the underlying tree in order. Structurally modifying the backing map during iteration (other than via the iterator's own `remove`) triggers a **fail-fast ConcurrentModificationException** — the same best-effort contract as iterating the whole TreeMap. The check reads the whole map's modification count, so a `put` outside the view's range fails the iterator too. Across threads, use `ConcurrentSkipListMap` (a concurrent NavigableMap with weakly consistent iterators) or hold a lock around the whole traversal. **Since JDK 27** the key-set spliterator and stream of an empty view throw `NullPointerException` on a null action, as the specification requires; on 25 LTS they returned false or completed normally. ## Worked example Keys {10,20,30,40}: - `headMap(30)` → {10,20} (30 excluded). - `headMap(30, true)` → {10,20,30}. - `tailMap(20)` → {20,30,40}. - `subMap(20, 40)` → {20,30} (half-open). - `subMap(20, true, 40, true)` → {20,30,40}. ## Why it matters Range views power time-window queries (events between t1 and t2), sorted pagination ('next 50 keys after X' via tailMap then limit), and efficient trimming (`pollFirstEntry` on a subMap). Each traversal starts with an O(log n) descent and then walks only the slice — far cheaper than filtering the whole map.

  • On keys {10,20,30,40}, what does subMap(20, 40) return and why?
    {20,30}. The two-arg SortedMap overload is half-open [from, to), so 20 is included and 40 is excluded.
  • How do you get an independent copy instead of a live view?
    Wrap it in a new TreeMap: new TreeMap<>(map.subMap(...)). That copies the entries so later changes to the original do not affect it.
  • What does size() cost on a bounded subMap?
    O(log n + k) for a slice of k entries: it finds the slice's ends, walks it, then caches the count until the backing map next changes. isEmpty() only has to find the first key in range, so prefer it for an emptiness check.

  • Thinking the returned sub-map is an independent copy
  • Assuming subMap(from,to) includes the to key (it's exclusive in the SortedMap overload)
  • Believing you can insert any key into a range view
  • Forgetting fail-fast ConcurrentModificationException applies to views too
  • Assuming size() on a bounded view is O(1).

SortedMap headMap, tailMap and subMap
Java 1.2
NavigableMap inclusive range overloads
Java 1.6

Assumes JDK 27. TreeMap's only code change from JDK 25 is that an empty view's key-set spliterator now throws NullPointerException on a null action, where on 25 LTS it returned false or completed normally; views otherwise behave the same.

context