Что такое Map в Java?

Map в Java: полное руководство для собеседования

Map — одна из самых важных структур данных в Java Collections Framework. Её понимание критично для любого разработчика, от junior до senior. Давайте разберёмся не только "что это", но и "как это работает" и "когда это использовать".

Определение и суть

Map — это структура данных, которая хранит пары ключ-значение (key-value pairs). Это не Collection в классическом смысле (Collection — это последовательность объектов), а скорее mapping, где каждый ключ уникален и соответствует ровно одному значению.

public interface Map<K, V> {
    V put(K key, V value);              // добавить/обновить
    V get(Object key);                  // получить по ключу
    V remove(Object key);               // удалить
    boolean containsKey(Object key);    // проверка наличия ключа
    Set<K> keySet();                    // все ключи
    Collection<V> values();             // все значения
    Set<Entry<K,V>> entrySet();         // все пары
}

От обычного интерфейса Collection, Map отличается:

• Нет ordering гарантий (у неупорядоченных реализаций)
• Ключи уникальны (использует hashCode/equals или compareTo)
• Оптимизирован для поиска (O(1) средний случай у HashMap)

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

HashMap — самая частая

Map<String, Integer> ageMap = new HashMap<>();
ageMap.put("Alice", 25);
ageMap.put("Bob", 30);
ageMap.put("Alice", 26);  // Обновляет значение

Integer aliceAge = ageMap.get("Alice");  // 26
boolean hasAlice = ageMap.containsKey("Alice");  // true

ageMap.remove("Bob");
int size = ageMap.size();  // 1

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

• O(1) среднее время для get/put/remove
• Не thread-safe (нужен ConcurrentHashMap для многопоточности)
• Позволяет null ключ (один!) и null значения
• Порядок не гарантирован

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

Map<String, Integer> linkedMap = new LinkedHashMap<>();
linkedMap.put("A", 1);
linkedMap.put("B", 2);
linkedMap.put("C", 3);

// Итерация в порядке вставки
for (String key : linkedMap.keySet()) {
    System.out.println(key);  // A, B, C
}

TreeMap — отсортированный Map

Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Z", 1);
treeMap.put("A", 2);
treeMap.put("M", 3);

// Итерация в отсортированном порядке (по ключам)
for (String key : treeMap.keySet()) {
    System.out.println(key);  // A, M, Z
}

// Доступны методы: firstKey(), lastKey(), subMap(), headMap(), tailMap()
String first = treeMap.firstKey();  // "A"
String last = treeMap.lastKey();    // "Z"

ConcurrentHashMap — для многопоточности

Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();

// Thread-safe без блокировки всей таблицы
// Использует segment locking (или bucket locking в Java 8+)
Integer value = concurrentMap.putIfAbsent("key", 100);

WeakHashMap — для кэширования

Map<String, byte[]> cache = new WeakHashMap<>();
// Если ключ больше не используется, он может быть garbage collected
// Полезно для кэшей, чтобы не было memory leaks

Как работает HashMap

Это одна из самых популярных вопросов на собеседованиях, поэтому углубимся:

Внутренняя структура: HashMap использует массив buckets (корзин), каждая из которых содержит linked list или red-black tree (в Java 8+).

Bucket[0] -> [Node(hash, key, value) -> Node(...) -> null]
Bucket[1] -> null
Bucket[2] -> [Node(...) -> null]
...

Процесс put(key, value):

1. Вычисляется hash = key.hashCode()
2. Вычисляется index = hash % buckets.length
3. На bucket[index] добавляется новый Node (или обновляется существующий)
4. Если коллизия (несколько объектов в одной корзине), используется equals() для сравнения

map.put("Alice", 25);

// Шаг 1: hash = "Alice".hashCode() = примерно 2009652290
// Шаг 2: index = 2009652290 % 16 = 14 (для default capacity 16)
// Шаг 3: bucket[14] получает новый Node

Коллизии (hash collisions): Если два разных объекта имеют одинаковый hash, они попадают в одну корзину. Тогда использует equals():

Map<Integer, String> map = new HashMap<>();
map.put(5, "Five");      // hash = 5, index = некий
map.put(21, "TwentyOne"); // hash = 21

// Если 5 и 21 имеют одинаковый index (маловероятно, но возможно),
// используется equals() для различия

Load Factor и Resizing: Когда размер Map растёт, HashMap расширяет capacity и rehash'ит все элементы:

// Load factor = 0.75 (по умолчанию)
// Когда размер превышает capacity * 0.75, HashMap удваивает capacity
// Это стоит дорого, поэтому если знаешь размер — инициализируй:

Map<String, Integer> map = new HashMap<>(1000);
// Вместо создания с default capacity 16

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

Пример 1: Подсчёт частоты слов

public Map<String, Integer> countWords(String[] words) {
    Map<String, Integer> frequency = new HashMap<>();
    
    for (String word : words) {
        // BAD: frequency.put(word, frequency.get(word) + 1);
        // Может быть NPE если ключа нет
        
        // GOOD: используй getOrDefault
        frequency.put(word, frequency.getOrDefault(word, 0) + 1);
    }
    
    return frequency;
}

String[] words = {"Java", "Java", "Python", "Java"};
Map<String, Integer> freq = countWords(words);
// {Java=3, Python=1}

Пример 2: Кэширование результатов (Memoization)

public class FibonacciCache {
    private Map<Integer, Long> cache = new HashMap<>();
    
    public long fibonacci(int n) {
        if (n <= 1) return n;
        
        // Проверяем кэш
        if (cache.containsKey(n)) {
            return cache.get(n);
        }
        
        long result = fibonacci(n - 1) + fibonacci(n - 2);
        cache.put(n, result);
        return result;
    }
}

// Без кэша: exponential время O(2^n)
// С кэшем: линейное время O(n)
FibonacciCache fib = new FibonacciCache();
long result = fib.fibonacci(100);  // мгновенно

Пример 3: Группировка по категориям

public Map<String, List<String>> groupByCategory(
        List<Product> products) {
    
    // Вариант 1: классический
    Map<String, List<String>> grouped = new HashMap<>();
    for (Product p : products) {
        grouped.computeIfAbsent(p.getCategory(), k -> new ArrayList<>())
            .add(p.getName());
    }
    
    // Вариант 2: Java Streams (более современный)
    return products.stream()
        .collect(Collectors.groupingBy(
            Product::getCategory,
            Collectors.mapping(Product::getName, Collectors.toList())
        ));
}

Пример 4: Работа с Entry (оптимальный перебор)

Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 95);
scores.put("Bob", 87);
scores.put("Charlie", 92);

// BAD: перебирает дважды (ключи, потом значения)
for (String name : scores.keySet()) {
    System.out.println(name + ": " + scores.get(name));
}

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

// BEST: лямбда выражение
scores.forEach((name, score) -> 
    System.out.println(name + ": " + score)
);

Сравнение реализаций

Частые ошибки

Ошибка 1: Использование mutable объекта как ключа

// BAD: ArrayList изменяется, поэтому hash изменяется
Map<ArrayList<String>, Integer> bad = new HashMap<>();
ArrayList<String> key = new ArrayList<>();
key.add("a");
bad.put(key, 1);
key.add("b");  // Теперь hash изменился, get() не найдёт!
bad.get(key);  // null

// GOOD: используй immutable ключи
Map<String, Integer> good = new HashMap<>();  // String immutable
Map<Integer, Integer> also_good = new HashMap<>();  // Integer immutable

Ошибка 2: Забывчиво обработать отсутствие ключа

// BAD: NPE если ключа нет
Integer value = map.get("key");  // может быть null
int result = value + 10;  // NullPointerException

// GOOD: несколько подходов
Integer value = map.getOrDefault("key", 0);  // 0 если нет
Integer value = map.get("key");  // null
if (value != null) { ... }

Ошибка 3: Неправильное сравнение equals/hashCode

public class Person {
    private String name;
    
    @Override
    public int hashCode() {
        return name.hashCode();  // OK
    }
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Person)) return false;
        return ((Person)obj).name.equals(this.name);  // OK
    }
}

// Теперь это работает как ключ:
Map<Person, Integer> map = new HashMap<>();
Person p1 = new Person("Alice");
Person p2 = new Person("Alice");  // другой объект, но равный
map.put(p1, 25);
map.get(p2);  // 25, работает!

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

HashMap:

• По умолчанию, если нужна скорость
• Когда порядок не важен
• Однопоточное приложение

LinkedHashMap:

• Нужно сохранить порядок вставки
• LRU кэш (с переопределением removeEldestEntry)

TreeMap:

• Нужна отсортированность
• Нужны range queries (subMap, headMap, tailMap)
• Нужна O(log n) гарантия (худший случай)

ConcurrentHashMap:

• Многопоточное приложение
• Performance критичнее, чем Hashtable
• Java 5+

WeakHashMap:

• Кэширование с автоматической очисткой
• Когда ключи могут быть garbage collected

Заключение

Map — это больше, чем просто "ассоциативный массив". Это структура данных с:

• Глубокими различиями между реализациями
• Сложными внутренними механизмами (hashing, resizing, collision handling)
• Критичными деталями (equals/hashCode контракт)

Понимание Map на этом уровне — признак опытного Java разработчика, который не просто использует, но понимает, как и почему это работает.