2.1.2. Map и её реализации

HashMap, TreeMap, LinkedHashMap, ConcurrentHashMap

Материалы

Тип	Ссылка
Документ	ссылка
Видео	ссылка

Что такое Map

Map - это интерфейс для хранения пар ключ-значение (key-value).

Каждый ключ уникален (не может повторяться)
Каждый ключ соответствует максимум одному значению
Map НЕ является коллекцией (не наследует Collection), но содержит collection-view операции

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);
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
}

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

Map<K, V>
├── SortedMap<K, V>
│   └── NavigableMap<K, V>
└── ConcurrentMap<K, V>
    └── ConcurrentNavigableMap<K, V>

HashMap - основная реализация

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

Структура данных: Hash Table (хеш-таблица с массивом и списками/деревьями)
Порядок: НЕ гарантируется и может меняться
Производительность: O(1) для get/put/remove (в среднем)
Null: один null-ключ разрешен, null-значения разрешены
Синхронизация: НЕ потокобезопасен

Внутреннее устройство (Java 8+)

HashMap = Array of Buckets
  bucket[0] → Node → Node → ...
  bucket[1] → TreeNode (если > 8 коллизий)
  bucket[2] → Node
  ...

Важные параметры:

initialCapacity (по умолчанию 16) - начальный размер массива
loadFactor (по умолчанию 0.75) - коэффициент заполнения для расширения
При достижении size > capacity * loadFactor происходит rehashing (увеличение в 2 раза)

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

Map<String, Integer> ages = new HashMap<>();
ages.put("Alice", 30);
ages.put("Bob", 25);
ages.put("Alice", 31);  // Заменит предыдущее значение

Integer age = ages.get("Alice");  // 31
boolean hasKey = ages.containsKey("Bob");  // true
boolean hasValue = ages.containsValue(25);  // true

ages.remove("Bob");

Итерация по HashMap

// 1. Через entrySet (рекомендуется)
for (Map.Entry<String, Integer> entry : ages.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    System.out.println(key + " = " + value);
}

// 2. Через keySet
for (String key : ages.keySet()) {
    Integer value = ages.get(key);
    System.out.println(key + " = " + value);
}

// 3. Через values (только значения)
for (Integer value : ages.values()) {
    System.out.println(value);
}

// 4. forEach (Java 8+)
ages.forEach((key, value) -> 
    System.out.println(key + " = " + value)
);

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

✅ По умолчанию для Map ✅ Порядок не важен ✅ Нужна максимальная скорость ✅ Однопоточное использование

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

Операция	Средний случай	Худший случай
get	O(1)	O(n) → O(log n) (с Java 8)
put	O(1)	O(n) → O(log n)
remove	O(1)	O(n) → O(log n)
containsKey	O(1)	O(n) → O(log n)

LinkedHashMap - HashMap с порядком

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

Структура данных: Hash Table + Doubly-Linked List
Порядок: сохраняется порядок вставки (insertion-order) или порядок доступа (access-order)
Производительность: чуть медленнее HashMap из-за поддержки linked list
Null: один null-ключ разрешен, null-значения разрешены
Синхронизация: НЕ потокобезопасен

Два режима порядка

1. Insertion-Order (по умолчанию)

Map<String, Integer> map = new LinkedHashMap<>();
map.put("First", 1);
map.put("Second", 2);
map.put("Third", 3);

// Итерация в порядке добавления: First, Second, Third
for (String key : map.keySet()) {
    System.out.println(key);
}

2. Access-Order (для LRU кэша)

Map<String, Integer> lruMap = new LinkedHashMap<>(16, 0.75f, true);
//                                                           ^^^^
//                                                        accessOrder=true

lruMap.put("A", 1);
lruMap.put("B", 2);
lruMap.put("C", 3);
lruMap.get("A");  // Доступ к "A" - перемещается в конец

// Порядок теперь: B, C, A (A в конце как последний использованный)

LRU Cache на LinkedHashMap

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxEntries;
    
    public LRUCache(int maxEntries) {
        super(16, 0.75f, true);  // accessOrder = true
        this.maxEntries = maxEntries;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxEntries;  // Удалять самый старый при превышении
    }
}

// Использование
LRUCache<String, String> cache = new LRUCache<>(3);
cache.put("1", "one");
cache.put("2", "two");
cache.put("3", "three");
cache.put("4", "four");  // "1" удалится автоматически

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

✅ Нужен предсказуемый порядок итерации ✅ Реализация LRU/MRU кэша ✅ История операций в порядке выполнения ✅ Сериализация/десериализация с сохранением порядка

TreeMap - отсортированная Map

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

Структура данных: Red-Black Tree (сбалансированное бинарное дерево)
Порядок: отсортирован по ключам (natural ordering или Comparator)
Производительность: O(log n) для всех основных операций
Null: null-ключи запрещены (с Java 7), null-значения разрешены
Синхронизация: НЕ потокобезопасен
Интерфейсы: реализует NavigableMap и SortedMap

Natural Ordering (по умолчанию)

TreeMap<String, Integer> map = new TreeMap<>();
map.put("Charlie", 30);
map.put("Alice", 25);
map.put("Bob", 28);

// Итерация в алфавитном порядке: Alice, Bob, Charlie
for (String key : map.keySet()) {
    System.out.println(key + " = " + map.get(key));
}

Custom Comparator

// Сортировка по убыванию
TreeMap<String, Integer> descendingMap = new TreeMap<>(
    Comparator.reverseOrder()
);

// Сортировка по длине ключа
TreeMap<String, Integer> lengthMap = new TreeMap<>(
    Comparator.comparing(String::length)
              .thenComparing(Comparator.naturalOrder())
);

NavigableMap методы

Поиск ближайших элементов

TreeMap<Integer, String> scores = new TreeMap<>();
scores.put(100, "Alice");
scores.put(85, "Bob");
scores.put(90, "Charlie");
scores.put(95, "Dave");

// Навигационные методы
scores.lowerKey(90);        // 85 (наибольший < 90)
scores.floorKey(90);        // 90 (наибольший <= 90)
scores.ceilingKey(92);      // 95 (наименьший >= 92)
scores.higherKey(90);       // 95 (наименьший > 90)

scores.lowerEntry(90);      // Entry(85, "Bob")
scores.higherEntry(90);     // Entry(95, "Dave")

Диапазоны (subMap, headMap, tailMap)

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");
map.put(4, "four");
map.put(5, "five");

// Поддиапазон [2, 4)
NavigableMap<Integer, String> subMap = map.subMap(2, true, 4, false);
// {2=two, 3=three}

// Все элементы < 3
SortedMap<Integer, String> headMap = map.headMap(3);
// {1=one, 2=two}

// Все элементы >= 3
SortedMap<Integer, String> tailMap = map.tailMap(3);
// {3=three, 4=four, 5=five}

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

Map.Entry<Integer, String> first = map.firstEntry();  // 1=one
Map.Entry<Integer, String> last = map.lastEntry();    // 5=five

Integer firstKey = map.firstKey();  // 1
Integer lastKey = map.lastKey();    // 5

// Удалить и вернуть
Map.Entry<Integer, String> removed = map.pollFirstEntry();  // 1=one

Обратный порядок

NavigableMap<Integer, String> descending = map.descendingMap();
// Итерация в обратном порядке: 5, 4, 3, 2, 1

NavigableSet<Integer> descendingKeys = map.descendingKeySet();

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

✅ Нужна автоматическая сортировка по ключам ✅ Нужны операции навигации (nearest, range) ✅ Диапазоны элементов (от X до Y) ✅ Нужны первый/последний элемент ✅ Подсчет элементов в диапазоне

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

Операция	Сложность
get	O(log n)
put	O(log n)
remove	O(log n)
containsKey	O(log n)
firstKey	O(log n)
lastKey	O(log n)

ConcurrentHashMap - потокобезопасная Map

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

Структура данных: Segmented Hash Table (с Java 8 - Node array + CAS)
Порядок: не гарантируется
Производительность: высокая параллельность, lock-free чтение
Null: null-ключи и null-значения ЗАПРЕЩЕНЫ
Синхронизация: полностью потокобезопасен

Основные отличия от HashMap

// HashMap
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put(null, 1);      // ✅ OK
hashMap.put("key", null);  // ✅ OK

// ConcurrentHashMap
Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();
concurrentMap.put(null, 1);      // ❌ NullPointerException
concurrentMap.put("key", null);  // ❌ NullPointerException

Преимущества перед синхронизированной Map

// Старый подход - грубая синхронизация
Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());
synchronized (syncMap) {
    syncMap.forEach((k, v) -> process(k, v));  // Блокирует всю map
}

// Современный подход - высокая параллельность
ConcurrentHashMap<String, Integer> concurrentMap = new ConcurrentHashMap<>();
concurrentMap.forEach((k, v) -> process(k, v));  // Не блокирует

Атомарные операции

putIfAbsent

// Добавить только если ключа нет
Integer oldValue = map.putIfAbsent("key", 100);
// null если ключа не было, старое значение если был

// Эквивалентно, но атомарно:
if (!map.containsKey("key")) {
    map.put("key", 100);
}

computeIfAbsent

// Вычислить значение только если ключа нет
map.computeIfAbsent("key", k -> expensiveComputation());

// Типичный use case - кэширование
ConcurrentHashMap<String, User> userCache = new ConcurrentHashMap<>();
User user = userCache.computeIfAbsent(userId, id -> loadUserFromDB(id));

computeIfPresent

// Вычислить новое значение если ключ существует
map.computeIfPresent("key", (k, oldValue) -> oldValue + 1);

// null удалит entry
map.computeIfPresent("key", (k, v) -> null);  // Удалит ключ

compute

// Вычислить значение независимо от наличия ключа
map.compute("key", (k, oldValue) -> 
    oldValue == null ? 1 : oldValue + 1
);

merge

// Объединить значения
map.merge("key", 1, Integer::sum);
// Если ключа нет - вставит 1
// Если ключ есть - прибавит 1 к старому значению

// Счетчик слов
words.forEach(word -> 
    wordCount.merge(word, 1, Integer::sum)
);

replace

// Заменить значение
Integer old = map.replace("key", newValue);

// Заменить только если текущее значение совпадает (CAS)
boolean replaced = map.replace("key", expectedOld, newValue);

remove с условием

// Удалить только если значение совпадает
boolean removed = map.remove("key", expectedValue);

Bulk операции (Java 8+)

forEach

// Параллельная итерация
map.forEach(1, (key, value) -> 
    System.out.println(key + " = " + value)
);
//           ^ parallelismThreshold (1 = всегда параллельно)

search

// Поиск первого совпадения
String result = map.search(1, (key, value) -> 
    value > 100 ? key : null
);

reduce

// Суммирование значений
Integer sum = map.reduce(1,
    (key, value) -> value,           // transformer
    0,                                // basis
    Integer::sum                      // reducer
);

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

✅ Многопоточная среда с частыми чтениями И записями ✅ Producer-Consumer с общим состоянием ✅ Кэш с множественным доступом ✅ Нужны атомарные операции (putIfAbsent, compute, merge) ✅ Высокая параллельность критична

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

Чтение: Lock-free, O(1)
Запись: Segmented locking (с Java 8 - CAS), O(1)
Итерация: Weakly consistent (может не видеть последние изменения)

Сравнительная таблица Map реализаций

Характеристика	HashMap	LinkedHashMap	TreeMap	ConcurrentHashMap
Порядок	Нет	Вставки или доступа	Сортировка	Нет
get/put	O(1)	O(1)	O(log n)	O(1)
Null ключи	1 null	1 null	❌	❌
Null значения	✅	✅	✅	❌
Thread-safe	❌	❌	❌	✅
Память	Средне	Больше	Больше	Средне
Use case	По умолчанию	Порядок важен	Сортировка	Многопоточность

Выбор реализации Map

Блок-схема выбора

Нужна потокобезопасность?
├─ Да → ConcurrentHashMap
└─ Нет
    └─ Нужна сортировка?
        ├─ Да → TreeMap
        └─ Нет
            └─ Важен порядок вставки?
                ├─ Да → LinkedHashMap
                └─ Нет → HashMap

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

HashMap - стандартный кэш конфигурации

Map<String, String> config = new HashMap<>();
config.put("db.host", "localhost");
config.put("db.port", "5432");

LinkedHashMap - HTTP заголовки

Map<String, String> headers = new LinkedHashMap<>();
headers.put("Content-Type", "application/json");
headers.put("Authorization", "Bearer token");
// Порядок важен при отправке

TreeMap - телефонная книга

TreeMap<String, String> phoneBook = new TreeMap<>();
phoneBook.put("Alice", "+1234");
phoneBook.put("Bob", "+5678");
phoneBook.put("Charlie", "+9012");

// Все имена от B до C
phoneBook.subMap("B", "D").forEach((name, phone) -> 
    System.out.println(name + ": " + phone)
);

ConcurrentHashMap - счетчики посещений

ConcurrentHashMap<String, AtomicLong> pageViews = new ConcurrentHashMap<>();

// Из разных потоков
pageViews.computeIfAbsent("/home", k -> new AtomicLong())
         .incrementAndGet();

Map.Entry - вложенный интерфейс

interface Map.Entry<K, V> {
    K getKey();
    V getValue();
    V setValue(V value);
}

Использование Entry

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    
    // Можно модифицировать значение через entry
    if (value < 0) {
        entry.setValue(0);
    }
}

Создание Entry

// Immutable entry (Java 9+)
Map.Entry<String, Integer> entry = Map.entry("key", 123);

// Создание Map из entries
Map<String, Integer> map = Map.ofEntries(
    Map.entry("one", 1),
    Map.entry("two", 2),
    Map.entry("three", 3)
);

Неизменяемые Map (Immutable)

Java 9+ - Map.of()

// До 10 элементов
Map<String, Integer> map = Map.of(
    "one", 1,
    "two", 2,
    "three", 3
);

// Больше 10 элементов
Map<String, Integer> largeMap = Map.ofEntries(
    Map.entry("key1", 1),
    Map.entry("key2", 2),
    // ...
);

map.put("four", 4);  // ❌ UnsupportedOperationException

Collections.unmodifiableMap()

Map<String, Integer> mutableMap = new HashMap<>();
mutableMap.put("one", 1);

Map<String, Integer> unmodifiableMap = 
    Collections.unmodifiableMap(mutableMap);

unmodifiableMap.put("two", 2);  // ❌ UnsupportedOperationException

// Внимание: если изменить исходную map, unmodifiable тоже изменится
mutableMap.put("two", 2);  // Изменит и unmodifiableMap!

Специализированные Map реализации

WeakHashMap

Ключи хранятся как weak references
Если ключ больше нигде не используется, entry удаляется GC
Использование: кэши, где ключи - объекты

Map<Object, String> cache = new WeakHashMap<>();
Object key = new Object();
cache.put(key, "value");

key = null;  // Больше нет strong references
System.gc(); // После GC entry удалится из map

IdentityHashMap

Сравнение ключей через == вместо equals()
Использование: когда важна идентичность объектов, а не равенство

Map<String, Integer> map = new IdentityHashMap<>();
String s1 = new String("key");
String s2 = new String("key");

map.put(s1, 1);
map.put(s2, 2);

map.size();  // 2 (разные объекты, хотя equals вернет true)

EnumMap

Оптимизированная Map для enum ключей
Внутри - массив
Очень быстрая и компактная

enum Day { MONDAY, TUESDAY, WEDNESDAY }

Map<Day, String> schedule = new EnumMap<>(Day.class);
schedule.put(Day.MONDAY, "Meeting");
schedule.put(Day.TUESDAY, "Workshop");

Часто используемые методы Map

Получение значения с default

Integer value = map.getOrDefault("key", 0);
// Если ключа нет, вернет 0 вместо null

Массовые операции

Map<String, Integer> source = Map.of("a", 1, "b", 2);
Map<String, Integer> target = new HashMap<>();

target.putAll(source);  // Копирует все entry

Проверки

boolean isEmpty = map.isEmpty();
int size = map.size();
boolean hasKey = map.containsKey("key");
boolean hasValue = map.containsValue(100);

Очистка

map.clear();  // Удаляет все элементы

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

❌ Неправильный hashCode и equals

class Person {
    String name;
    int age;
    
    // ❌ Не переопределены equals и hashCode
}

Map<Person, String> map = new HashMap<>();
Person p1 = new Person("Alice", 30);
map.put(p1, "data");

Person p2 = new Person("Alice", 30);
map.get(p2);  // null ! Разные объекты

Правильно:

class Person {
    String name;
    int age;
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

❌ Использование mutable объектов как ключей

List<String> key = new ArrayList<>();
key.add("item");

map.put(key, "value");
key.add("another");  // ❌ Изменили ключ после вставки

map.get(key);  // Может не найти! hashCode изменился

Правильно: используй immutable объекты как ключи (String, Integer, и т.д.)

❌ Изменение Map во время итерации

for (String key : map.keySet()) {
    if (condition) {
        map.remove(key);  // ❌ ConcurrentModificationException
    }
}

Правильно:

Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
    Map.Entry<String, Integer> entry = it.next();
    if (condition) {
        it.remove();  // ✅ OK
    }
}

// Или (Java 8+)
map.entrySet().removeIf(entry -> condition);

✅ Указание initial capacity

// Плохо
Map<String, String> map = new HashMap<>();
for (int i = 0; i < 10000; i++) {
    map.put("key" + i, "value" + i);  // Много rehashing
}

// Хорошо
Map<String, String> map = new HashMap<>(10000);

✅ Правильное вычисление capacity

// Для N элементов с loadFactor=0.75
int capacity = (int) (N / 0.75 + 1);
Map<String, String> map = new HashMap<>(capacity);

Функциональные методы (Java 8+)

forEach

map.forEach((key, value) -> {
    System.out.println(key + " = " + value);
});

replaceAll

// Заменить все значения
map.replaceAll((key, value) -> value.toUpperCase());

computeIfAbsent - кэширование

Map<String, List<String>> groupedData = new HashMap<>();

// Старый способ
if (!groupedData.containsKey(category)) {
    groupedData.put(category, new ArrayList<>());
}
groupedData.get(category).add(item);

// Новый способ (Java 8+)
groupedData.computeIfAbsent(category, k -> new ArrayList<>())
           .add(item);

merge - счетчики

Map<String, Integer> wordCount = new HashMap<>();

words.forEach(word -> 
    wordCount.merge(word, 1, Integer::sum)
);

Итоговые рекомендации

По умолчанию:

Выбирай HashMap - самая быстрая и универсальная
Если нужна потокобезопасность → ConcurrentHashMap
Если нужен порядок → LinkedHashMap
Если нужна сортировка → TreeMap

Помни:

Всегда переопределяй hashCode() и equals() для кастомных ключей
Используй immutable объекты как ключи
Указывай initial capacity если знаешь размер
Для многопоточности используй Concurrent коллекции, а не синхронизацию
ConcurrentHashMap не поддерживает null
TreeMap не поддерживает null-ключи

Оптимизация:

// Правильный размер
Map<K, V> map = new HashMap<>((int)(expectedSize / 0.75 + 1));

// Для маленьких immutable map
Map<K, V> small = Map.of(k1, v1, k2, v2);

// Для больших immutable map
Map<K, V> large = Map.ofEntries(...);

Итоги

Map хранит пары ключ-значение, ключи уникальны
HashMap - по умолчанию, O(1) операции, порядок не гарантируется
LinkedHashMap - сохраняет порядок вставки или доступа (LRU кэш)
TreeMap - автоматическая сортировка по ключам, O(log n)
ConcurrentHashMap - потокобезопасная, не поддерживает null
Всегда переопределяй hashCode и equals для кастомных ключей
Используй immutable объекты как ключи (String, Integer и т.д.)
computeIfAbsent/merge - атомарные операции для обновления значений
Не модифицируй Map во время итерации - используй iterator.remove()
Указывай initial capacity для оптимизации производительности

Задания для практики

Подсчет слов: Дан текст. Создай Map<String, Integer> с частотой каждого слова. Используй merge().
LRU Cache: Реализуй LRU кэш на 5 элементов используя LinkedHashMap с accessOrder=true.
Группировка: Дан список Person(name, city). Создай Map<String, List> - группировка по городу.
ConcurrentHashMap: Реализуй потокобезопасный счетчик посещений страниц. Несколько потоков инкрементируют счетчики.
NavigableMap: Дан TreeMap с ценами товаров. Найди все товары в диапазоне цен [100, 500].

Keyboard shortcuts

Java Backend Handbook