Что значит Sorted в SortedMap?

SortedMap в Java

SortedMap — это интерфейс, который расширяет интерфейс Map и гарантирует, что все ключи хранятся в отсортированном порядке. "Sorted" означает, что ключи упорядочены согласно их естественному порядку (natural order) или пользовательскому компаратору (Comparator).

Основная идея

Обычный HashMap хранит элементы в произвольном порядке. SortedMap гарантирует, что при итерации по ключам они будут выданы в отсортированном порядке:

// HashMap — порядок произвольный
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("Виктор", 30);
hashMap.put("Алиса", 25);
hashMap.put("Боб", 28);

for (String name : hashMap.keySet()) {
    System.out.println(name); // Порядок не гарантирован: может быть Боб, Алиса, Виктор
}

// SortedMap — ключи всегда отсортированы
SortedMap<String, Integer> sortedMap = new TreeMap<>();
sortedMap.put("Виктор", 30);
sortedMap.put("Алиса", 25);
sortedMap.put("Боб", 28);

for (String name : sortedMap.keySet()) {
    System.out.println(name); // Всегда: Алиса, Боб, Виктор
}

Реализация — TreeMap

Основная реализация SortedMap — это TreeMap, которая использует красно-чёрное дерево (Red-Black Tree):

// TreeMap реализует SortedMap
SortedMap<String, Integer> map = new TreeMap<>();

map.put("Виктор", 30);
map.put("Алиса", 25);
map.put("Боб", 28);
map.put("Гена", 27);

// Итерация гарантирует порядок
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}
// Вывод (в алфавитном порядке):
// Алиса: 25
// Боб: 28
// Гена: 27
// Виктор: 30

Порядок сортировки

1. Естественный порядок (Natural Order)

Для строк — это алфавитный порядок. Для чисел — по величине:

SortedMap<Integer, String> intMap = new TreeMap<>();
intMap.put(3, "три");
intMap.put(1, "один");
intMap.put(2, "два");

for (Integer key : intMap.keySet()) {
    System.out.println(key); // Вывод: 1, 2, 3
}

2. Пользовательский порядок (Custom Comparator)

Можно задать свой порядок сортировки через Comparator:

// Отсортировать по убыванию
SortedMap<Integer, String> descendingMap = new TreeMap<>(
    Collections.reverseOrder()
);

descendingMap.put(3, "три");
descendingMap.put(1, "один");
descendingMap.put(2, "два");

for (Integer key : descendingMap.keySet()) {
    System.out.println(key); // Вывод: 3, 2, 1
}

// Пользовательский компаратор
SortedMap<String, Integer> customMap = new TreeMap<>(
    (a, b) -> Integer.compare(b.length(), a.length()) // По длине строки, по убыванию
);

customMap.put("Виктор", 30);
customMap.put("Алиса", 25);
customMap.put("Боб", 28);

for (String key : customMap.keySet()) {
    System.out.println(key); // Вывод: Виктор (6 букв), Алиса (5), Боб (3)
}

Методы SortedMap

SortedMap добавляет дополнительные методы для работы с отсортированными ключами:

SortedMap<String, Integer> map = new TreeMap<>();
map.put("Виктор", 30);
map.put("Алиса", 25);
map.put("Боб", 28);
map.put("Гена", 27);

// firstKey() — первый ключ (минимальный)
String firstKey = map.firstKey(); // "Алиса"
System.out.println("Первый ключ: " + firstKey);

// lastKey() — последний ключ (максимальный)
String lastKey = map.lastKey(); // "Виктор"
System.out.println("Последний ключ: " + lastKey);

// headMap(K toKey) — все ключи СТРОГО меньше toKey
SortedMap<String, Integer> headMap = map.headMap("Гена");
System.out.println("headMap: " + headMap); // {Алиса=25, Боб=28}

// tailMap(K fromKey) — все ключи больше или равны fromKey
SortedMap<String, Integer> tailMap = map.tailMap("Боб");
System.out.println("tailMap: " + tailMap); // {Боб=28, Гена=27, Виктор=30}

// subMap(K from, K to) — все ключи от from (включая) до to (исключая)
SortedMap<String, Integer> subMap = map.subMap("Боб", "Виктор");
System.out.println("subMap: " + subMap); // {Боб=28, Гена=27}

// comparator() — получить компаратор
Comparator<? super String> comp = map.comparator();
System.out.println("Компаратор: " + comp); // null (естественный порядок)

Практические примеры

Сортировка по доходу (объекты с пользовательским порядком)

public class Employee implements Comparable<Employee> {
    private String name;
    private double salary;
    
    public Employee(String name, double salary) {
        this.name = name;
        this.salary = salary;
    }
    
    @Override
    public int compareTo(Employee other) {
        return Double.compare(this.salary, other.salary);
    }
    
    @Override
    public String toString() {
        return name + " (" + salary + ")"; 
    }
}

public class Main {
    public static void main(String[] args) {
        SortedMap<Employee, String> employees = new TreeMap<>();
        
        employees.put(new Employee("Виктор", 50000), "Developer");
        employees.put(new Employee("Алиса", 60000), "Senior Developer");
        employees.put(new Employee("Боб", 40000), "Junior Developer");
        
        // Ключи отсортированы по зарплате (по возрастанию)
        for (Map.Entry<Employee, String> entry : employees.entrySet()) {
            System.out.println(entry.getKey() + " — " + entry.getValue());
        }
        // Вывод:
        // Боб (40000.0) — Junior Developer
        // Виктор (50000.0) — Developer
        // Алиса (60000.0) — Senior Developer
    }
}

Диапазонные запросы

SortedMap<Integer, String> years = new TreeMap<>();
years.put(2020, "начало");
years.put(2021, "развитие");
years.put(2022, "рост");
years.put(2023, "зрелость");
years.put(2024, "стабильность");

// Получить все события с 2021 по 2023 (исключая 2024)
SortedMap<Integer, String> period = years.subMap(2021, 2024);
System.out.println(period); // {2021=развитие, 2022=рост, 2023=зрелость}

Сравнение Map и SortedMap

Выводы

SortedMap — это мощный инструмент когда:

✓ Нужно хранить данные в отсортированном порядке ✓ Нужны диапазонные запросы (headMap, tailMap, subMap) ✓ Нужен доступ к минимальному или максимальному ключу ✓ Нужна итерация в определённом порядке

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