Какая структура Map?

Структура Map в Java

Map — одна из самых важных структур данных в Java Collections Framework. Это интерфейс для хранения пар ключ-значение с различными реализациями под разные сценарии.

Иерархия интерфейсов Map

public interface Map<K, V> {
    // Основные операции
    V put(K key, V value);
    V get(Object key);
    V remove(Object key);
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    int size();
    boolean isEmpty();
    void clear();
    
    // Представления
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
}

1. HashMap — хеш-таблица

Наиболее часто используемая реализация Map. Основана на хешировании:

public class HashMapStructure {
    // Внутренняя структура HashMap:
    static class Node<K, V> {
        final int hash;              // хеш ключа
        final K key;                 // ключ
        V value;                     // значение
        Node<K, V> next;            // для цепочки (коллизий)
    }
    
    // Массив buckets
    transient Node<K, V>[] table;   // размер обычно 2^n
    
    // С Java 8: преобразование в TreeNode при > 8 коллизий
    static final class TreeNode<K, V> extends Node<K, V> {
        TreeNode<K, V> parent;
        TreeNode<K, V> left;
        TreeNode<K, V> right;       // Red-Black Tree
    }
}

// Практическое использование:
Map<String, Integer> map = new HashMap<>();
map.put("apple", 100);
map.put("banana", 200);
map.put("cherry", 150);

Integer price = map.get("apple");  // O(1)
map.remove("banana");               // O(1)

// Итерация
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

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

• Сложность: O(1) get/put/remove в среднем, O(n) в худшем
• Порядок: не гарантирует порядок итерации
• Потокобезопасность: нет (используй Collections.synchronizedMap())
• Null ключи: один null ключ разрешён
• Null значения: разрешены

2. LinkedHashMap — упорядоченная хеш-таблица

Расширение HashMap, сохраняющее порядок вставки элементов:

public class LinkedHashMapStructure {
    // Расширяет HashMap с двусвязным списком
    static class LinkedHashMapEntry<K, V> extends HashMap.Node<K, V> {
        LinkedHashMapEntry<K, V> before;  // предыдущий
        LinkedHashMapEntry<K, V> after;   // следующий
    }
    
    // Голова списка (самый старый элемент)
    transient LinkedHashMapEntry<K, V> head;
    // Хвост списка (самый новый элемент)
    transient LinkedHashMapEntry<K, V> tail;
}

// Практическое использование:
Map<String, Integer> map = new LinkedHashMap<>();
map.put("first", 1);
map.put("second", 2);
map.put("third", 3);

// Итерация в порядке вставки
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey());  // first, second, third
}

// Access-order LinkedHashMap (для LRU кэша)
Map<String, Integer> lru = new LinkedHashMap<String, Integer>(16, 0.75f, true) {
    @Override
    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");      // "a" становится самым новым
lru.put("d", 4);   // удалено "b" (самый старый)

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

• Сложность: O(1) операции как HashMap
• Порядок: гарантирует порядок вставки или доступа
• Память: больше памяти (двусвязный список)
• Применение: LRU кэш, сохранение порядка

3. TreeMap — отсортированная карта

Реализация на основе Red-Black Tree. Сохраняет элементы отсортированными по ключам:

public class TreeMapStructure {
    // Red-Black Tree узел
    static final class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> left;      // левое поддерево
        Entry<K, V> right;     // правое поддерево
        Entry<K, V> parent;    // родитель
        boolean color = BLACK; // RED or BLACK для баланса
    }
    
    // Корень дерева
    private transient Entry<K, V> root;
    private transient int size = 0;
}

// Практическое использование:
Map<Integer, String> map = new TreeMap<>();
map.put(5, "five");
map.put(2, "two");
map.put(8, "eight");
map.put(1, "one");

// Автоматически отсортировано по ключам
for (Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}
// Вывод: 1:one, 2:two, 5:five, 8:eight

// Операции с диапазонами
SortedMap<Integer, String> subMap = map.subMap(2, 8);
// Содержит: 2:two, 5:five

SortedMap<Integer, String> headMap = map.headMap(5);
// Содержит все ключи < 5: 1:one, 2:two

SortedMap<Integer, String> tailMap = map.tailMap(5);
// Содержит все ключи >= 5: 5:five, 8:eight

// NavigableMap (Java 6+)
NavigableMap<Integer, String> nav = map;
System.out.println(nav.floorEntry(7).getValue());    // five (<=7)
System.out.println(nav.ceilingEntry(7).getValue());  // eight (>=7)
System.out.println(nav.lowerEntry(5).getValue());    // two (<5)
System.out.println(nav.higherEntry(5).getValue());   // eight (>5)

// Обратный порядок
for (Map.Entry<Integer, String> entry : nav.descendingMap().entrySet()) {
    System.out.println(entry.getKey());  // 8, 5, 2, 1
}

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

• Сложность: O(log n) get/put/remove
• Порядок: отсортирован по ключам (естественный или Comparator)
• Потокобезопасность: нет
• Применение: отсортированные данные, операции диапазона

4. ConcurrentHashMap — потокобезопасная карта

Оптимизированная для многопоточных приложений:

public class ConcurrentHashMapStructure {
    // Разделена на сегменты (segments) для параллелизма
    static final class Node<K, V> {
        final int hash;
        final K key;
        volatile V value;     // volatile для видимости
        volatile Node<K, V> next;
    }
    
    // Массив buckets подразделяется на сегменты
    // Разные потоки могут работать с разными сегментами параллельно
}

// Практическое использование:
Map<String, Integer> map = new ConcurrentHashMap<>();

// Потокобезопасные операции
map.put("key1", 100);
map.putIfAbsent("key1", 200);  // Вернёт 100
map.putIfAbsent("key2", 200);  // Вернёт null

// Compute операции (атомарные)
map.compute("key1", (k, v) -> v == null ? 100 : v + 50);

map.computeIfPresent("key1", (k, v) -> v * 2);

map.computeIfAbsent("key3", k -> {
    // Только если ключа нет
    return 300;
});

// Merge операции
map.merge("key1", 50, Integer::sum);  // добавить 50 к существующему

// Итерация (безопасная против изменений)
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

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

• Сложность: O(1) операции в среднем
• Потокобезопасность: да (segment locking)
• Порядок: не гарантирует порядок
• Null: нет поддержки null ключей и значений
• Применение: многопоточные приложения

5. WeakHashMap — карта со слабыми ссылками

Использует слабые ссылки для ключей (для автоматической сборки мусора):

public class WeakHashMapExample {
    public static void main(String[] args) throws InterruptedException {
        Map<String, String> map = new WeakHashMap<>();
        
        String key = new String("temporary");
        map.put(key, "value");
        
        System.out.println("Size before: " + map.size());  // 1
        
        key = null;  // ключ на удаление
        System.gc(); // сборка мусора
        Thread.sleep(100);
        
        System.out.println("Size after GC: " + map.size());  // 0 (элемент удалён)
    }
}

6. Сравнение всех реализаций Map

Практический пример: выбор реализации

public class MapSelectionExample {
    // Быстрый доступ, порядок не важен
    void example1() {
        Map<String, User> userCache = new HashMap<>();
        userCache.put("123", new User("123", "John"));
    }
    
    // Нужен порядок вставки (например, LRU кэш)
    void example2() {
        Map<String, String> recentlyUsed = new LinkedHashMap<String, String>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > 100;
            }
        };
    }
    
    // Нужна сортировка по ключам
    void example3() {
        Map<Integer, String> ranking = new TreeMap<>(Collections.reverseOrder());
        ranking.put(3, "third");
        ranking.put(1, "first");
        ranking.put(2, "second");
        // Итерация в порядке убывания
    }
    
    // Многопоточное приложение
    void example4() {
        Map<String, Integer> counters = new ConcurrentHashMap<>();
        // Много потоков могут обновлять без synchronized
    }
    
    // Кэш со слабыми ссылками
    void example5() {
        Map<String, byte[]> imageCache = new WeakHashMap<>();
        // Изображения автоматически удалятся при нехватке памяти
    }
}

Резюме: структура Map

HashMap — основная реализация, О(1) операции LinkedHashMap — упорядоченная, для LRU кэшей TreeMap — отсортированная, для диапазонов ConcurrentHashMap — потокобезопасная, для многопоточности WeakHashMap — слабые ссылки для автоматической очистки

ЗОЛОТОЕ ПРАВИЛО: Выбирай HashMap, пока не будет причины для выбора чего-то другого!