В чем разница между SortedMap и LinkedHashMap?

# Разница между SortedMap и LinkedHashMap

Определение

SortedMap интерфейс (interface) для Map, где ключи отсортированы по какому-то порядку.

LinkedHashMap конкретная реализация Map, которая сохраняет порядок вставки элементов.

Это разные концепции: один это контракт (interface), другой конкретная реализация.

SortedMap — интерфейс с сортировкой

SortedMap это интерфейс, который гарантирует, что ключи отсортированы в определённом порядке.

import java.util.*;

public class SortedMapExample {
    public static void main(String[] args) {
        // TreeMap реализует SortedMap
        SortedMap<String, Integer> map = new TreeMap<>();
        
        map.put("banana", 2);
        map.put("apple", 1);
        map.put("cherry", 3);
        
        // Ключи автоматически отсортированы
        for (String key : map.keySet()) {
            System.out.println(key);  // apple, banana, cherry
        }
    }
}

Характеристики:

• Interface, не конкретный класс
• Ключи отсортированы
• Сравнивает ключи при добавлении
• Можно получить подмножество (subMap, headMap, tailMap)
• Реализация: TreeMap (красно-чёрное дерево)

LinkedHashMap — сохранение порядка вставки

LinkedHashMap это конкретная реализация, которая запоминает порядок вставки элементов.

import java.util.*;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        // LinkedHashMap сохраняет порядок добавления
        LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
        
        map.put("banana", 2);
        map.put("apple", 1);
        map.put("cherry", 3);
        
        // Ключи в порядке добавления
        for (String key : map.keySet()) {
            System.out.println(key);  // banana, apple, cherry
        }
    }
}

Характеристики:

• Конкретный класс
• Сохраняет порядок вставки элементов
• Использует двусвязный список (linked list)
• Быстрее, чем TreeMap
• Может также работать с порядком последнего обращения

Основные различия

Практический пример — SortedMap

import java.util.*;

public class SortedMapComparison {
    public static void main(String[] args) {
        // Пример: сортировка по алфавиту
        SortedMap<String, Integer> scores = new TreeMap<>();
        
        scores.put("Charlie", 85);
        scores.put("Alice", 90);
        scores.put("Bob", 88);
        
        // Ключи отсортированы: Alice, Bob, Charlie
        scores.forEach((name, score) -> 
            System.out.println(name + ": " + score)
        );  // Alice: 90, Bob: 88, Charlie: 85
        
        // Методы SortedMap
        System.out.println(scores.firstKey());   // Alice
        System.out.println(scores.lastKey());    // Charlie
        
        // Подмножество
        SortedMap<String, Integer> subset = 
            scores.subMap("Alice", "Charlie");
        // Alice: 90, Bob: 88
    }
}

Практический пример — LinkedHashMap

import java.util.*;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        // Пример: сохранение порядка истории
        LinkedHashMap<String, String> userActions = 
            new LinkedHashMap<>();
        
        userActions.put("1", "Login");
        userActions.put("2", "View Profile");
        userActions.put("3", "Edit Settings");
        userActions.put("4", "Logout");
        
        // Порядок как в истории
        userActions.forEach((id, action) -> 
            System.out.println(id + ": " + action)
        );  // 1: Login, 2: View Profile, 3: Edit Settings, 4: Logout
    }
}

Сортировка с кастомным компаратором

import java.util.*;

public class CustomSortedMap {
    public static void main(String[] args) {
        // SortedMap с кастомным компаратором (обратный порядок)
        SortedMap<String, Integer> descending = 
            new TreeMap<>((a, b) -> b.compareTo(a));
        
        descending.put("apple", 1);
        descending.put("banana", 2);
        descending.put("cherry", 3);
        
        // Обратный порядок
        descending.forEach((k, v) -> 
            System.out.println(k)  // cherry, banana, apple
        );
    }
}

LinkedHashMap с порядком доступа (LRU)

import java.util.*;

public class LRUCache {
    public static void main(String[] args) {
        // LinkedHashMap может отслеживать порядок доступа
        LinkedHashMap<String, String> lru = 
            new LinkedHashMap<String, String>(16, 0.75f, true) { 
                // accessOrder = true
                protected boolean removeEldestEntry(Map.Entry eldest) {
                    return size() > 3;  // Максимум 3 элемента
                }
            };
        
        lru.put("a", "1");
        lru.put("b", "2");
        lru.put("c", "3");
        
        lru.get("a");  // Осуществляем доступ
        lru.put("d", "4");  // Удалит "b" (был давно не использован)
        
        System.out.println(lru.keySet());  // [a, c, d]
    }
}

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

Используй SortedMap (TreeMap):

• Когда нужны ключи отсортированы
• Когда нужны операции subMap, headMap, tailMap
• Когда компаратор важен
• Нужна навигация по диапазону ключей

SortedMap<Integer, String> rankings = new TreeMap<>();
rankings.put(3, "Bronze");
rankings.put(2, "Silver");
rankings.put(1, "Gold");

// Получить лучшие 2
rankings.subMap(1, 3).forEach((k, v) -> 
    System.out.println(k + ": " + v)
);  // 1: Gold, 2: Silver

Используй LinkedHashMap:

• Когда нужен порядок вставки
• Когда нужна история событий
• LRU cache
• Когда важна предсказуемость порядка

LinkedHashMap<String, Integer> visitLog = new LinkedHashMap<>();
visitLog.put("Home", 1);
visitLog.put("Products", 2);
visitLog.put("Checkout", 3);
// Логирует в порядке посещения

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

// SortedMap (TreeMap) O(log n)
SortedMap<Integer, String> sorted = new TreeMap<>();
sorted.put(100, "value");      // O(log n)
String v = sorted.get(100);    // O(log n)

// LinkedHashMap O(1)
LinkedHashMap<Integer, String> linked = new LinkedHashMap<>();
linked.put(100, "value");      // O(1)
String v = linked.get(100);    // O(1)

Итог

• SortedMap это интерфейс для отсортированных Map (реализация TreeMap), используй когда нужна сортировка
• LinkedHashMap это класс, сохраняет порядок вставки, быстрее SortedMap для большинства операций

Они решают разные задачи: SortedMap для сортировки, LinkedHashMap для сохранения порядка вставки.