Collections

115. NavigableMap & NavigableSet: Submaps, Floor, and Ceiling

NavigableMap and NavigableSet extend SortedMap/SortedSet with closest-match queries (floor, ceiling, lower, higher) and flexible range views (subMap, headMap, tailMap).

Java 21 (java.util.NavigableMap & NavigableSet)

Explanation

SortedMap (implemented by TreeMap) provides basic sorting, but lacks convenient navigation methods when searching for boundaries or closest matches. NavigableMap provides comprehensive directional navigation over keys and entries: - lowerEntry(k): Greatest key strictly less than k (< k). - floorEntry(k): Greatest key less than or equal to k (<= k). - ceilingEntry(k): Least key greater than or equal to k (>= k). - higherEntry(k): Least key strictly greater than k (> k). - pollFirstEntry() / pollLastEntry(): Retrieves and removes minimum or maximum entry. - descendingMap(): Reverse-order view with zero copying. - subMap(from, fromInclusive, to, toInclusive): Bounded range sub-views.

Interview applications include: rate-limiting sliding windows, IP address range lookup, scheduling nearest deadlines, and building routing tables.

Example

import java.util.NavigableMap;
import java.util.TreeMap;

public class NavigableMapDemo {
    public static void main(String[] args) {
        NavigableMap<Integer, String> schedule = new TreeMap<>();
        schedule.put(900,  "Standup Meeting");
        schedule.put(1030, "Architecture Review");
        schedule.put(1300, "Lunch Break");
        schedule.put(1500, "1-on-1 Sync");

        int queryTime = 1045; // 10:45 AM

        // What was the most recent meeting that started?
        var current = schedule.floorEntry(queryTime);
        System.out.printf("Current event: [%d] %s%n", current.getKey(), current.getValue());

        // What is the upcoming meeting?
        var upcoming = schedule.ceilingEntry(queryTime);
        System.out.printf("Upcoming event: [%d] %s%n", upcoming.getKey(), upcoming.getValue());

        // Range query: all afternoon meetings between 12:00 and 17:00
        NavigableMap<Integer, String> afternoon = schedule.subMap(1200, true, 1700, true);
        System.out.println("Afternoon events: " + afternoon);

        // Reverse view
        System.out.println("Latest event: " + schedule.lastEntry());
    }
}

Sources