0Pricing
Java Academy · Урок

Подкарты и представления диапазонов

Извлекайте представления subMap, headMap и tailMap для поиска по диапазонам в отсортированных картах.

«Подкарты и представления диапазонов» — бесплатный урок Java Academy на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Java Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Java Academy содержит 4 уроков всего.

Представления диапазонов в TreeMap

subMap, headMap и tailMap TreeMap возвращают связанные представления: они отражают изменения в исходной карте и наоборот. Изменения, внесённые через представление, отражаются в исходной карте.

TreeMap<Integer, String> map = new TreeMap<>();
for (int i = 1; i <= 10; i++) map.put(i * 10, "item" + i);

var view = map.subMap(30, 70); // [30, 70)
System.out.println(view); // {30=item3, 40=item4, 50=item5, 60=item6}

map.put(45, "new"); // also visible through view!
System.out.println(view.containsKey(45)); // true

headMap: ключи меньше границы

headMap(toKey) возвращает все записи с ключами, строго меньшими toKey. Используйте включающий границу вариант headMap(toKey, true), чтобы включить саму границу.

TreeMap<String, Integer> words = new TreeMap<>();
"banana cherry apple date elderberry".chars()
    .mapToObj(c -> String.valueOf((char)c)).distinct()
    .forEach(w -> words.put(w, w.length()));
// Actually let's use real words:
TreeMap<String, Integer> wc = new TreeMap<>();
wc.put("apple",5); wc.put("banana",6); wc.put("cherry",6); wc.put("date",4);

System.out.println(wc.headMap("cherry")); // {apple=5, banana=6}

tailMap: ключи начиная с границы

tailMap(fromKey) возвращает все записи с ключами ≥ fromKey.

TreeMap<Integer, String> grades = new TreeMap<>();
grades.put(50,"F"); grades.put(60,"D"); grades.put(70,"C"); grades.put(80,"B"); grades.put(90,"A");

// All passing grades (>= 60)
var passing = grades.tailMap(60);
System.out.println(passing); // {60=D, 70=C, 80=B, 90=A}

subMap с включаемыми границами

Четырёхаргументный вариант subMap(from, fromInclusive, to, toInclusive) обеспечивает полный контроль над включением границ:

TreeMap<Integer, String> map = new TreeMap<>();
for (int i = 10; i <= 100; i += 10) map.put(i, "v"+i);

// [30, 60] — both inclusive
System.out.println(map.subMap(30, true, 60, true));
// {30=v30, 40=v40, 50=v50, 60=v60}

// (30, 60) — both exclusive
System.out.println(map.subMap(30, false, 60, false));
// {40=v40, 50=v50}

Изменение данных через представление

Операции put и remove над представлением subMap отражаются в исходной карте и наоборот. Попытка добавить ключ за пределами диапазона представления приводит к исключению.

TreeMap<Integer, String> map = new TreeMap<>();
for (int i = 1; i <= 5; i++) map.put(i * 10, "v" + i);

var view = map.subMap(20, 40); // [20, 40)
view.remove(20); // removes from both view and original map
System.out.println(map.containsKey(20)); // false

// This would throw IllegalArgumentException:
// view.put(50, "out of range");

Пример применения: запрос диапазона журналов

Получайте все записи журнала между двумя временными метками с помощью представления диапазона TreeMap:

import java.time.*;
TreeMap<LocalDateTime, String> logs = new TreeMap<>();
logs.put(LocalDateTime.of(2024,1,1,8,0), "Server start");
logs.put(LocalDateTime.of(2024,1,1,10,0), "Request spike");
logs.put(LocalDateTime.of(2024,1,1,14,0), "Maintenance");
logs.put(LocalDateTime.of(2024,1,1,18,0), "Server stop");

var morning = logs.subMap(
    LocalDateTime.of(2024,1,1,8,0), true,
    LocalDateTime.of(2024,1,1,12,0), false
);
morning.forEach((t,m) -> System.out.println(t+" : "+m));

Пример применения: поиск по диапазону цен

Находите все товары в диапазоне цен, используя цены в качестве ключей TreeMap:

TreeMap<Double, String> products = new TreeMap<>();
products.put(9.99, "Pen");
products.put(24.99, "Book");
products.put(49.99, "Headphones");
products.put(299.99, "Tablet");

double min = 10.0, max = 100.0;
var affordable = products.subMap(min, true, max, true);
affordable.forEach((p,n) -> System.out.println(n+" $"+p));
// Book $24.99, Headphones $49.99

descending SubMap

Объединяйте descendingMap() с представлением для навигации в обратном порядке:

TreeMap<Integer, String> map = new TreeMap<>();
for (int i = 10; i <= 100; i += 10) map.put(i, "v"+i);

// Get [40, 80] in descending order
map.subMap(40, true, 80, true)
   .descendingMap()
   .forEach((k,v) -> System.out.println(k + "=" + v));
// 80=v80, 70=v70, 60=v60, 50=v50, 40=v40

Интерфейс NavigableMap

NavigableMap расширяет SortedMap и добавляет навигацию по ключам с помощью ceiling, floor, higher и lower, а также представления в обратном порядке. TreeMap — наиболее распространённая реализация; ConcurrentSkipListMap — безопасная при работе с потоками альтернатива.

Производительность представлений

Операции над представлением подкарты (get, put, containsKey) имеют ту же сложность O(log n), что и операции над исходной TreeMap. Создание самого представления имеет сложность O(1) — копирование не выполняется. Обход диапазона из n ключей в представлении имеет сложность O(log N + n), где N — полный размер карты.

Проблема: устаревшие представления

Поскольку представления связаны с исходной картой, представление может стать пустым или вызвать исключение, если исходная карта была очищена. Всегда документируйте, что представления являются динамическими, и не сохраняйте их дольше предусмотренного срока жизни.

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "a"); map.put(20, "b"); map.put(30, "c");

var view = map.subMap(10, 30);
map.clear(); // view becomes empty
System.out.println(view.size()); // 0 — but no exception

Быстрая проверка

Вы вызываете map.subMap(30, false, 70, true) для TreeMap с ключами {10,20,30,40,50,60,70,80}. Какие ключи входят в результат?

Повторение: подкарты и представления диапазонов

Основные выводы:

  • subMap, headMap и tailMap возвращают динамические связанные представления — копирование не выполняется
  • Изменения в представлении отражаются в исходной карте и наоборот
  • Используйте четырёхаргументный subMap(from, fromInclusive, to, toInclusive) для полного контроля над границами
  • Операции put за пределами диапазона через представление приводят к IllegalArgumentException
  • Сложность обхода диапазона: O(log N + n)

Часто задаваемые вопросы

Урок «Подкарты и представления диапазонов» бесплатный?

Да — полный текст урока «Подкарты и представления диапазонов» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Java Academy, подпишись на CoddyKit PRO. Курс Java Academy содержит 4 уроков всего.

Чему я научусь в уроке «Подкарты и представления диапазонов»?

Извлекайте представления subMap, headMap и tailMap для поиска по диапазонам в отсортированных картах. Ты практикуешь Java Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Java Academy?

Предыдущий опыт не требуется. Java Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.

Сколько времени занимает урок «Подкарты и представления диапазонов»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Java Academy?

Да. Каждый урок Java Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. TreeMap: отсортированные пары ключ–значение
  2. Подкарты и представления диапазонов
  3. TreeSet и NavigableSet
  4. Пользовательский порядок в древовидных коллекциях
← Назад к Java Academy