Для чего нужна структура данных словарь?

# Структура данных Словарь (Map) в Java

Словарь (Map) — это структура данных, которая хранит пары ключ-значение (key-value pairs) и обеспечивает быстрый поиск значения по ключу. В Java словари реализуются через интерфейс java.util.Map.

Основное назначение

Словарь нужен для:

1. Быстрого поиска — O(1) в среднем случае
2. Связывания ключей со значениями — логическое объединение данных
3. Кэширования — сохранение часто используемых значений
4. Подсчета частоты — количество вхождений элементов
5. Преобразования данных — отображение из одного формата в другой

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

// Создание словаря
Map<String, Integer> ages = new HashMap<>();

// Добавление (key-value)
ages.put("Алиса", 25);
ages.put("Боб", 30);
ages.put("Виктор", 28);

// Получение значения по ключу
Integer aliceAge = ages.get("Алиса");  // 25

// Проверка наличия ключа
if (ages.containsKey("Боб")) {
    System.out.println("Боб есть в словаре");
}

// Удаление
ages.remove("Виктор");

// Размер
int size = ages.size();  // 2

// Проверка, пуст ли
boolean isEmpty = ages.isEmpty();  // false

// Очистка
ages.clear();

Иерархия типов Map в Java

java.util.Map
├── HashMap         - быстрый, неупорядоченный
├── LinkedHashMap   - упорядоченный (insertion order)
├── TreeMap         - отсортированный по ключам
├── ConcurrentHashMap - потокобезопасный
├── Hashtable       - синхронизированный (старый)
└── WeakHashMap     - для слабых ссылок

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

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

public class WordCounter {
    public static Map<String, Integer> countWords(String text) {
        Map<String, Integer> wordCount = new HashMap<>();
        String[] words = text.toLowerCase().split(" ");
        
        for (String word : words) {
            wordCount.put(
                word,
                wordCount.getOrDefault(word, 0) + 1
            );
        }
        
        return wordCount;
    }
}

// Использование
String text = "java java программирование java";
Map<String, Integer> result = WordCounter.countWords(text);
System.out.println(result);  // {java=3, программирование=1}

Пример 2: Кэш пользователей

public class UserCache {
    private Map<Long, User> cache = new HashMap<>();
    
    public User getUser(long id) {
        if (cache.containsKey(id)) {
            return cache.get(id);  // Из кэша O(1)
        }
        
        // Если нет, получить из БД
        User user = database.findUser(id);
        cache.put(id, user);  // Сохранить в кэш
        return user;
    }
    
    public void clearCache() {
        cache.clear();
    }
}

Пример 3: Преобразование данных

public class DataTransformer {
    public static void main(String[] args) {
        // Преобразование кода страны в название
        Map<String, String> countries = new HashMap<>();
        countries.put("RU", "Россия");
        countries.put("US", "США");
        countries.put("FR", "Франция");
        
        String code = "US";
        String name = countries.getOrDefault(code, "Неизвестно");
        System.out.println(name);  // США
    }
}

Пример 4: Конфигурационные параметры

public class Configuration {
    private Map<String, String> config = new HashMap<>();
    
    public Configuration() {
        config.put("database.url", "jdbc:mysql://localhost:3306/mydb");
        config.put("database.user", "root");
        config.put("server.port", "8080");
        config.put("app.name", "MyApplication");
    }
    
    public String getConfig(String key) {
        return config.getOrDefault(key, "");
    }
}

Реализации Map

HashMap — самая быстрая

Map<String, String> map = new HashMap<>();
map.put("key", "value");  // O(1) в среднем
map.get("key");           // O(1) в среднем

// Неупорядоченный
for (String key : map.keySet()) {
    System.out.println(key);  // Порядок не гарантирован
}

LinkedHashMap — упорядоченный

Map<String, Integer> map = new LinkedHashMap<>();
map.put("первый", 1);
map.put("второй", 2);
map.put("третий", 3);

// Сохраняет порядок вставки
for (String key : map.keySet()) {
    System.out.println(key);  // первый, второй, третий
}

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

Map<String, Integer> map = new TreeMap<>();
map.put("яблоко", 1);
map.put("апельсин", 2);
map.put("банан", 3);

// Отсортирован по ключам
for (String key : map.keySet()) {
    System.out.println(key);  // апельсин, банан, яблоко
}

ConcurrentHashMap — потокобезопасный

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

// Безопасен в многопоточной среде без synchronized
ExecutorService executor = Executors.newFixedThreadPool(4);
for (int i = 0; i < 1000; i++) {
    int num = i;
    executor.submit(() -> map.put("key" + num, num));
}

Итерирование по Map

1. Через KeySet

Map<String, String> map = new HashMap<>();
map.put("1", "один");
map.put("2", "два");

for (String key : map.keySet()) {
    String value = map.get(key);
    System.out.println(key + " = " + value);
}

2. Через Values

for (String value : map.values()) {
    System.out.println(value);  // один, два
}

3. Через EntrySet (самый эффективный)

for (Map.Entry<String, String> entry : map.entrySet()) {
    String key = entry.getKey();
    String value = entry.getValue();
    System.out.println(key + " = " + value);
}

4. Через Iterator

Iterator<Map.Entry<String, String>> iter = map.entrySet().iterator();
while (iter.hasNext()) {
    Map.Entry<String, String> entry = iter.next();
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

Полезные методы Map

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.put("b", 2);

// getOrDefault — безопасное получение
int value = map.getOrDefault("c", 0);  // 0 если нет ключа

// putIfAbsent — добавить если нет
map.putIfAbsent("c", 3);

// compute — вычислить новое значение
map.compute("a", (k, v) -> v == null ? 10 : v + 10);

// merge — слияние значений
map.merge("a", 5, (oldVal, newVal) -> oldVal + newVal);

// replace — заменить значение
map.replace("a", 1, 100);

// replaceAll — заменить все
map.replaceAll((k, v) -> v * 2);

Сложность операций

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

HashMap:

• Нужна максимальная производительность
• Порядок не важен
• Нет требований к многопоточности

LinkedHashMap:

• Нужно сохранить порядок вставки
• Реализация LRU кэша

TreeMap:

• Нужна отсортированная структура
• Нужны операции по диапазону (subMap)

ConcurrentHashMap:

• Многопоточное приложение
• Высокая конкурентность

Словарь — одна из самых важных и часто используемых структур данных в программировании.