Java TreeMap: мастерство отсортированных карт с практическими примерами

Java TreeMap

Изучите класс Java TreeMap — мощную, естественно отсортированную реализацию карты — с чёткими примерами, ключевыми операциями и продвинутыми техниками навигации.

Класс TreeMap является частью Java Collections Framework и предоставляет реализацию красно-чёрного дерева, которая хранит записи в отсортированном виде согласно естественному упорядочиванию ключей или пользовательскому Comparator. Он реализует интерфейс NavigableMap, добавляющий удобные методы для обхода и запросов к карте.

Создание TreeMap

Прежде чем использовать TreeMap, импортируйте пакет:

import java.util.TreeMap;

Затем создайте экземпляр:

TreeMap<Key, Value> numbers = new TreeMap<>();

По умолчанию ключи сортируются в естественном порядке возрастания. Если нужен пользовательский порядок, передайте Comparator в конструктор.

Key — уникальный идентификатор для каждой записи.
Value — данные, ассоциированные с ключом.

Обзор методов TreeMap

Класс предлагает богатый набор операций. Ниже ключевые категории с фрагментами кода.

Вставка элементов

put() — добавляет или заменяет пару ключ/значение.
putAll() — объединяет другую карту в эту.
putIfAbsent() — вставляет только если ключ отсутствует.

Пример:

import java.util.TreeMap;
class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> evenNumbers = new TreeMap<>();
        evenNumbers.put("Two", 2);
        evenNumbers.put("Four", 4);
        evenNumbers.putIfAbsent("Six", 6);
        System.out.println("TreeMap of even numbers: " + evenNumbers);
        TreeMap<String, Integer> numbers = new TreeMap<>();
        numbers.put("One", 1);
        numbers.putAll(evenNumbers);
        System.out.println("TreeMap of numbers: " + numbers);
    }
}

Вывод

TreeMap of even numbers: {Four=4, Six=6, Two=2} TreeMap of numbers: {Four=4, One=1, Six=6, Two=2}

Доступ к элементам

Использование представлений коллекций

entrySet() — возвращает все пары ключ/значение.
keySet() — возвращает все ключи.
values() — возвращает все значения.

Пример:

import java.util.TreeMap;
class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> numbers = new TreeMap<>();
        numbers.put("One", 1);
        numbers.put("Two", 2);
        numbers.put("Three", 3);
        System.out.println("TreeMap: " + numbers);
        System.out.println("Key/Value mappings: " + numbers.entrySet());
        System.out.println("Keys: " + numbers.keySet());
        System.out.println("Values: " + numbers.values());
    }
}

Вывод

TreeMap: {One=1, Three=3, Two=2} Key/Value mappings: [One=1, Three=3, Two=2] Keys: [One, Three, Two] Values: [1, 3, 2]

Получение значений

get() — возвращает значение для ключа или null, если отсутствует.
getOrDefault() — возвращает значение по умолчанию, если ключ отсутствует.

Пример:

import java.util.TreeMap;
class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> numbers = new TreeMap<>();
        numbers.put("One", 1);
        numbers.put("Two", 2);
        numbers.put("Three", 3);
        System.out.println("TreeMap: " + numbers);
        int value1 = numbers.get("Three");
        System.out.println("Using get(): " + value1);
        int value2 = numbers.getOrDefault("Five", 5);
        System.out.println("Using getOrDefault(): " + value2);
    }
}

Вывод

TreeMap: {One=1, Three=3, Two=2} Using get(): 3 Using getOrDefault(): 5

Удаление записей

remove(key) — удаляет запись и возвращает её значение.
remove(key, value) — удаляет только если ключ отображает указанное значение.

Пример:

import java.util.TreeMap;
class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> numbers = new TreeMap<>();
        numbers.put("One", 1);
        numbers.put("Two", 2);
        numbers.put("Three", 3);
        System.out.println("TreeMap: " + numbers);
        int removed = numbers.remove("Two");
        System.out.println("Removed value: " + removed);
        boolean removedPair = numbers.remove("Three", 3);
        System.out.println("Is the entry {Three=3} removed? " + removedPair);
        System.out.println("Updated TreeMap: " + numbers);
    }
}

Вывод

TreeMap: {One=1, Three=3, Two=2} Removed value: 2 Is the entry {Three=3} removed? true Updated TreeMap: {One=1}

Замена значений

replace(key, value) — обновляет значение для ключа.
replace(key, old, new) — обновляет только если текущее значение совпадает с old.
replaceAll(function) — применяет функцию к каждой записи.

Пример:

import java.util.TreeMap;
class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> numbers = new TreeMap<>();
        numbers.put("First", 1);
        numbers.put("Second", 2);
        numbers.put("Third", 3);
        System.out.println("Original TreeMap: " + numbers);
        numbers.replace("Second", 22);
        numbers.replace("Third", 3, 33);
        System.out.println("After replace(): " + numbers);
        numbers.replaceAll((k, v) -> v + 2);
        System.out.println("After replaceAll(): " + numbers);
    }
}

Вывод

Original TreeMap: {First=1, Second=2, Third=3} After replace(): {First=1, Second=22, Third=33} After replaceAll(): {First=3, Second=24, Third=35}

Поскольку TreeMap реализует NavigableMap, он предлагает методы для эффективного запроса структуры.

Первый и последний элементы

firstKey() — первый ключ в порядке.
firstEntry() — запись для первого ключа.
lastKey() — последний ключ.
lastEntry() — запись для последнего ключа.

Пример:

import java.util.TreeMap;
class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> numbers = new TreeMap<>();
        numbers.put("First", 1);
        numbers.put("Second", 2);
        numbers.put("Third", 3);
        System.out.println("TreeMap: " + numbers);
        System.out.println("First Key: " + numbers.firstKey());
        System.out.println("Last Key: " + numbers.lastKey());
        System.out.println("First Entry: " + numbers.firstEntry());
        System.out.println("Last Entry: " + numbers.lastEntry());
    }
}

Вывод

TreeMap: {First=1, Second=2, Third=3} First Key: First Last Key: Third First Entry: First=1 Last Entry: Third=3

Ceiling, Floor, Higher и Lower

Эти методы возвращают ключи или записи относительно заданного ключа, облегчая запросы диапазонов.

higherKey(), higherEntry() — следующий более высокий ключ/запись.
lowerKey(), lowerEntry() — предыдущий более низкий ключ/запись.
ceilingKey(), ceilingEntry() — наименьший ключ/запись ≥ заданного ключа.
floorKey(), floorEntry() — наибольший ключ/запись ≤ заданного ключа.

Пример:

import java.util.TreeMap;
class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> numbers = new TreeMap<>();
        numbers.put("First", 1);
        numbers.put("Second", 5);
        numbers.put("Third", 4);
        numbers.put("Fourth", 6);
        System.out.println("TreeMap: " + numbers);
        System.out.println("higherKey('Fourth'): " + numbers.higherKey("Fourth"));
        System.out.println("higherEntry('Fourth'): " + numbers.higherEntry("Fourth"));
        System.out.println("lowerKey('Fourth'): " + numbers.lowerKey("Fourth"));
        System.out.println("lowerEntry('Fourth'): " + numbers.lowerEntry("Fourth"));
        System.out.println("ceilingKey('Fourth'): " + numbers.ceilingKey("Fourth"));
        System.out.println("ceilingEntry('Fourth'): " + numbers.ceilingEntry("Fourth"));
        System.out.println("floorKey('Fourth'): " + numbers.floorKey("Fourth"));
        System.out.println("floorEntry('Fourth'): " + numbers.floorEntry("Fourth"));
    }
}

Вывод

TreeMap: {First=1, Fourth=6, Second=5, Third=4} higherKey('Fourth'): Second higherEntry('Fourth'): Second=5 lowerKey('Fourth'): First lowerEntry('Fourth'): First=1 ceilingKey('Fourth'): Fourth ceilingEntry('Fourth'): Fourth=6 floorKey('Fourth'): Fourth floorEntry('Fourth'): Fourth=6

Polling и диапазоны

pollFirstEntry() и pollLastEntry() удаляют и возвращают первую/последнюю записи соответственно.

import java.util.TreeMap;
class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> numbers = new TreeMap<>();
        numbers.put("First", 1);
        numbers.put("Second", 2);
        numbers.put("Third", 3);
        System.out.println("TreeMap: " + numbers);
        System.out.println("pollFirstEntry(): " + numbers.pollFirstEntry());
        System.out.println("pollLastEntry(): " + numbers.pollLastEntry());
        System.out.println("Updated TreeMap: " + numbers);
    }
}

Вывод

TreeMap: {First=1, Second=2, Third=3} pollFirstEntry(): First=1 pollLastEntry(): Third=3 Updated TreeMap: {Second=2}

headMap, tailMap, subMap

Эти методы предоставляют представления над конкретными диапазонами ключей.

headMap(toKey, inclusive) — ключи < toKey (или ≤ если inclusive).
tailMap(fromKey, inclusive) — ключи ≥ fromKey (или > если exclusive).
subMap(fromKey, fromInclusive, toKey, toInclusive) — ключи между двумя границами.

Пример:

import java.util.TreeMap;
class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> numbers = new TreeMap<>();
        numbers.put("First", 1);
        numbers.put("Second", 2);
        numbers.put("Third", 3);
        numbers.put("Fourth", 4);
        System.out.println("TreeMap: " + numbers);
        System.out.println("headMap('Fourth'): " + numbers.headMap("Fourth"));
        System.out.println("headMap('Fourth', true): " + numbers.headMap("Fourth", true));
        System.out.println("tailMap('Second'): " + numbers.tailMap("Second"));
        System.out.println("tailMap('Second', false): " + numbers.tailMap("Second", false));
        System.out.println("subMap('Fourth', true, 'Third', false): " + numbers.subMap("Fourth", true, "Third", false));
    }
}

Вывод

TreeMap: {First=1, Fourth=4, Second=2, Third=3} headMap('Fourth'): {First=1} headMap('Fourth', true): {First=1, Fourth=4} tailMap('Second'): {Second=2, Third=3, Fourth=4} tailMap('Second', false): {Third=3, Fourth=4} subMap('Fourth', true, 'Third', false): {Fourth=4, Second=2}

Дополнительные утилитарные методы

Метод	Описание
`clone()`	Создаёт поверхностную копию карты.
`containsKey()`	Проверяет наличие ключа.
`containsValue()`	Проверяет конкретное значение.
`size()`	Возвращает количество записей.
`clear()`	Удаляет все записи.

Пользовательское упорядочивание ключей с Comparator

Для другой сортировки ключей — например, обратный порядок или нечувствительная к регистру строки — реализуйте Comparator и передайте его в конструктор TreeMap.

import java.util.TreeMap;
import java.util.Comparator;
class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> numbers = new TreeMap<>(new CustomComparator());
        numbers.put("First", 1);
        numbers.put("Second", 2);
        numbers.put("Third", 3);
        numbers.put("Fourth", 4);
        System.out.println("TreeMap: " + numbers);
    }
    static class CustomComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            // Обратный естественный порядок
            return a.compareTo(b) * -1;
        }
    }
}

Вывод

TreeMap: {Third=3, Second=2, Fourth=4, First=1}

Для большего о Comparator см. официальную документацию Java.

Освоение Java NavigableMap: возможности, методы и реализация TreeMap Освоение ConcurrentMap в Java: потокобезопасные карты разъяснены

java

Java TreeMap: мастерство отсортированных карт с практическими примерами

Java TreeMap

Создание TreeMap

Обзор методов TreeMap

Вставка элементов

Доступ к элементам

Использование представлений коллекций

Получение значений

Удаление записей

Замена значений

Навигационные методы

Первый и последний элементы

Ceiling, Floor, Higher и Lower

Polling и диапазоны

headMap, tailMap, subMap

Дополнительные утилитарные методы

Пользовательское упорядочивание ключей с Comparator