Definition
- Closest-match methods –
floorKey(k)returns the greatest key less than or equal to k;ceilingKey(k)returns the smallest key greater than or equal to k;lowerKey(k)andhigherKey(k)are strictly less and strictly greater - Range views –
headMap(toKey),tailMap(fromKey),subMap(fromKey, toKey)return live views backed by the original map; modifications to the view affect the original - Poll methods –
pollFirstEntry()andpollLastEntry()atomically remove and return the smallest or largest entry - Reverse views –
descendingMap()anddescendingKeySet()provide reverse-order iteration without copying - Implementations –
TreeMap(NavigableMap) andTreeSet(NavigableSet), both backed by red-black trees with O(log n) operations
At National Bank of India, all fixed deposit certificates are stored in a sorted filing cabinet ordered by maturity date. Rajesh asks: "What is the nearest maturity date on or before 2025-06-15?" That is floorKey. "What is the nearest maturity date on or after 2025-06-15?" That is ceilingKey. "Give me all certificates maturing before 2025-01-01." That is headMap. The clerk does not copy the files; instead, the clerk opens a view into the cabinet. Any new certificate filed in that range automatically appears in the view.
Understanding the Concepts
What are NavigableMap and NavigableSet?
NavigableMap is an interface that extends SortedMap with navigation methods for finding the closest match to a given key. NavigableSet does the same for sets. The standard implementations are TreeMap and TreeSet, both backed by red-black trees.
These collections are useful when you need sorted data with efficient nearest-neighbour lookups, range queries, or priority-based retrieval.
package com.bank.demo;
import java.math.BigDecimal;
import java.util.NavigableMap;
import java.util.TreeMap;
public class NavigableMapBasicDemo {
public static void main(String[] args) {
NavigableMap<String, BigDecimal> accounts = new TreeMap<>();
accounts.put("ACC-100", new BigDecimal("50000"));
accounts.put("ACC-200", new BigDecimal("75000"));
accounts.put("ACC-300", new BigDecimal("120000"));
accounts.put("ACC-400", new BigDecimal("200000"));
accounts.put("ACC-500", new BigDecimal("500000"));
System.out.println("All accounts: " + accounts);
System.out.println("First: " + accounts.firstEntry());
System.out.println("Last: " + accounts.lastEntry());
}
}
All accounts: {ACC-100=50000, ACC-200=75000, ACC-300=120000, ACC-400=200000, ACC-500=500000}
First: ACC-100=50000
Last: ACC-500=500000
How do floor, ceiling, lower, and higher work?
These four methods find the closest match to a given key. The difference is whether the match includes the key itself (floor/ceiling) or excludes it (lower/higher).
| Method | Returns | Includes key itself | |---|---|---| | floorKey(k) | Greatest key <= k | Yes | | ceilingKey(k) | Smallest key >= k | Yes | | lowerKey(k) | Greatest key < k | No (strictly less) | | higherKey(k) | Smallest key > k | No (strictly greater) |
Each method also has an Entry variant (floorEntry, ceilingEntry, lowerEntry, higherEntry) that returns the full key-value pair.
package com.bank.demo;
import java.math.BigDecimal;
import java.util.NavigableMap;
import java.util.TreeMap;
public class ClosestMatchDemo {
public static void main(String[] args) {
NavigableMap<String, BigDecimal> accounts = new TreeMap<>();
accounts.put("ACC-100", new BigDecimal("50000"));
accounts.put("ACC-200", new BigDecimal("75000"));
accounts.put("ACC-300", new BigDecimal("120000"));
accounts.put("ACC-400", new BigDecimal("200000"));
accounts.put("ACC-500", new BigDecimal("500000"));
String searchKey = "ACC-250";
System.out.println("Searching for: " + searchKey);
System.out.println("floorKey (<=): " + accounts.floorKey(searchKey));
System.out.println("ceilingKey (>=): " + accounts.ceilingKey(searchKey));
System.out.println("lowerKey (<): " + accounts.lowerKey(searchKey));
System.out.println("higherKey (>): " + accounts.higherKey(searchKey));
// When the key exists exactly
String exactKey = "ACC-300";
System.out.println("\nSearching for exact: " + exactKey);
System.out.println("floorKey (<=): " + accounts.floorKey(exactKey));
System.out.println("lowerKey (<): " + accounts.lowerKey(exactKey));
}
}
Searching for: ACC-250
floorKey (<=): ACC-200
ceilingKey (>=): ACC-300
lowerKey (<): ACC-200
higherKey (>): ACC-300
Searching for exact: ACC-300
floorKey (<=): ACC-300
lowerKey (<): ACC-200
How do headMap, tailMap, and subMap work?
Range views return a live view of a portion of the map. Changes to the view are reflected in the original map, and changes to the original within the range are reflected in the view.
The one-argument versions use default bounds: headMap(toKey) is exclusive of toKey, tailMap(fromKey) is inclusive of fromKey. The two-argument overloads let you control inclusivity.
package com.bank.demo;
import java.math.BigDecimal;
import java.util.NavigableMap;
import java.util.SortedMap;
import java.util.TreeMap;
public class RangeViewDemo {
public static void main(String[] args) {
NavigableMap<String, BigDecimal> accounts = new TreeMap<>();
accounts.put("ACC-100", new BigDecimal("50000"));
accounts.put("ACC-200", new BigDecimal("75000"));
accounts.put("ACC-300", new BigDecimal("120000"));
accounts.put("ACC-400", new BigDecimal("200000"));
accounts.put("ACC-500", new BigDecimal("500000"));
// headMap: all keys < ACC-300 (exclusive by default)
SortedMap<String, BigDecimal> head = accounts.headMap("ACC-300");
System.out.println("headMap(<ACC-300): " + head);
// tailMap: all keys >= ACC-300 (inclusive by default)
SortedMap<String, BigDecimal> tail = accounts.tailMap("ACC-300");
System.out.println("tailMap(>=ACC-300): " + tail);
// subMap with inclusive bounds
NavigableMap<String, BigDecimal> sub = accounts.subMap(
"ACC-200", true, "ACC-400", true
);
System.out.println("subMap[ACC-200..ACC-400]: " + sub);
// Views are BACKED by original
head.put("ACC-050", new BigDecimal("10000"));
System.out.println("Original after view.put: " + accounts.get("ACC-050"));
}
}
headMap(<ACC-300): {ACC-100=50000, ACC-200=75000}
tailMap(>=ACC-300): {ACC-300=120000, ACC-400=200000, ACC-500=500000}
subMap[ACC-200..ACC-400]: {ACC-200=75000, ACC-300=120000, ACC-400=200000}
Original after view.put: 10000
How do pollFirstEntry and pollLastEntry work?
These methods atomically remove and return the smallest or largest entry. They are useful for priority-based processing where you always consume the next item in order.
package com.bank.demo;
import java.math.BigDecimal;
import java.util.Map;
import java.util.TreeMap;
public class PollEntryDemo {
public static void main(String[] args) {
TreeMap<BigDecimal, String> pendingTransfers = new TreeMap<>();
pendingTransfers.put(new BigDecimal("500000"), "TRF-001: Rajesh to Priya");
pendingTransfers.put(new BigDecimal("10000"), "TRF-002: Priya to savings");
pendingTransfers.put(new BigDecimal("250000"), "TRF-003: Pankaj salary");
System.out.println("Processing smallest transfer first:");
while (!pendingTransfers.isEmpty()) {
Map.Entry<BigDecimal, String> entry = pendingTransfers.pollFirstEntry();
System.out.println(" Amount: " + entry.getKey() + " - " + entry.getValue());
}
System.out.println("Remaining: " + pendingTransfers.size());
}
}
Processing smallest transfer first:
Amount: 10000 - TRF-002: Priya to savings
Amount: 250000 - TRF-003: Pankaj salary
Amount: 500000 - TRF-001: Rajesh to Priya
Remaining: 0
How is NavigableMap different from SortedMap?
| Feature | SortedMap | NavigableMap |
|---|---|---|
| Closest-match | Not available | floorKey, ceilingKey, lowerKey, higherKey |
| Poll methods | Not available | pollFirstEntry, pollLastEntry |
| Descending view | Not available | descendingMap, descendingKeySet |
| Inclusive bounds | headMap(to) exclusive only | headMap(to, inclusive) |
| Introduced in | Java 2 | Java 6 |
package com.bank.demo;
import java.util.NavigableMap;
import java.util.TreeMap;
public class DescendingViewDemo {
public static void main(String[] args) {
NavigableMap<String, String> accounts = new TreeMap<>();
accounts.put("ACC-100", "Rajesh");
accounts.put("ACC-200", "Priya");
accounts.put("ACC-300", "Pankaj");
System.out.println("Ascending: " + accounts);
System.out.println("Descending: " + accounts.descendingMap());
}
}
Ascending: {ACC-100=Rajesh, ACC-200=Priya, ACC-300=Pankaj}
Descending: {ACC-300=Pankaj, ACC-200=Priya, ACC-100=Rajesh}
What are common mistakes?
Mistake: Inserting an out-of-range key into a range view
import java.util.*;
// WRONG: adding a key outside the view's range
NavigableMap<String, String> map = new TreeMap<>();
map.put("ACC-200", "Rajesh");
map.put("ACC-300", "Priya");
SortedMap<String, String> head = map.headMap("ACC-300"); // keys < ACC-300
head.put("ACC-400", "Pankaj"); // IllegalArgumentException! ACC-400 >= ACC-300
// CORRECT: add to the original map, not the restricted view
map.put("ACC-400", "Pankaj");
System.out.println(map); // {ACC-200=Rajesh, ACC-300=Priya, ACC-400=Pankaj}
Mistake: Forgetting that headMap(key) is exclusive by default
// WRONG assumption: headMap includes the boundary key
TreeMap<Integer, String> balances = new TreeMap<>();
balances.put(100, "Low");
balances.put(200, "Medium");
balances.put(300, "High");
SortedMap<Integer, String> head = balances.headMap(200);
System.out.println(head); // {100=Low} -- 200 is EXCLUDED
// CORRECT: use the two-argument version for inclusive
NavigableMap<Integer, String> headInclusive = balances.headMap(200, true);
System.out.println(headInclusive); // {100=Low, 200=Medium}
What are the edge cases?
package com.bank.demo;
import java.util.NavigableMap;
import java.util.TreeMap;
public class NavigableEdgeCasesDemo {
public static void main(String[] args) {
NavigableMap<String, String> map = new TreeMap<>();
map.put("ACC-100", "Rajesh");
map.put("ACC-300", "Priya");
// Edge case 1: floor/ceiling when no match exists
System.out.println("floorKey below all: " + map.floorKey("ACC-050"));
System.out.println("ceilingKey above all: " + map.ceilingKey("ACC-999"));
// Edge case 2: pollFirstEntry on empty map
NavigableMap<String, String> empty = new TreeMap<>();
System.out.println("pollFirst on empty: " + empty.pollFirstEntry());
// Edge case 3: subMap where from > to
try {
map.subMap("ACC-300", true, "ACC-100", true);
} catch (IllegalArgumentException e) {
System.out.println("from > to: " + e.getMessage());
}
}
}
floorKey below all: null
ceilingKey above all: null
pollFirst on empty: null
from > to: fromKey > toKey
When should you use NavigableMap?
Use NavigableMap (TreeMap) when you need sorted keys with efficient closest-match lookups, range queries, or priority-based consumption. Common banking scenarios include finding the nearest interest rate tier for a balance, selecting all transactions in a date range, and processing pending transfers in order of amount.
When should you NOT use NavigableMap?
Do not use TreeMap when you only need key-value lookups by exact key. HashMap provides O(1) average-case performance compared to TreeMap's O(log n). If you do not need sorting or navigation, HashMap is the better choice.
What should a senior engineer know?
- O(log n) for all operations. TreeMap uses a red-black tree internally. Every get, put, floor, ceiling, and range-view creation is O(log n).
- Comparator vs natural ordering. TreeMap can use a custom Comparator. If no comparator is provided, keys must implement Comparable.
- ConcurrentSkipListMap. For concurrent scenarios, use
ConcurrentSkipListMap, which implements NavigableMap with lock-free reads and O(log n) writes. - Range views are O(1) to create because they are just window objects pointing into the tree. Iterating the view is O(k + log n) where k is the number of elements in the range.
What are common interview follow-up questions?
- "What is the difference between floorKey and lowerKey?" : floorKey is less than or equal to (inclusive), lowerKey is strictly less than (exclusive).
- "Are headMap/tailMap copies or views?" : Views. They are backed by the original map. Changes propagate both ways.
- "What is the time complexity of TreeMap operations?" : O(log n) for get, put, remove, floor, ceiling, lower, higher.
- "Can you use TreeMap for concurrent access?" : No. Use ConcurrentSkipListMap for a concurrent NavigableMap.
Visual Overview
NavigableMap Closest-Match Methods
==================================
Keys in TreeMap: ACC-100, ACC-200, ACC-300, ACC-400, ACC-500
Search key: ACC-250 (does not exist)
┌─────────────────────────────────────────────┐
│ floorKey(ACC-250) -> ACC-200 (<=, incl.) │
│ ceilingKey(ACC-250) -> ACC-300 (>=, incl.) │
│ lowerKey(ACC-250) -> ACC-200 (<, strict) │
│ higherKey(ACC-250) -> ACC-300 (>, strict) │
└─────────────────────────────────────────────┘
Search key: ACC-300 (exists)
┌─────────────────────────────────────────────┐
│ floorKey(ACC-300) -> ACC-300 (<=, incl.) │
│ ceilingKey(ACC-300) -> ACC-300 (>=, incl.) │
│ lowerKey(ACC-300) -> ACC-200 (<, strict) │
│ higherKey(ACC-300) -> ACC-400 (>, strict) │
└─────────────────────────────────────────────┘
Range Views (live-backed):
┌───────────────────────────────────────────────────────┐
│ headMap(ACC-300) -> {ACC-100, ACC-200} │
│ tailMap(ACC-300) -> {ACC-300, ACC-400, ACC-500} │
│ subMap(ACC-200,ACC-400)-> {ACC-200, ACC-300} │
└───────────────────────────────────────────────────────┘
Changes in view <-> changes in original (both ways)
Key Takeaway
NavigableMap and NavigableSet extend the sorted interfaces with powerful navigation methods. The closest-match methods (floorKey, ceilingKey, lowerKey, higherKey) find the nearest key relative to a search key, while range views (headMap, tailMap, subMap) return live windows into the underlying tree. These views are not copies: adding an entry to a view also adds it to the original, and vice versa.
The poll methods (pollFirstEntry, pollLastEntry) atomically remove and return the smallest or largest entry, making TreeMap usable as a simple priority structure. The descending views provide reverse-order iteration without creating a new collection.
In the National Bank of India's fixed deposit system, Pankaj used a TreeMap keyed by maturity date. Finding the nearest maturing deposit was a single ceilingKey call. Selecting all deposits maturing in a quarter was a subMap view. Processing matured deposits used pollFirstEntry in a loop, consuming them in chronological order.
Remember one sentence: NavigableMap (TreeMap) provides O(log n) closest-match lookups with floor, ceiling, lower, and higher, plus live-backed range views that propagate changes both ways.
---