Какими реализациями Map пользовался

Какими реализациями Map пользовался

Введение

В Java существует несколько реализаций интерфейса Map, каждая с различными характеристиками и use cases. Опытный разработчик должен знать, когда использовать каждую из них для оптимальной производительности и функциональности.

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

1. HashMap

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

• Самая часто используемая реализация
• Основана на хеш-таблице
• O(1) среднее время для get, put, remove
• Не сохраняет порядок элементов
• Не потокобезопасна

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

// Кэширование данных
private Map<String, UserCache> userCache = new HashMap<>();

public void cacheUser(String userId, UserCache cache) {
    userCache.put(userId, cache);
}

public UserCache getUser(String userId) {
    return userCache.get(userId); // O(1)
}

// Маппинг ID на объекты
Map<Long, User> usersById = new HashMap<>();
for (User user : users) {
    usersById.put(user.getId(), user);
}

Performance:

• Get: O(1) average, O(n) worst case (при множестве коллизий)
• Put: O(1) average
• Remove: O(1) average
• Memory: умеренное использование памяти

// Load Factor = 0.75 (по умолчанию)
// При размере > 0.75 * capacity -> resize в 2 раза
HashMap<String, Integer> map = new HashMap<>(1000); // initial capacity

2. LinkedHashMap

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

• Сохраняет порядок вставки элементов
• Двусвязный список + хеш-таблица
• O(1) время для get, put, remove (как HashMap)
• Не потокобезопасна
• Немного медленнее HashMap из-за двусвязного списка

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

// Нужно сохранить порядок вставки
Map<String, String> configuration = new LinkedHashMap<>();
configuration.put("database", "postgresql");
configuration.put("port", "5432");
configuration.put("host", "localhost");

// Итерация будет в порядке вставки
for (Map.Entry<String, String> entry : configuration.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}
// Output:
// database = postgresql
// port = 5432
// host = localhost

// LRU Cache реализация
private static class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);  // true = access-order (последний использованный в конце)
        this.capacity = capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;  // удалить старейший при переполнении
    }
}

LRUCache<String, String> cache = new LRUCache<>(100);
cache.put("key1", "value1");
String value = cache.get("key1");  // "key1" переместился в конец (most recently used)

Performance:

• Get: O(1)
• Put: O(1)
• Memory: больше, чем HashMap, из-за двусвязного списка

3. TreeMap

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

• Реализован как Red-Black дерево
• Сортированный Map (по ключам)
• O(log n) время для get, put, remove
• Не потокобезопасна
• Медленнее HashMap, но гарантирует порядок

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

// Нужен сортированный порядок
Map<Integer, User> rankedUsers = new TreeMap<>();
rankedUsers.put(3, new User("Alice"));
rankedUsers.put(1, new User("Bob"));
rankedUsers.put(2, new User("Charlie"));

// Итерация будет в порядке ключей (1, 2, 3)
for (Integer rank : rankedUsers.keySet()) {
    System.out.println(rank); // 1, 2, 3
}

// Диапазонные запросы
SortedMap<String, User> subMap = 
    usersByName.subMap("Alice", "Charlie");
// Получить всех пользователей от Alice до Charlie (не включая Charlie)

// Первый и последний элементы
Map.Entry<Integer, User> first = rankedUsers.firstEntry();
Map.Entry<Integer, User> last = rankedUsers.lastEntry();
Map.Entry<Integer, User> floor = rankedUsers.floorEntry(2);  // <= 2
Map.Entry<Integer, User> ceiling = rankedUsers.ceilingEntry(2);  // >= 2

Custom Comparator:

// Сортировка в обратном порядке
Map<Integer, String> reverseMap = new TreeMap<>(
    Comparator.reverseOrder()
);
reverseMap.put(3, "Three");
reverseMap.put(1, "One");
reverseMap.put(2, "Two");
// Итерация: 3, 2, 1

// Кастомная сортировка
Map<User, Integer> scoreMap = new TreeMap<>(
    Comparator.comparing(User::getName)
);

Performance:

• Get: O(log n)
• Put: O(log n)
• Remove: O(log n)
• Memory: оптимально для сортированных данных

4. Hashtable (устаревший)

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

• Как HashMap, но потокобезопасна (synchronized)
• Синхронизирована ВСЕ методы
• УСТАРЕВШИЙ класс (используй ConcurrentHashMap)

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

// ❌ НЕ ИСПОЛЬЗУЙ Hashtable!
Hashtable<String, String> map = new Hashtable<>();  // старое, медленно

// ✅ Используй ConcurrentHashMap
Map<String, String> map = new ConcurrentHashMap<>();

5. ConcurrentHashMap

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

• Потокобезопасна (в отличие от HashMap)
• Использует bucket-level locking (не блокирует всю таблицу)
• O(1) время для get, put, remove
• Не гарантирует порядок элементов
• Лучший выбор для многопоточных приложений

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

// Многопоточный кэш
private ConcurrentHashMap<String, User> userCache = 
    new ConcurrentHashMap<>();

public void cacheUser(String userId, User user) {
    userCache.put(userId, user);
}

public User getUser(String userId) {
    return userCache.get(userId);
}

// putIfAbsent для безопасного кэширования
public User getUserOrCompute(String userId) {
    return userCache.putIfAbsent(userId, 
        loadUserFromDatabase(userId));
}

// computeIfAbsent (более удобный способ)
public User getUserOrCompute(String userId) {
    return userCache.computeIfAbsent(userId, 
        id -> loadUserFromDatabase(id));
}

// merge для обновления
userCache.merge(userId, newUser, 
    (existing, updated) -> {
        existing.updateLastAccess();
        return existing;
    }
);

Performance:

• Get: O(1)
• Put: O(1)
• Memory: как HashMap
• Параллелизм: отличный для многопоточности

// Segment-based locking (Java 7)
// Bucket-based locking (Java 8+)
// Не блокирует всю таблицу при put

6. WeakHashMap

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

• Ключи хранятся как weak references
• Если ключ больше нигде не используется -> удаляется
• Используется для кэшей, которые не должны предотвращать garbage collection

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

// Кэш, который не должен предотвращать GC
Map<Image, String> imageMetadata = new WeakHashMap<>();

Image image = loadImage("photo.jpg");
imageMetadata.put(image, "sunset photo");

// Когда image выходит из scope и GC его удаляет,
// запись в WeakHashMap тоже удалится автоматически
image = null;
System.gc();
// imageMetadata.size() теперь 0

Performance:

• Get: O(1)
• Занимает менньше памяти в долгосрочной перспективе

7. IdentityHashMap

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

• Использует == (identity) вместо .equals() для сравнения ключей
• Очень быстро для специфичных use cases
• Редко используется

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

// Когда нужно различать разные объекты, даже если они equal
Object key1 = new String("test");
Object key2 = new String("test");

Map<Object, String> hashMap = new HashMap<>();
hashMap.put(key1, "value1");
hashMap.put(key2, "value2");  // перезапишет, т.к. key1.equals(key2)
// hashMap.size() == 1

Map<Object, String> identityMap = new IdentityHashMap<>();
identityMap.put(key1, "value1");
identityMap.put(key2, "value2");  // добавит отдельно, т.к. key1 != key2
// identityMap.size() == 2

8. EnumMap

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

• Специализирован для enum ключей
• Очень быстро и эффективно по памяти
• Использует array под капотом

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

public enum Color {
    RED, GREEN, BLUE
}

// Вместо HashMap с enum
Map<Color, String> colorNames = new EnumMap<>(Color.class);
colorNames.put(Color.RED, "красный");
colorNames.put(Color.GREEN, "зелёный");
colorNames.put(Color.BLUE, "синий");

// Очень быстро и экономно по памяти
String name = colorNames.get(Color.RED);  // O(1) array lookup

Performance:

• Get: O(1) (очень быстро)
• Memory: минимальное использование

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

Практические примеры из реальных проектов

// Spring Boot Application
@Service
public class UserService {
    // Кэш с порядком вставки
    private final Map<Long, User> recentUsers = 
        new LinkedHashMap<Long, User>(100, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > 100;  // max 100 recent users
            }
        };
    
    // Многопоточный кэш
    private final ConcurrentHashMap<String, TokenData> tokens =
        new ConcurrentHashMap<>();
    
    // Сортированный список пользователей по имени
    private final TreeMap<String, User> usersByName = 
        new TreeMap<>();
    
    // Для enum статусов
    private final EnumMap<UserStatus, Long> statusCounts =
        new EnumMap<>(UserStatus.class);
}

// Java Streams
List<User> users = ...;

// Кроме того, часто используются в toMap() collectors
Map<Long, User> usersById = users.stream()
    .collect(Collectors.toMap(User::getId, Function.identity()));

// С LinkedHashMap для порядка
Map<Long, User> usersInOrder = users.stream()
    .collect(Collectors.toMap(
        User::getId, 
        Function.identity(),
        (u1, u2) -> u1,  // merger
        LinkedHashMap::new  // map supplier
    ));

// С TreeMap для сортировки
Map<String, Long> frequencyMap = words.stream()
    .collect(Collectors.groupingBy(
        Function.identity(),
        TreeMap::new,  // sorted by key
        Collectors.counting()
    ));

Вывод

Выбор правильной реализации Map критичен для производительности:

1. HashMap — 90% случаев, быстро и просто
2. LinkedHashMap — когда нужен порядок вставки
3. TreeMap — когда нужна сортировка или диапазонные запросы
4. ConcurrentHashMap — для многопоточных приложений
5. EnumMap — для enum ключей
6. WeakHashMap — для специфичных кэшей
7. Hashtable — НЕ ИСПОЛЬЗУЙ (deprecated)

Опытный разработчик должен выбирать подходящую реализацию в зависимости от требований.