Java Interview Questions

Главная / Все ответы / Коллекции

Вопрос 13 · Раздел 4

Что такое TreeSet и как он работает?

4. View = live, не копия 5. Java 21 → SequencedSet API 6. Cache miss при итерации — учитывайте 7. Память в 3-4 раза больше HashSet

Russian Коллекции Исходный Markdown
Версии по языкам: English Russian Ukrainian

🟢 Junior Level

TreeSet — отсортированная коллекция уникальных элементов.

Простая аналогия: Словарь — слова всегда в алфавитном порядке, независимо от того, в каком порядке вы их добавляли.

TreeSet<Integer> set = new TreeSet<>();
set.add(5);
set.add(2);
set.add(8);
set.add(1);

System.out.println(set);  // → [1, 2, 5, 8] (всегда отсортировано!)

Особенности:

  • Элементы всегда отсортированы
  • Нельзя null
  • Медленнее HashSet: O(log n) вместо O(1) + каждый узел — отдельный объект в куче (cache miss при обходе). Но данные отсортированы.

🟡 Middle Level

Внутри: TreeMap

// TreeSet = адаптер над TreeMap
private transient TreeMap<E, Object> m;
private static final Object PRESENT = new Object();

// Все операции делегируются TreeMap
// Сложность: O(log n) для add/remove/contains

Красно-черное дерево

Самобалансирующееся бинарное дерево:
  → Высота всегда O(log n)
  → При вставке/удалении: rebalancing (повороты)
    Повороты = перестройка связей между узлами дерева, чтобы высота оставалась O(log n). Без поворотов дерево выродится в linked list с O(n).
  → Цвета узлов (красный/черный) для баланса

    5(B)
   /   \
  2(R)  8(R)
 /  \
1(B) 3(B)

Навигация

TreeSet<Integer> set = new TreeSet<>(Set.of(1, 3, 5, 7, 9));

set.floor(6);    // → 5 (ближайший ≤ 6)
set.ceiling(6);  // → 7 (ближайший ≥ 6)
set.lower(5);    // → 3 (строго < 5)
set.higher(5);   // → 7 (строго > 5)

set.subSet(3, 8);    // → [3, 5, 7] (диапазон)
set.headSet(5);      // → [1, 3] (меньше 5)
set.tailSet(5);      // → [5, 7, 9] (больше или равно)

compareTo vs equals

// TreeSet использует compareTo, НЕ equals!
class Person implements Comparable<Person> {
    String name;
    public int compareTo(Person o) {
        return name.compareTo(o.name);  // По имени
    }
}

// Если compareTo = 0 → элемент НЕ добавится
// Даже если equals возвращает false!

// → equals и compareTo должны быть согласованы!

Когда НЕ использовать TreeSet

  1. Нужна только уникальность — HashSet быстрее (O(1) vs O(log n))
  2. Элементы не имплементируют Comparable и нет Comparator — TreeSet не сможет сортировать
  3. Память критична — TreeSet в 3-4 раза больше HashSet (узлы дерева с prev/next/left/right)

🔴 Senior Level

Memory Footprint

Каждый Entry в TreeMap:
  Object Header: 12 байт
  K key: 4-8 байт
  V value: 4 байта (PRESENT)
  Entry left: 4-8 байт
  Entry right: 4-8 байт
  Entry parent: 4-8 байт
  boolean color: 1 байт
  Padding: до 8 байт
  
Итого: ~40-48 байт на элемент!

→ TreeSet в 3-4 раза больше HashSet

Cache Locality проблема

Узлы дерева разбросаны по Heap:
  [Entry1]...[Entry2]...[Entry3]
  
Каждый переход к потомку = cache miss!
  → Ожидание из RAM: 100+ циклов
  
→ Итерация TreeSet медленнее HashSet

Java 21: SequencedSet

// TreeSet → SequencedSet (SequencedSet — требует Java 21+, недоступно на Java 11/17.)
set.getFirst();   // Наименьший элемент
set.getLast();    // Наибольший элемент
set.reversed();   // Обратный порядок (view)

// addFirst/addLast → UnsupportedOperationException
// → Порядок дерева фиксирован!

View семантика

NavigableSet<Integer> view = set.subSet(3, true, 7, true);
// → "Живое" представление, не копия!

view.add(5);       // Добавляет в ИСХОДНЫЙ set
set.remove(5);     // Удаляет из view тоже!

view.add(10);      // → IllegalArgumentException!
// → 10 вне диапазона [3, 7]

Custom Comparator с null

// TreeSet не принимает null по умолчанию
// Но можно через Comparator:
TreeSet<String> set = new TreeSet<>(
    Comparator.nullsFirst(Comparator.naturalOrder())
);
set.add(null);  // OK! null первый

Spliterator оптимизации

Spliterator<Integer> spliterator = set.spliterator();
// Характеристики:
//   SORTED   → Stream API оптимизирует
//   DISTINCT → distinct() бесплатен
//   SIZED    → известен размер

set.stream()
   .distinct()  // → Ничего не делает! Уже уникальны
   .count();    // → O(1), знает размер

Production Experience

Реальный сценарий: Tax brackets

// Налоговые ставки по порогу дохода
NavigableMap<Integer, Double> taxBrackets = new TreeMap<>();
taxBrackets.put(0, 0.0);      // 0% до 0
taxBrackets.put(10000, 0.1);  // 10% до 10к
taxBrackets.put(50000, 0.2);  // 20% до 50к

// Найти ставку для дохода 35,000
double rate = taxBrackets.floorEntry(35000).getValue();
// → 0.1 (10%)

// HashMap НЕ сможет! Нужна сортировка

Best Practices

  1. TreeMap внутри → O(log n) операции
  2. compareTo = equals контракт!
  3. null запрещён (без custom Comparator)
  4. View = live, не копия
  5. Java 21 → SequencedSet API
  6. Cache miss при итерации — учитывайте
  7. Память в 3-4 раза больше HashSet

Резюме для Senior

  • TreeSet = TreeMap + PRESENT заглушка
  • Красно-черное дерево → O(log n), балансировка
  • compareTo определяет уникальность, не equals
  • NavigableSet → floor/ceiling/subSet
  • View = live представление, O(1) создание
  • Cache Locality плохая → узлы разбросаны
  • Memory ~40-48 байт на элемент
  • SequencedSet (Java 21) → getFirst/reversed

🎯 Шпаргалка для интервью

Обязательно знать:

  • TreeSet = адаптер над TreeMap, элементы хранятся как ключи, значение = static final Object PRESENT
  • Внутри: красно-чёрное дерево (самобалансирующееся бинарное дерево), высота всегда O(log n)
  • Сложность: O(log n) для add/remove/contains — медленнее HashSet (O(1))
  • NavigableSet API: floor, ceiling, lower, higher, subSet, headSet, tailSet
  • Не принимает null (без custom Comparator) — NullPointerException
  • compareTo определяет уникальность, а не equals — если compareTo = 0, элемент не добавится
  • Memory: ~40-48 байт на элемент (left, right, parent, color) — в 3-4 раза больше HashSet
  • Cache locality плохая — узлы разбросаны по heap, каждый переход = cache miss
  • View (subSet и т.д.) = live представление, не копия, O(1) создание

Частые уточняющие вопросы:

  • Почему TreeSet медленнее HashSet? — O(log n) из-за дерева + cache miss при каждом переходе между узлами.
  • Что будет если compareTo и equals не согласованы? — TreeSet может считать разные элементы (по equals) одинаковыми (по compareTo = 0) — потеря данных.
  • Как добавить null в TreeSet? — Через Comparator.nullsFirst(Comparator.naturalOrder()).
  • Зачем нужны View (subSet) и какие у них ограничения? — Live представление диапазона. Можно добавлять только элементы внутри диапазона — иначе IllegalArgumentException.

Красные флаги (НЕ говорить):

  • ❌ «TreeSet использует equals для сравнения элементов» — использует compareTo!
  • ❌ «TreeSet быстрее HashSet» — в 50 раз медленнее из-за O(log n) и cache miss
  • ❌ «TreeSet можно использовать с null по умолчанию» — нет, только с custom Comparator
  • ❌ «subSet создаёт копию данных» — это live view, изменения отражаются в исходном множестве

Связанные темы:

  • [[11. В чём разница между HashSet, LinkedHashSet и TreeSet]]
  • [[15. В чём разница между HashMap, LinkedHashMap и TreeMap]]
  • [[16. Когда использовать TreeMap]]
  • [[14. Что такое Map и какие реализации существуют]]