Contents

NavigableMap extends SortedMap with four proximity methods that answer nearest-key questions. floorKey(k) returns the greatest key ≤ k; ceilingKey(k) returns the smallest key ≥ k. lowerKey(k) and higherKey(k) are strictly exclusive versions. Each method also has an *Entry variant that returns the full Map.Entry<K,V> in one tree traversal — more efficient than calling the key variant and then get(). All return null when no qualifying key exists.

import java.util.*; // NavigableMap adds four proximity methods on top of SortedMap: // floorKey(k) — greatest key <= k (null if none) // ceilingKey(k) — smallest key >= k (null if none) // lowerKey(k) — greatest key < k (strictly less, null if none) // higherKey(k) — smallest key > k (strictly greater, null if none) // Each also has an *Entry variant returning Map.Entry<K,V> TreeMap<Integer, String> tm = new TreeMap<>(); tm.put(10, "ten"); tm.put(20, "twenty"); tm.put(30, "thirty"); tm.put(40, "forty"); tm.put(50, "fifty"); // --- Key-only variants --- System.out.println(tm.floorKey(25)); // 20 (greatest key <= 25) System.out.println(tm.floorKey(20)); // 20 (exact match counts) System.out.println(tm.floorKey(5)); // null (nothing <= 5) System.out.println(tm.ceilingKey(25)); // 30 (smallest key >= 25) System.out.println(tm.ceilingKey(30)); // 30 (exact match counts) System.out.println(tm.ceilingKey(55)); // null (nothing >= 55) System.out.println(tm.lowerKey(30)); // 20 (strictly < 30) System.out.println(tm.lowerKey(10)); // null (nothing strictly < 10) System.out.println(tm.higherKey(30)); // 40 (strictly > 30) System.out.println(tm.higherKey(50)); // null (nothing strictly > 50) // --- Entry variants (key + value together) --- Map.Entry<Integer, String> floorEntry = tm.floorEntry(25); Map.Entry<Integer, String> ceilingEntry = tm.ceilingEntry(25); System.out.println(floorEntry); // 20=twenty System.out.println(ceilingEntry); // 30=thirty // Practical: find the price tier for a spend amount TreeMap<Integer, String> priceTiers = new TreeMap<>(); priceTiers.put(0, "Free"); priceTiers.put(10, "Starter"); priceTiers.put(50, "Pro"); priceTiers.put(200, "Enterprise"); int spend = 75; Map.Entry<Integer, String> tier = priceTiers.floorEntry(spend); System.out.println("Tier: " + tier.getValue()); // Pro (greatest threshold <= 75) // Edge case: spend below all tiers Map.Entry<Integer, String> below = priceTiers.floorEntry(-1); System.out.println(below); // null — handle carefully All four methods return null when no qualifying key exists. The entry variants are more efficient than calling the key variant followed by get() because they retrieve the value in the same tree traversal.

NavigableMap provides three range-view methods that return a live, backed sub-map — not a copy. headMap(toKey) gives all entries with keys strictly less than toKey; pass a second boolean argument to make the boundary inclusive. tailMap(fromKey) gives entries from fromKey onward (inclusive by default). subMap(from, to) returns a half-open [from, to) window; the overload with two booleans lets you control inclusivity on both ends. Because these views are live, any write through the view updates the original map and vice versa.

TreeMap<Integer, String> tm = new TreeMap<>(); for (int i = 10; i <= 100; i += 10) { tm.put(i, "val-" + i); } // Keys: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 // headMap(toKey) — keys STRICTLY less than toKey (exclusive by default) SortedMap<Integer, String> head = tm.headMap(40); System.out.println(head.keySet()); // [10, 20, 30] // headMap(toKey, inclusive) — keys <= toKey when inclusive=true NavigableMap<Integer, String> headInclusive = tm.headMap(40, true); System.out.println(headInclusive.keySet()); // [10, 20, 30, 40] // tailMap(fromKey) — keys >= fromKey (inclusive by default) SortedMap<Integer, String> tail = tm.tailMap(70); System.out.println(tail.keySet()); // [70, 80, 90, 100] // tailMap(fromKey, inclusive) — keys > fromKey when inclusive=false NavigableMap<Integer, String> tailExclusive = tm.tailMap(70, false); System.out.println(tailExclusive.keySet()); // [80, 90, 100] // subMap(fromKey, toKey) — [fromKey, toKey) half-open by default SortedMap<Integer, String> sub = tm.subMap(30, 70); System.out.println(sub.keySet()); // [30, 40, 50, 60] // subMap with explicit inclusivity — fully closed [30, 70] NavigableMap<Integer, String> closedSub = tm.subMap(30, true, 70, true); System.out.println(closedSub.keySet()); // [30, 40, 50, 60, 70] // Views are LIVE — modifications reflect in the original map sub.put(35, "thirty-five"); // adds 35 to tm System.out.println(tm.containsKey(35)); // true // Modifications outside the view's range throw IllegalArgumentException // sub.put(80, "eighty"); // throws — 80 outside [30, 70) // Using headMap/tailMap for range counts long countBetween30And70 = tm.subMap(30, true, 70, true).size(); System.out.println("Keys in [30,70]: " + countBetween30And70); // 5 (30,35,40,50,60,70) Range views returned by headMap, tailMap, and subMap are live, backed views of the original map — not copies. Structural changes through the view modify the underlying map, and iterating the original map reflects keys added through the view. Create a copy with new TreeMap<>(sub) when you need an independent snapshot.

descendingMap() returns a live NavigableMap view with the key order reversed — iterating it goes from the largest key to the smallest. descendingKeySet() returns the same idea as a NavigableSet. All navigation methods (floor, ceiling, headMap, etc.) work on the descending view, but their semantics flip: firstKey() on the descending view returns what was the last key in the original. Both views are live — mutations are reflected in both directions.

TreeMap<String, Integer> scores = new TreeMap<>(); scores.put("Alice", 92); scores.put("Bob", 78); scores.put("Carol", 85); scores.put("Diana", 95); scores.put("Ethan", 71); // descendingMap — returns a live view with reversed key order NavigableMap<String, Integer> desc = scores.descendingMap(); desc.forEach((name, score) -> System.out.println(name + ": " + score)); // Ethan: 71 Diana: 95 Carol: 85 Bob: 78 Alice: 92 (Z→A) // descendingKeySet — NavigableSet of keys in reverse order NavigableSet<String> reverseKeys = scores.descendingKeySet(); System.out.println(reverseKeys.first()); // "Ethan" (last in natural order) System.out.println(reverseKeys.last()); // "Alice" (first in natural order) // Get top-3 scorers: sort by score descending, limit 3 scores.entrySet().stream() .sorted(Map.Entry.<String, Integer>comparingByValue().reversed()) .limit(3) .forEach(e -> System.out.println(e.getKey() + ": " + e.getValue())); // Diana: 95 Alice: 92 Carol: 85 // Reverse iteration over keys using descendingKeySet for (String name : scores.descendingKeySet()) { System.out.println(name + " = " + scores.get(name)); } // descendingMap is also NavigableMap — all navigation methods work in reverse NavigableMap<String, Integer> descView = scores.descendingMap(); System.out.println(descView.firstKey()); // Ethan (last alphabetically) System.out.println(descView.floorKey("Charlie")); // Carol (greatest reversed key <= Charlie) // headMap on a descending view: keys >= threshold in original order NavigableMap<String, Integer> afterCarol = descView.tailMap("Carol", true); System.out.println(afterCarol.keySet()); // [Carol, Bob, Alice] (descending, from Carol)

pollFirstEntry() atomically removes and returns the entry with the smallest key; pollLastEntry() does the same for the largest key. Both return null on an empty map — unlike firstEntry()/lastEntry() which only peek without removing. This makes them the idiomatic building block for a sorted task queue or priority scheduler: keep polling the front (or back) until empty or a condition is met.

// pollFirstEntry() — removes AND returns the entry with the smallest key // pollLastEntry() — removes AND returns the entry with the largest key // Return null if the map is empty (unlike firstEntry/lastEntry which throw) TreeMap<Integer, String> tasks = new TreeMap<>(); tasks.put(1, "critical"); tasks.put(5, "high"); tasks.put(10, "medium"); tasks.put(20, "low"); // Process tasks in priority order (lowest number = highest priority) Map.Entry<Integer, String> next; while ((next = tasks.pollFirstEntry()) != null) { System.out.println("Processing [" + next.getKey() + "] " + next.getValue()); } // Processing [1] critical // Processing [5] high // Processing [10] medium // Processing [20] low // (map is now empty) // pollLastEntry — useful for max-priority-first processing TreeMap<Integer, String> bids = new TreeMap<>(); bids.put(100, "buyer-A"); bids.put(150, "buyer-B"); bids.put(120, "buyer-C"); bids.put(200, "buyer-D"); // Accept highest bids first until budget exhausted int budget = 350; Map.Entry<Integer, String> topBid; while (!bids.isEmpty() && (topBid = bids.pollLastEntry()) != null) { if (budget >= topBid.getKey()) { budget -= topBid.getKey(); System.out.println("Accepted bid " + topBid.getKey() + " from " + topBid.getValue()); } else { System.out.println("Skipped bid " + topBid.getKey() + " — over budget"); break; } } // Accepted bid 200 from buyer-D // Accepted bid 150 from buyer-B (budget now 0) // Skipped bid 120 — over budget // firstEntry / lastEntry — peek without removing TreeMap<String, Integer> tm = new TreeMap<>(Map.of("a", 1, "z", 26, "m", 13)); System.out.println(tm.firstEntry()); // a=1 (peek) System.out.println(tm.lastEntry()); // z=26 (peek) System.out.println(tm.size()); // 3 (unchanged) pollFirstEntry() and pollLastEntry() are the idiomatic way to implement a sorted work queue or priority scheduler in a single-threaded context. For concurrent use, consider ConcurrentSkipListMap which also implements NavigableMap and is thread-safe.

NavigableSet extends SortedSet with the same four proximity methods as NavigableMap, but operating on elements instead of keys: floor(e), ceiling(e), lower(e), and higher(e). pollFirst() and pollLast() remove and return the smallest and largest elements. descendingSet() gives a live reverse-order view. TreeSet is the standard implementation.

import java.util.*; // NavigableSet adds the same proximity methods as NavigableMap, but for sets only // floor(e) — greatest element <= e // ceiling(e) — smallest element >= e // lower(e) — greatest element < e (strictly) // higher(e) — smallest element > e (strictly) TreeSet<Integer> ts = new TreeSet<>(Set.of(10, 20, 30, 40, 50)); System.out.println(ts.floor(25)); // 20 System.out.println(ts.floor(30)); // 30 (exact match) System.out.println(ts.floor(5)); // null System.out.println(ts.ceiling(25)); // 30 System.out.println(ts.ceiling(30)); // 30 (exact match) System.out.println(ts.ceiling(55)); // null System.out.println(ts.lower(30)); // 20 (strictly < 30) System.out.println(ts.higher(30)); // 40 (strictly > 30) // pollFirst() / pollLast() — remove and return smallest/largest TreeSet<String> words = new TreeSet<>(Set.of("apple", "banana", "cherry", "date")); System.out.println(words.pollFirst()); // apple (removed) System.out.println(words.pollLast()); // date (removed) System.out.println(words); // [banana, cherry] // first() / last() — peek without removing TreeSet<Integer> nums = new TreeSet<>(Set.of(5, 3, 8, 1, 9)); System.out.println(nums.first()); // 1 System.out.println(nums.last()); // 9 System.out.println(nums.size()); // 5 (unchanged) // descendingSet() — live reversed view NavigableSet<Integer> descNums = nums.descendingSet(); System.out.println(descNums.first()); // 9 descNums.forEach(System.out::println); // 9, 8, 5, 3, 1

NavigableSet mirrors the map range-view methods. headSet(toElement) returns all elements strictly less than toElement; pass true as the second argument to make it inclusive. tailSet(fromElement) returns elements from fromElement upward. subSet(from, to) returns a half-open range by default; the four-argument overload gives full control over both boundaries. Like map views, all set views are live and backed by the original — writes through the view affect the source set.

TreeSet<Integer> ts = new TreeSet<>(); for (int i = 10; i <= 100; i += 10) ts.add(i); // {10, 20, 30, 40, 50, 60, 70, 80, 90, 100} // headSet(toElement) — elements STRICTLY less than toElement SortedSet<Integer> head = ts.headSet(50); System.out.println(head); // [10, 20, 30, 40] // headSet(toElement, inclusive) NavigableSet<Integer> headInc = ts.headSet(50, true); System.out.println(headInc); // [10, 20, 30, 40, 50] // tailSet(fromElement) — elements >= fromElement SortedSet<Integer> tail = ts.tailSet(70); System.out.println(tail); // [70, 80, 90, 100] // tailSet(fromElement, inclusive=false) — strictly > fromElement NavigableSet<Integer> tailExcl = ts.tailSet(70, false); System.out.println(tailExcl); // [80, 90, 100] // subSet(from, to) — [from, to) half-open SortedSet<Integer> sub = ts.subSet(30, 70); System.out.println(sub); // [30, 40, 50, 60] // subSet with explicit inclusivity — closed [30, 70] NavigableSet<Integer> closedSub = ts.subSet(30, true, 70, true); System.out.println(closedSub); // [30, 40, 50, 60, 70] // Live views — adds through sub appear in the original set closedSub.add(35); System.out.println(ts.contains(35)); // true // Count elements in a range int count = ts.subSet(20, true, 60, true).size(); // [20,60] = 5 elements System.out.println("Elements in [20,60]: " + count); // Iterate range without creating a subSet for (Integer k = ts.ceiling(25); k != null && k <= 65; k = ts.higher(k)) { System.out.print(k + " "); // 30 35 40 50 60 }

TreeMap is the standard NavigableMap implementation, backed by a Red-Black tree with O(log n) for all operations. It accepts a custom Comparator at construction time to override natural ordering. TreeSet is backed internally by a TreeMap and implements NavigableSet. One important rule: if a Comparator considers two elements equal (returns 0), the tree treats them as the same key — regardless of what equals() says. For concurrent workloads, ConcurrentSkipListMap / ConcurrentSkipListSet implement the same interfaces with lock-free thread safety.

import java.util.*; // TreeMap — Red-Black tree // Implements: NavigableMap → SortedMap → Map // All operations: O(log n) // No null keys (compareTo would NPE); null values allowed // Custom comparator — reverse alphabetical key order TreeMap<String, Integer> reverseAlpha = new TreeMap<>(Comparator.reverseOrder()); reverseAlpha.put("apple", 1); reverseAlpha.put("cherry", 3); reverseAlpha.put("banana", 2); reverseAlpha.forEach((k, v) -> System.out.println(k)); // cherry, banana, apple // TreeSet — backed by a TreeMap internally // Implements: NavigableSet → SortedSet → Set // Custom ordering TreeSet<String> byLength = new TreeSet<>( Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder())); byLength.addAll(List.of("banana", "fig", "apple", "kiwi", "cherry", "ox")); System.out.println(byLength); // [ox, fig, kiwi, apple, banana, cherry] (len asc, then alpha) // Comparator consistency with equals: // If two elements compare as 0 by the comparator, TreeSet treats them as duplicates // Even if equals() says they are different objects TreeSet<String> caseInsensitive = new TreeSet<>(String.CASE_INSENSITIVE_ORDER); caseInsensitive.add("Hello"); caseInsensitive.add("hello"); // treated as duplicate — not added System.out.println(caseInsensitive.size()); // 1 System.out.println(caseInsensitive); // [Hello] // TreeMap from existing map (copy constructor) Map<String, Integer> source = Map.of("c", 3, "a", 1, "b", 2); TreeMap<String, Integer> sorted = new TreeMap<>(source); System.out.println(sorted); // {a=1, b=2, c=3} // ConcurrentSkipListMap / ConcurrentSkipListSet for concurrent NavigableMap/Set // java.util.concurrent.ConcurrentSkipListMap implements NavigableMap, is thread-safe // O(log n) expected, but lock-free — better throughput under contention than TreeMap When two elements compare as equal via the supplied Comparator, TreeSet and TreeMap treat them as the same key. For TreeSet this means the second element is not inserted. Always ensure your comparator is consistent with equals() unless the "duplicate by ordering" behavior is intentional.

Three patterns that show up frequently in real code: querying a time-ordered event log with subMap and floorEntry, implementing a score-based leaderboard with reverse-ordered TreeMap and headMap for rank calculation, and counting or iterating distinct values in a sorted window using TreeSet.subSet.

import java.util.*; import java.time.*; // --- Example 1: Event log — find events in a time range --- record LogEvent(Instant time, String message) {} TreeMap<Instant, LogEvent> eventLog = new TreeMap<>(); Instant base = Instant.parse("2026-03-14T10:00:00Z"); eventLog.put(base.plusSeconds(0), new LogEvent(base.plusSeconds(0), "Server started")); eventLog.put(base.plusSeconds(30), new LogEvent(base.plusSeconds(30), "Request received")); eventLog.put(base.plusSeconds(65), new LogEvent(base.plusSeconds(65), "DB query executed")); eventLog.put(base.plusSeconds(120), new LogEvent(base.plusSeconds(120), "Response sent")); eventLog.put(base.plusSeconds(180), new LogEvent(base.plusSeconds(180), "Connection closed")); Instant from = base.plusSeconds(25); Instant to = base.plusSeconds(130); // All events in [from, to] inclusive NavigableMap<Instant, LogEvent> window = eventLog.subMap(from, true, to, true); window.forEach((t, e) -> System.out.println(t.getEpochSecond() - base.getEpochSecond() + "s: " + e.message())); // 30s: Request received // 65s: DB query executed // 120s: Response sent // Most recent event before a given time Instant query = base.plusSeconds(100); Map.Entry<Instant, LogEvent> latest = eventLog.floorEntry(query); System.out.println("Most recent before T+100: " + latest.getValue().message()); // Most recent before T+100: DB query executed // Next event after a given time Map.Entry<Instant, LogEvent> next = eventLog.higherEntry(query); System.out.println("Next after T+100: " + next.getValue().message()); // Next after T+100: Response sent // --- Example 2: Leaderboard — top-N retrieval and rank queries --- TreeMap<Integer, String> leaderboard = new TreeMap<>(Comparator.reverseOrder()); leaderboard.put(9500, "Alice"); leaderboard.put(8200, "Bob"); leaderboard.put(7800, "Carol"); leaderboard.put(9100, "Diana"); leaderboard.put(6500, "Ethan"); leaderboard.put(9500, "Fiona"); // same score as Alice — overwrites in TreeMap // Top 3 scores leaderboard.entrySet().stream() .limit(3) .forEach(e -> System.out.println(e.getValue() + ": " + e.getKey())); // Fiona: 9500 Diana: 9100 Bob: 8200 // Rank of a player: how many players have strictly higher scores? int carolScore = 7800; int rank = leaderboard.headMap(carolScore, false).size() + 1; // exclusive = strictly higher System.out.println("Carol's rank: " + rank); // 3 // Players within 500 points of Bob int bobScore = 8200; NavigableMap<Integer, String> nearBob = leaderboard.subMap( bobScore - 500, true, bobScore + 500, true); System.out.println("Near Bob: " + nearBob.values()); // [Bob] (none within 500 in this set) // --- Example 3: NavigableSet for a sliding-window unique-count --- // Count distinct values in a sorted window using TreeSet subSet TreeSet<Integer> window2 = new TreeSet<>(Set.of(1, 3, 5, 7, 9, 11, 13, 15, 17, 19)); int lo = 5, hi = 15; int countInRange = window2.subSet(lo, true, hi, true).size(); System.out.println("Elements in [" + lo + "," + hi + "]: " + countInRange); // 6 // Nearest value to a target that is in the set int target = 10; Integer floorVal = window2.floor(target); // 9 Integer ceilingVal = window2.ceiling(target); // 11 int closest = (floorVal == null) ? ceilingVal : (ceilingVal == null) ? floorVal : (target - floorVal <= ceilingVal - target) ? floorVal : ceilingVal; System.out.println("Closest to " + target + ": " + closest); // 9 or 11 (tie → 9)