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

They return sub-portions of the TreeMap by key range: headMap = keys below a bound, tailMap = keys at/above a bound, subMap = keys between two bounds. The overloads with a boolean let you include or exclude the endpoints. The result is a live view, not a copy — changes go both ways.

solid answer

~40 s

headMap(toKey), tailMap(fromKey), and subMap(fromKey, toKey) return sorted sub-maps restricted by key range. The legacy 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'). Views are O(log n) to create (they just hold bounds) and iterate the relevant slice. Typical uses: paginating sorted data, 'events between two timestamps', or trimming with pollFirst/pollLast. 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(log n) creation, 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 writes throw**: `put`ting a key outside the view's range throws `IllegalArgumentException` ('key out of range'). - Creating a view is **O(log n)** (it locates bounds lazily); it does not copy entries. 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 contract as iterating the whole TreeMap. Across threads you would need `ConcurrentSkipListMap` (a concurrent NavigableMap) instead. ## 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). They are O(log n) to start and stream 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.

saying these in an interview costs you the question

  • 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

context

resolving links…