skip to content

What navigation methods does NavigableMap add, and what does each of floorKey, ceilingKey, lowerEntry, and higherEntry return?

level: middleimportance: must knowfreq 68%

answer

  1. floor ≤ k, ceiling ≥ k (inclusive)
  2. lower < k, higher > k (strict)
  3. *Key returns key, *Entry returns Map.Entry
  4. null when no such key exists
  5. Lookups O(log n) on TreeMap's red-black tree

basics

~20 s

NavigableMap adds nearest-key lookups. For a key k: floorKey returns the largest key ≤ k, ceilingKey the smallest key ≥ k, lowerKey the largest key strictly < k, higherKey the smallest key strictly > k. The *Entry versions return the whole entry, or null if none exists.

solid answer

~50 s

NavigableMap (implemented by TreeMap) adds nearest-neighbour and endpoint navigation on the sorted keys. The four relative lookups, given a key k, are: floor = greatest key ≤ k (inclusive below), ceiling = least key ≥ k (inclusive above), lower = greatest key strictly < k (exclusive below), higher = least key strictly > k (exclusive above). Each comes in a *Key form returning just the key and a *Entry form returning the Map.Entry; both return null when no such key exists. It also adds firstEntry/lastEntry, pollFirstEntry/pollLastEntry (read-and-remove), descendingMap/descendingKeySet (reverse views), and the inclusive-bound range views headMap/tailMap/subMap with a boolean to include or exclude the endpoint. On TreeMap the lookups and first/last/poll methods run in O(log n); creating a view is O(1). Returned entries are snapshots, so setValue throws. The mnemonic: floor/ceiling are inclusive (≤ / ≥), lower/higher are strict (< / >).

go deeper

for a junior

Knows TreeMap can find the nearest key and that there are floor/ceiling-style methods.

for a middle

Correctly states inclusive vs strict semantics for all four lookups and the Key vs Entry/null behaviour.

for a senior

Adds poll/descending/endpoint methods, the firstKey-throws-vs-firstEntry-returns-null gotcha, and concrete use cases like as-of queries.

for a principal

Designs APIs/algorithms on these primitives (interval trees, scheduling, versioned lookups) and reasons about view semantics and concurrency.

## Why NavigableMap exists Because TreeMap keeps keys **sorted**, it can answer questions an unordered map cannot: 'what is the nearest key at or below 50?' or 'give me every entry between 10 and 20'. These live on the **NavigableMap** interface (which extends SortedMap), and TreeMap answers the nearest-key questions in **O(log n)** by descending its balanced tree; a range walk adds the size of the slice. ## The four relative lookups Given a query key `k`, picture the sorted keys on a number line: - **floorKey(k)** → the **greatest key ≤ k** ('floor' = round down, *inclusive*). For keys {10,20,30}, floorKey(25)=20, floorKey(20)=20. - **ceilingKey(k)** → the **least key ≥ k** ('ceiling' = round up, *inclusive*). ceilingKey(25)=30, ceilingKey(20)=20. - **lowerKey(k)** → the **greatest key strictly < k** (*exclusive*). lowerKey(20)=10. - **higherKey(k)** → the **least key strictly > k** (*exclusive*). higherKey(20)=30. The distinction is inclusivity: **floor/ceiling include k itself; lower/higher exclude it.** ## Key form vs Entry form Each lookup has two variants: - `floorKey(k)` returns the **key** (or null). - `floorEntry(k)` returns the whole **Map.Entry** (key + value) (or null). Use the Entry form when you also need the value; the Key form when you only need the key. **Both return null when no matching key exists** — e.g. lowerKey(10) on {10,20,30} is null because nothing is strictly below 10. Entries from these methods, and from `firstEntry`, `lastEntry` and the poll methods below, are **snapshots**: `setValue` on one throws `UnsupportedOperationException`, so change a value with `put`. Under natural ordering a null `k` throws `NullPointerException` once the map has entries; on an empty map these lookups compare nothing and return null. ## Endpoint and poll methods - `firstEntry()` / `lastEntry()` — smallest / largest entry (null if empty). - `firstKey()` / `lastKey()` (from SortedMap) — but these **throw NoSuchElementException** when empty, unlike firstEntry/lastEntry which return null. (A common gotcha.) - `pollFirstEntry()` / `pollLastEntry()` — return **and remove** the smallest/largest entry; great for priority-queue-like draining. - Since **Java 21** the `firstEntry`/`lastEntry`/poll methods are also declared on `SequencedMap`. ## Reverse views - `descendingMap()` — a view of the same map with reversed ordering. - `descendingKeySet()` / `navigableKeySet()` — navigable key-set views. These are **views**, not copies: `descendingMap()` writes through both ways, and the key-set views reflect the map and support removal but not `add`. ## Range views (covered more in subMap/headMap/tailMap) `headMap(k, inclusive)`, `tailMap(k, inclusive)`, `subMap(from, fromIncl, to, toIncl)` return sorted sub-views with explicit endpoint inclusivity. ## Mental model Think of the keys as a ruler. floor/ceiling snap **to-or-toward** k inclusively; lower/higher step **past** k exclusively. All of these are why people reach for TreeMap: time-series 'value as of timestamp T' (floorEntry), autocomplete ranges (subMap), nearest-match lookups.

  • On a TreeMap with keys {10,20,30}, what do floorKey(20) and lowerKey(20) return?
    floorKey(20)=20 (inclusive, ≤), lowerKey(20)=10 (strict, <).
  • What is a real use case for floorEntry?
    Time-series 'as-of' lookups: a TreeMap keyed by timestamp, floorEntry(t) gives the most recent record at or before time t.

  • Swapping inclusive (floor/ceiling) with strict (lower/higher)
  • Thinking floorKey throws when absent (it returns null)
  • Confusing floorEntry returning null with firstKey throwing NoSuchElementException
  • Assuming these methods are O(n)
  • Calling setValue on a floorEntry result; it is a snapshot and throws.

NavigableMap
Java 1.6

Assumes JDK 27; NavigableMap.java is byte-identical at JDK 25. NavigableMap dates from 1.6, and SequencedMap, which also carries the first, last and poll methods, from Java 21, so 25 LTS behaves the same.

context