NavigableSet/NavigableMap

1. Введение

В стандартной библиотеке Java есть множество коллекций, но когда речь заходит о диапазонах, поиске «ближайших» элементов, приоритизации и работе с временными слотами, на сцену выходят интерфейсы NavigableSet и NavigableMap.

NavigableSet расширяет SortedSet, добавляя методы для поиска элементов относительно заданного значения (меньше, больше, ближайший и т. д.), а также для работы с диапазонами.
NavigableMap расширяет SortedMap, добавляя похожие методы для поиска по ключам и работы с диапазонами.

Самые известные реализации: TreeSet и TreeMap.

Когда нужны NavigableSet/NavigableMap?

• Когда важно не просто хранить уникальные элементы/ключи в отсортированном порядке, но и быстро находить «соседей» (например, ближайшее свободное время, приоритетную задачу, диапазон значений).
• Когда нужно работать с диапазонами: «все элементы между X и Y», «все ключи больше/меньше заданного», «найти ближайший ключ».

2. Диапазоны: subSet, headSet, tailSet

Методы для работы с диапазонами

NavigableSet и NavigableMap позволяют получать «живые» представления (view) на подмножества коллекции:

• subSet(fromElement, fromInclusive, toElement, toInclusive) — элементы в диапазоне [fromElement; toElement], включительно/исключительно.
• headSet(toElement, inclusive) — все элементы меньше (или меньше либо равно) toElement.
• tailSet(fromElement, inclusive) — все элементы больше (или больше либо равно) fromElement.

Пример:

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));

// Диапазон от 15 (включительно) до 45 (исключительно)
NavigableSet<Integer> sub = set.subSet(15, true, 45, false); // [20, 30, 40]
System.out.println(sub); // [20, 30, 40]

// Все элементы <= 30
NavigableSet<Integer> head = set.headSet(30, true); // [10, 20, 30]

// Все элементы > 20
NavigableSet<Integer> tail = set.tailSet(20, false); // [30, 40, 50]

Включительность/исключительность:

• true — включительно (элемент входит в диапазон)
• false — исключительно (элемент не входит)

Для NavigableMap методы аналогичны, только работают с ключами.

3. Операции ближних значений: floor, ceiling, lower, higher; pollFirst/Last

Поиск ближайших элементов

NavigableSet:

• lower(E e) — наибольший элемент < e (строго меньше)
• floor(E e) — наибольший элемент ≤ e (меньше или равно)
• ceiling(E e) — наименьший элемент ≥ e (больше или равно)
• higher(E e) — наименьший элемент > e (строго больше)

Пример:

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));

System.out.println(set.lower(30));   // 20
System.out.println(set.floor(30));   // 30
System.out.println(set.ceiling(25)); // 30
System.out.println(set.higher(40));  // 50

pollFirst() / pollLast()

• pollFirst() — удаляет и возвращает наименьший элемент (или null, если пусто)
• pollLast() — удаляет и возвращает наибольший элемент

Пример:

System.out.println(set.pollFirst()); // 10
System.out.println(set.pollLast());  // 50
System.out.println(set);             // [20, 30, 40]

NavigableMap: аналогичные методы для ключей — lowerKey, floorKey, ceilingKey, higherKey, а также pollFirstEntry, pollLastEntry.

4. Виды: descendingSet/descendingMap; представления‑view и их «живость»

Обратный порядок: descendingSet/descendingMap

• descendingSet() — возвращает представление множества в обратном порядке.
• descendingMap() — возвращает представление карты в обратном порядке ключей.

Пример:

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));
NavigableSet<Integer> desc = set.descendingSet();
System.out.println(desc); // [50, 40, 30, 20, 10]

Важно: это не копия, а «живое» представление (view) на тот же набор данных. Изменения в одном отражаются в другом.

Представления (view) и их «живость»

• Методы subSet, headSet, tailSet, descendingSet, descendingMap возвращают view — «живое» представление на исходную коллекцию.
• Любые изменения в view отражаются в исходной коллекции и наоборот.
• Если удалить элемент из subSet — он исчезнет и из исходного множества.

Пример:

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));
NavigableSet<Integer> sub = set.subSet(20, true, 40, true); // [20, 30, 40]
sub.remove(30);
System.out.println(set); // [10, 20, 40, 50]

Осторожно: если вы измените исходную коллекцию так, что элемент «выпадет» из диапазона view, при следующем обращении к view получите ConcurrentModificationException.

5. Кейсы использования NavigableSet/NavigableMap

1. Слоты времени/расписания

Задача: найти ближайший свободный временной слот для встречи.

NavigableSet<LocalTime> slots = new TreeSet<>(List.of(
    LocalTime.of(9, 0),
    LocalTime.of(10, 0),
    LocalTime.of(11, 0),
    LocalTime.of(14, 0)
));

LocalTime requested = LocalTime.of(10, 30);
LocalTime nextSlot = slots.ceiling(requested); // 11:00
System.out.println("Ближайшее время: " + nextSlot);

2. Приоритизация (очередь с приоритетом)

Задача: всегда быстро получать элемент с наивысшим/наименьшим приоритетом.

NavigableSet<Task> tasks = new TreeSet<>(Comparator.comparingInt(Task::priority));
tasks.add(new Task("Почта", 2));
tasks.add(new Task("Звонок", 1));
tasks.add(new Task("Отчёт", 3));

Task next = tasks.pollFirst(); // Задача с наивысшим приоритетом (1)

3. «Самый близкий ключ» (например, для поиска диапазона в Map)

Задача: найти диапазон значений по ключу, или ближайший ключ.

NavigableMap<Integer, String> grades = new TreeMap<>();
grades.put(50, "Неудовлетворительно");
grades.put(65, "Удовлетворительно");
grades.put(75, "Хорошо");
grades.put(85, "Отлично");

int score = 78;
int key = grades.floorKey(score); // 75
System.out.println("Оценка: " + grades.get(key)); // Хорошо

6. Практика: мини-примеры

Пример 1: Диапазон дат

NavigableSet<LocalDate> holidays = new TreeSet<>(List.of(
    LocalDate.of(2024, 1, 1),
    LocalDate.of(2024, 5, 1),
    LocalDate.of(2024, 12, 31)
));
LocalDate from = LocalDate.of(2024, 1, 1);
LocalDate to = LocalDate.of(2024, 6, 1);
NavigableSet<LocalDate> spring = holidays.subSet(from, true, to, false);
System.out.println(spring); // [2024-01-01, 2024-05-01]

Пример 2: Поиск ближайшего значения

NavigableSet<Integer> numbers = new TreeSet<>(List.of(10, 20, 30, 40, 50));
int x = 25;
System.out.println("Меньше: " + numbers.lower(x));              // 20
System.out.println("Меньше или равно: " + numbers.floor(x));    // 20
System.out.println("Больше или равно: " + numbers.ceiling(x));  // 30
System.out.println("Больше: " + numbers.higher(x));             // 30

7. Типичные ошибки и нюансы

Ошибка №1: Путают включительность/исключительность в subSet/headSet/tailSet.
Всегда внимательно смотрите на параметры inclusive — по умолчанию в старых версиях Java диапазоны были исключительными, в NavigableSet/NavigableMap можно явно указать включительно/исключительно.

Ошибка №2: Ожидание, что view — это копия.
View — это «живое» представление, а не копия! Изменения в view отражаются в исходной коллекции.

Ошибка №3: ConcurrentModificationException при изменении исходной коллекции вне view.
Если вы изменяете исходную коллекцию так, что элемент «выпадает» из диапазона view, при следующем обращении к view получите исключение.

Ошибка №4: Использование NavigableSet/NavigableMap без Comparable или Comparator.
Эти коллекции требуют, чтобы элементы (или ключи) были сравнимы (Comparable) или был передан Comparator. Иначе получите ClassCastException.

Ошибка №5: Ожидание, что pollFirst/pollLast не изменяют коллекцию.
Эти методы удаляют элементы! Если нужен просто просмотр — используйте first()/last().