TreeMap: примеры (JAVA)

Примеры использования TreeMap

Пример 1: Создание и базовые операции

import java.util.*;
public class Example1 {
    public static void main(String[] args) {
        TreeMap map = new TreeMap<>();
        map.put(3, "три");
        map.put(1, "один");
        map.put(2, "два");
        System.out.println(map);                    // {1=один, 2=два, 3=три}
        System.out.println(map.get(2));             // два
        System.out.println(map.remove(1));          // один
        System.out.println(map);                    // {2=два, 3=три}
    }
}

{1=один, 2=два, 3=три}
два
один
{2=два, 3=три}

Пример 2: firstKey / lastKey и подкарты

TreeMap map = new TreeMap<>();
map.put(10, "десять");
map.put(20, "двадцать");
map.put(30, "тридцать");
map.put(40, "сорок");
System.out.println("firstKey: " + map.firstKey());          // 10
System.out.println("lastKey: " + map.lastKey());            // 40
System.out.println("subMap(20,40): " + map.subMap(20,40));  // {20=двадцать, 30=тридцать}
System.out.println("headMap(30): " + map.headMap(30));      // {10=десять, 20=двадцать}
System.out.println("tailMap(20): " + map.tailMap(20));      // {20=двадцать, 30=тридцать, 40=сорок}

firstKey: 10
lastKey: 40
subMap(20,40): {20=двадцать, 30=тридцать}
headMap(30): {10=десять, 20=двадцать}
tailMap(20): {20=двадцать, 30=тридцать, 40=сорок}

Пример 3: Пользовательский компаратор

TreeMap map = new TreeMap<>(Comparator.reverseOrder());
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
System.out.println(map);  // {cherry=3, banana=2, apple=1}

{cherry=3, banana=2, apple=1}

Аналоги в Java

• HashMap - не поддерживает порядок ключей. Лучший выбор, если порядок не важен и требуется максимальная производительность (O(1) вставка/поиск).
• LinkedHashMap - сохраняет порядок вставки или порядок последнего доступа (access order). Подходит для кэшей (LRU).
• ConcurrentSkipListMap - потокобезопасная версия сортированной карты на основе skip-list. Используется в многопоточных сценариях, когда нужна сортировка и безопасность.

Когда выбирать TreeMap: требуется упорядоченный по ключам доступ, операции по диапазону, нахождение ближайших ключей. Если сортировка не нужна, HashMap эффективнее. Если важна потокобезопасность, ConcurrentSkipListMap предпочтительнее, хотя TreeMap может быть обернута в Collections.synchronizedSortedMap.

Альтернативы в других языках

PHP - ассоциативные массивы ([]), сортировка через ksort() или sort(). Нет встроенного дерева, но можно использовать SplObjectStorage? Зато есть SPL класс SplPriorityQueue, но это очередь, не карта. Для сортированных пар ключ-значение можно использовать массивы с последующей сортировкой.

$arr = [3 => "три", 1 => "один", 2 => "два"];
ksort($arr);
print_r($arr); // Array ( [1] => один [2] => два [3] => три )

Array ( [1] => один [2] => два [3] => три )

JavaScript - объект {} не гарантирует порядок ключей (но современные браузеры строковые ключи упорядочивают по времени добавления). Map сохраняет порядок вставки. Для сортировки ключей можно использовать массив ключей и сортировку.

const map = new Map([[3,"три"],[1,"один"],[2,"два"]]);
const sorted = new Map([...map.entries()].sort((a,b)=>a[0]-b[0]));
console.log([...sorted]); // [[1,"один"],[2,"два"],[3,"три"]]

[ [1, "один"], [2, "два"], [3, "три"] ]

Python - словарь (dict) с Python 3.7 сохраняет порядок вставки. Для сортировки по ключам используется sorted(dict.items()). Модуль sortedcontainers (сторонний) предоставляет SortedDict.

d = {3: "три", 1: "один", 2: "два"}
sorted_d = dict(sorted(d.items()))
print(sorted_d)  # {1: 'один', 2: 'два', 3: 'три'}

{1: 'один', 2: 'два', 3: 'три'}

SQL - ключ-значение хранятся в таблицах, сортировка задается через ORDER BY. Для эффективного поиска по диапазону используются индексы и B-деревья.

SELECT key, value FROM kv_table ORDER BY key;

C# - SortedDictionary (на основе красно-черного дерева) и SortedList. SortedDictionary быстрее на вставку/удаление, SortedList - на доступ по индексу.

var map = new SortedDictionary();
map.Add(3, "три");
map.Add(1, "один");
map.Add(2, "два");
Console.WriteLine(string.Join(", ", map)); // [1, один], [2, два], [3, три]

[1, один], [2, два], [3, три]

Lua - таблицы не гарантируют порядок. Для сортировки ключей используют table.sort итерацию по отсортированному массиву ключей.

local t = {[3]="три", [1]="один", [2]="два"}
local keys = {}
for k in pairs(t) do table.insert(keys, k) end
table.sort(keys)
for _, k in ipairs(keys) do print(k, t[k]) end

1   один
2   два
3   три

Go - встроенная map не упорядочена. Для сортировки ключей нужно собирать ключи в срез и сортировать.

m := map[int]string{3:"три", 1:"один", 2:"два"}
keys := make([]int, 0, len(m))
for k := range m { keys = append(keys, k) }
sort.Ints(keys)
for _, k := range keys { fmt.Println(k, m[k]) }

1 один
2 два
3 три

Kotlin - sortedMapOf (возвращает TreeMap) и mutableMapOf. Есть расширения для сортировки.

val map = sortedMapOf(3 to "три", 1 to "один", 2 to "два")
println(map) // {1=один, 2=два, 3=три}

{1=один, 2=два, 3=три}

Типичные ошибки

1. Использование null в качестве ключа - TreeMap не допускает null ключи (в отличие от HashMap). Бросается NullPointerException.

TreeMap map = new TreeMap<>();
map.put(null, 1);  // NullPointerException

Exception in thread "main" java.lang.NullPointerException

2. Отсутствие Comparator или Comparable для ключей - если ключи не реализуют Comparable и не передан компаратор, при вставке бросается ClassCastException.

class Key { int id; }  // не Comparable
TreeMap map = new TreeMap<>();
map.put(new Key(), "value");  // ClassCastException

Exception in thread "main" java.lang.ClassCastException: class Key cannot be cast to class java.lang.Comparable

3. Изменение ключа после вставки - если ключ mutable и его хеш/сравнение меняется, TreeMap может нарушить структуру. Рекомендуется использовать immutable ключи.

4. ConcurrentModificationException при одновременной итерации и модификации - если коллекция изменяется итератором во время обхода (кроме методов remove самого итератора).

TreeMap map = new TreeMap<>();
for (Integer k : map.keySet()) {
    if (k == 2) map.put(5, "новый");  // ConcurrentModificationException
}

Exception in thread "main" java.util.ConcurrentModificationException

Изменения в версиях

В Java 8 в интерфейс Map были добавлены default методы: replace, replaceAll, computeIfAbsent, computeIfPresent, compute, merge, forEach. Эти методы наследуются и доступны в TreeMap.

Java 9 ввела статические фабричные методы Map.of и Map.ofEntries, которые создают неизменяемые карты (но не TreeMap). TreeMap по-прежнему создается через конструктор.

Java 21 не принесла значительных изменений в TreeMap, за исключением внутренних оптимизаций производительности. Методы firstEntry, lastEntry, pollFirstEntry, pollLastEntry присутствуют с Java 6 (NavigableMap).

В будущих версиях возможно появление новых методов в NavigableMap, но пока их нет.

Расширенные примеры

Пример 1: Сортировка по длине строки (компаратор)

TreeMap map = new TreeMap<>(Comparator.comparingInt(String::length));
map.put("abc", 1);
map.put("z", 2);
map.put("hello", 3);
System.out.println(map); // {z=2, abc=1, hello=3}

{z=2, abc=1, hello=3}

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

Пример 2: Использование lowerKey, higherKey, floorKey, ceilingKey

TreeMap map = new TreeMap<>();
map.put(10, "десять");
map.put(20, "двадцать");
map.put(30, "тридцать");
System.out.println("lowerKey(20): " + map.lowerKey(20));   // 10
System.out.println("higherKey(20): " + map.higherKey(20)); // 30
System.out.println("floorKey(25): " + map.floorKey(25));   // 20
System.out.println("ceilingKey(25): " + map.ceilingKey(25)); // 30

lowerKey(20): 10
higherKey(20): 30
floorKey(25): 20
ceilingKey(25): 30

Пример 3: pollFirstEntry и pollLastEntry (атомарное удаление)

TreeMap map = new TreeMap<>();
map.put(1, "A");
map.put(2, "B");
map.put(3, "C");
System.out.println("pollFirst: " + map.pollFirstEntry()); // 1=A
System.out.println("pollLast: " + map.pollLastEntry());   // 3=C
System.out.println("остаток: " + map);                    // {2=B}

pollFirst: 1=A
pollLast: 3=C
остаток: {2=B}

Пример 4: Подкарта с включением обеих границ (через subMap с булевыми флагами inclusive)

TreeMap map = new TreeMap<>();
map.put(1,"a"); map.put(2,"b"); map.put(3,"c"); map.put(4,"d");
System.out.println(map.subMap(2, true, 4, true)); // {2=b, 3=c, 4=d}

{2=b, 3=c, 4=d}

Пример 5: Использование TreeMap с пользовательским объектом (реализация Comparable)

class Person implements Comparable<Person> {
    String name; int age;
    Person(String n, int a) { name=n; age=a; }
    public int compareTo(Person o) { return Integer.compare(this.age, o.age); }
    public String toString() { return name+"("+age+")"; }
}
TreeMap<Person, String> map = new TreeMap<>();
map.put(new Person("Alice",30), "QA");
map.put(new Person("Bob",25), "Dev");
map.put(new Person("Charlie",35), "PM");
System.out.println(map); // {Bob(25)=Dev, Alice(30)=QA, Charlie(35)=PM}

{Bob(25)=Dev, Alice(30)=QA, Charlie(35)=PM}

Пример 6: Обратный порядок с помощью Collections.reverseOrder()

TreeMap map = new TreeMap<>(Collections.reverseOrder());
map.put(1,"один"); map.put(2,"два"); map.put(3,"три");
System.out.println(map); // {3=три, 2=два, 1=один}

{3=три, 2=два, 1=один}

Пример 7: Итерация по записям и получение EntrySet

TreeMap map = new TreeMap<>();
map.put(1,"one"); map.put(2,"two"); map.put(3,"three");
for (Map.Entry<Integer,String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " -> " + entry.getValue());
}

1 -> one
2 -> two
3 -> three