Интерфейсы SortedSet, NavigableSet и класс TreeSet в Java

Расписание паромов хранится в TreeSet: [1830, 2010]. Нужен последний паром до 16:00. Вызов times.headSet(1600).last() бросает NoSuchElementException: подмножество пустое. А times.lower(1600) просто вернёт null. Оба способа ищут одно и то же, но первый взят из SortedSet, а второй — из NavigableSet.

SortedSet (java.util.SortedSet<E>) — интерфейс отсортированного множества: элементы без повторов хранятся по возрастанию в естественном порядке (Comparable) или по правилу Comparator. NavigableSet расширяет его методами поиска ближайших элементов: ceiling(), floor(), higher(), lower(). TreeSet — основная реализация обоих интерфейсов на красно-чёрном дереве, операции add(), remove() и contains() выполняются за O(log n).

Интерфейс SortedSet: методы first, last, headSet, subSet, tailSet

SortedSet в Java — это Set, который всегда хранит элементы отсортированными. Он добавляет шесть методов: first() и last() возвращают крайние элементы, headSet(), subSet() и tailSet() — диапазоны, а comparator() — правило сортировки. Порядок задаёт Comparable элементов или переданный Comparator.

Пример использования методов subSet(), headSet(), tailSet(), first() и last():

import java.util.SortedSet;
import java.util.TreeSet;

public class SortedSetExample {
    public static void main(String[] args) {
        SortedSet<String> set = new TreeSet<>();

        set.add("Харьков");
        set.add("Киев");
        set.add("Львов");
        set.add("Кременчуг");
        set.add("Харьков");

        System.out.println(set);

        SortedSet<String> subSet = set.subSet("Киев", "Львов");
        System.out.println("SubSet: " + subSet);

        System.out.println("HeadSet: " + set.headSet("Львов"));
        System.out.println("TailSet: " + set.tailSet("Львов"));
        System.out.println("Первый элемент: " + set.first());
        System.out.println("Последний элемент: " + set.last());
    }
}

Результат выполнения программы:

[Киев, Кременчуг, Львов, Харьков]
SubSet: [Киев, Кременчуг]
HeadSet: [Киев, Кременчуг]
TailSet: [Львов, Харьков]
Первый элемент: Киев
Последний элемент: Харьков

Повторный «Харьков» не добавился — это всё ещё множество. «Львов» не попал ни в subSet("Киев", "Львов"), ни в headSet("Львов"): верхняя граница диапазона в SortedSet всегда исключается, а нижняя — включается. Строки сравниваются по кодам символов, поэтому для словарного порядка с буквой «Ё» нужен Collator — подробно в уроке Comparable и Comparator.

Интерфейс NavigableSet: ceiling, floor, higher, lower

NavigableSet в Java — интерфейс, который расширяет SortedSet методами навигации: найти ближайший элемент к заданному значению, извлечь крайний элемент с удалением, обойти множество в обратном порядке и взять диапазон с явным включением границ. Интерфейс появился в Java 6, его реализуют TreeSet и ConcurrentSkipListSet.

Методы поиска не бросают исключений: если подходящего элемента нет, они возвращают null. Разница между парами — в строгости сравнения: ceiling() и floor() принимают равный элемент, higher() и lower() — нет.

Что выведет этот код? Множество одно, а четыре метода дают четыре разных ответа:

import java.util.List;
import java.util.NavigableSet;
import java.util.TreeSet;

public class NearestExample {
    public static void main(String[] args) {
        NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30));

        System.out.println(set.ceiling(20)); // 20 — равный подходит
        System.out.println(set.higher(20));  // 30 — только строго больший
        System.out.println(set.floor(20));   // 20
        System.out.println(set.lower(20));   // 10
        System.out.println(set.ceiling(35)); // null — больше 35 ничего нет
        System.out.println(set.floor(5));    // null — меньше 5 ничего нет
    }
}

Вывод:

20
30
20
10
null
null

Пример использования интерфейса NavigableSet на практике — расписание паромов. Одна и та же задача решается методами SortedSet и методами NavigableSet:

import java.util.NavigableSet;
import java.util.SortedSet;
import java.util.TreeSet;

public class Ferry {
    public static void main(String[] args) {
        NavigableSet<Integer> times = new TreeSet<>();
        times.add(1205);
        times.add(1505);
        times.add(1545);
        times.add(1830);
        times.add(2010);
        times.add(2100);

        // Через методы SortedSet: headSet() и tailSet()
        System.out.println("SortedSet");
        SortedSet<Integer> headSet = times.headSet(1600);
        System.out.println("Последний паром перед 16:00 - " + headSet.last());

        SortedSet<Integer> tailSet = times.tailSet(2000);
        System.out.println("Первый паром после 20:00 - " + tailSet.first());
        System.out.println();

        // Через методы NavigableSet: lower() и higher()
        System.out.println("NavigableSet");
        System.out.println("Последний паром перед 16:00 - " + times.lower(1600));
        System.out.println("Первый паром после 20:00 - " + times.higher(2000));
    }
}

Вывод:

SortedSet
Последний паром перед 16:00 - 1545
Первый паром после 20:00 - 2010

NavigableSet
Последний паром перед 16:00 - 1545
Первый паром после 20:00 - 2010

Результаты совпадают, но вариант с lower() и higher() короче и безопаснее: если паромов до 16:00 нет, он вернёт null, а headSet(1600).last() бросит NoSuchElementException, как в примере из начала урока.

headSet, tailSet и subSet с флагами inclusive

Методы диапазонов в SortedSet работают с полуоткрытым интервалом: нижняя граница включается, верхняя — нет. В NavigableSet у тех же методов есть перегрузки с параметром boolean inclusive, и включение каждой границы задаётся явно. Обе версии возвращают представление исходного множества, а не копию.

import java.util.List;
import java.util.NavigableSet;
import java.util.TreeSet;

public class RangeExample {
    public static void main(String[] args) {
        NavigableSet<Integer> nums = new TreeSet<>(List.of(10, 20, 30, 40, 50));

        System.out.println(nums.headSet(30));                 // [10, 20]
        System.out.println(nums.headSet(30, true));           // [10, 20, 30]
        System.out.println(nums.tailSet(30));                 // [30, 40, 50]
        System.out.println(nums.tailSet(30, false));          // [40, 50]
        System.out.println(nums.subSet(20, 40));              // [20, 30]
        System.out.println(nums.subSet(20, false, 40, true)); // [30, 40]
        System.out.println(nums.subSet(40, 20));              // IllegalArgumentException
    }
}

Вывод:

[10, 20]
[10, 20, 30]
[30, 40, 50]
[40, 50]
[20, 30]
[30, 40]
Exception in thread "main" java.lang.IllegalArgumentException: fromKey > toKey

Границы не обязаны быть элементами множества: nums.subSet(15, 35) вернёт [20, 30]. Версия без флагов эквивалентна headSet(toElement, false), tailSet(fromElement, true) и subSet(fromElement, true, toElement, false).

Подмножества — это представления (backed-collection)

Методы headSet(), tailSet(), subSet() и descendingSet() не копируют элементы, а возвращают представление исходного множества — по-другому это называется backed-collection. Изменения видны в обе стороны: добавление в исходное множество появляется в подмножестве, удаление из подмножества удаляет элемент из исходного. Добавить в представление значение вне его диапазона нельзя.

import java.util.List;
import java.util.NavigableSet;
import java.util.TreeSet;

public class BackedSetExample {
    public static void main(String[] args) {
        TreeSet<Integer> all = new TreeSet<>(List.of(10, 20, 30, 40, 50));
        NavigableSet<Integer> head = all.headSet(30, true);
        System.out.println(head);  // [10, 20, 30]

        all.add(25);
        System.out.println(head);  // [10, 20, 25, 30]

        head.remove(10);
        System.out.println(all);   // [20, 25, 30, 40, 50]

        head.add(45);              // 45 вне диапазона "до 30 включительно"
    }
}

Вывод:

[10, 20, 30]
[10, 20, 25, 30]
[20, 25, 30, 40, 50]
Exception in thread "main" java.lang.IllegalArgumentException: key out of range

Если нужна независимая копия диапазона, оберните представление: new TreeSet<>(all.headSet(30, true)). Тот же механизм у subMap() в TreeMap и у Arrays.asList() разобран в уроке Backed Collections.

pollFirst, pollLast, descendingSet и обратный итератор

pollFirst() и pollLast() возвращают наименьший и наибольший элементы и сразу удаляют их, а для пустого множества возвращают null. descendingSet() даёт представление в обратном порядке, descendingIterator() — итератор от большего к меньшему. Обычный iterator() у TreeSet всегда обходит элементы по возрастанию.

import java.util.Iterator;
import java.util.List;
import java.util.TreeSet;

public class PollDescendingExample {
    public static void main(String[] args) {
        TreeSet<String> tasks = new TreeSet<>(List.of("b", "d", "a", "c"));

        System.out.println(tasks.descendingSet());     // [d, c, b, a]

        Iterator<String> it = tasks.descendingIterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");          // d c b a
        }
        System.out.println();

        System.out.println(tasks.pollFirst());          // a
        System.out.println(tasks.pollLast());           // d
        System.out.println(tasks);                      // [b, c]

        TreeSet<String> empty = new TreeSet<>();
        System.out.println(empty.pollFirst());          // null
        System.out.println(empty.first());              // NoSuchElementException
    }
}

Вывод:

[d, c, b, a]
d c b a
a
d
[b, c]
null
Exception in thread "main" java.util.NoSuchElementException

Пара pollFirst() в цикле while удобна, чтобы обработать элементы по возрастанию и одновременно очистить множество. Итератор TreeSet fail-fast: если изменить множество во время обхода не через сам итератор, следующий next() бросит ConcurrentModificationException — подробнее в уроке Iterator.

Класс TreeSet: устройство и конструкторы

TreeSet в Java — это класс, реализующий NavigableSet (а значит, и SortedSet, и Set). Внутри он хранит элементы как ключи TreeMap — красно-чёрного дерева, поэтому add(), remove() и contains() выполняются за O(log n). Это медленнее, чем O(1) в среднем у HashSet, но быстрее линейного поиска O(n) в списке.

Пример использования класса TreeSet:

import java.util.SortedSet;
import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        SortedSet<String> set = new TreeSet<>();

        set.add("Харьков");
        set.add("Киев");
        set.add("Львов");
        set.add("Кременчуг");
        set.add("Харьков");

        System.out.println(set);
    }
}

Элементы были добавлены в произвольном порядке, но при выводе на консоль они отсортированы:

[Киев, Кременчуг, Львов, Харьков]

Порядок задаётся при создании множества и потом не меняется. Конструкторы класса TreeSet:

Какой из двух последних конструкторов вызовется, решает компилятор по объявленному типу переменной, а не по реальному объекту:

import java.util.Collection;
import java.util.Comparator;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;

public class TreeSetConstructorExample {
    public static void main(String[] args) {
        SortedSet<String> desc = new TreeSet<>(Comparator.reverseOrder());
        desc.addAll(List.of("a", "b", "c"));

        System.out.println(new TreeSet<>(desc));          // [c, b, a]

        Collection<String> asCollection = desc;
        System.out.println(new TreeSet<>(asCollection));  // [a, b, c]
    }
}

Вывод:

[c, b, a]
[a, b, c]

В первом вызове выбран TreeSet(SortedSet), и копия сохранила обратный порядок. Во втором та же коллекция объявлена как Collection, вызывается TreeSet(Collection) — и копия молча сортируется по возрастанию.

SortedSet, NavigableSet и TreeSet: что выбрать

SortedSet и NavigableSet — интерфейсы, TreeSet — класс, который их реализует, поэтому вопрос «SortedSet vs TreeSet» сводится к тому, каким типом объявить переменную. Объявляйте NavigableSet, если нужны ceiling(), floor() или флаги диапазонов, SortedSet — если хватает first(), last() и subSet(). В new указывается реализация.

Если сортировка не нужна, берите HashSet или LinkedHashSet — их различия описаны в уроке Set, HashSet и LinkedHashSet. Аналог NavigableSet для пар «ключ–значение» — NavigableMap и класс TreeMap из урока Map, а общая таблица выбора коллекции — в разделе Какую реализацию выбрать.

Где чаще всего ошибаются

Большинство ошибок с TreeSet связано с границами диапазонов, пустым множеством и тем, что подмножества — представления, а не копии. Ниже — типичные промахи, что при этом происходит и как написать правильно.