Почему для кэшей используется Map?

Почему для кэшей используется Map: архитектурные причины

Выбор Map для реализации кэшей — это не случайно, а следствие их структуры данных и семантики. Давайте разберёмся, почему именно Map оптимален.

Основная причина: связь ключ-значение

Кэш по своей природе — это хранилище пар (ключ, значение):

// Запрос -> Ответ
cache.put("user:123", user);
User cached = cache.get("user:123");

// URL -> HTML
cache.put("https://example.com", htmlContent);
String html = cache.get("https://example.com");

// Параметры функции -> Результат
cache.put("fibonacci(10)", 55);
int result = cache.get("fibonacci(10)");

Map предоставляет эту семантику встроенно: каждому уникальному ключу соответствует один результат.

Почему не List или Set?

Проблема с List

// Плохо: поиск в List медленный
List<CacheEntry> cache = new ArrayList<>();

for (CacheEntry entry : cache) {  // O(n) поиск
    if (entry.key.equals(key)) {
        return entry.value;
    }
}

// Представьте кэш с 10000 записями
// Каждый поиск проверяет все 10000 элементов
// Если 100 запросов в секунду -> 100 * 10000 = 1 млн операций

Проблема с Set

// Set хранит уникальные элементы, но нет связи ключ-значение
Set<CacheEntry> cache = new HashSet<>();

// Как получить значение по ключу?
// Нужно переопределить equals и hashCode на ключ
// Но тогда несколько входов с одинаковым ключом не могут храниться
// А если значение изменилось, нужно удалить и вставить снова

Причина 1: Быстрая операция поиска

HashMap даёт O(1) в среднем:

// HashMap (кэш)
Map<String, User> cache = new HashMap<>();
cache.put("user:123", user);
User result = cache.get("user:123"); // O(1) — мгновенно!

// vs List
List<User> list = new ArrayList<>();
User result = null;
for (User u : list) {              // O(n) — полный поиск
    if (u.getId().equals("user:123")) {
        result = u;
        break;
    }
}

Реальный пример:

// Кэш с 1 млн записей
long start = System.nanoTime();
User u = cache.get("user:999999");  // HashMap: ~3 мкс
long mapTime = System.nanoTime() - start;

start = System.nanoTime();
User u2 = null;
for (User user : list) {            // List: ~500 мкс (в 100+ раз медленнее)
    if (user.getId().equals("user:999999")) {
        u2 = user;
        break;
    }
}
long listTime = System.nanoTime() - start;

Причина 2: Встроенная семантика кэширования

Map естественно выражает кэширование:

// Типичная операция кэширования
User user = cache.get("user:123");
if (user == null) {
    user = database.getUser(123);  // Медленно
    cache.put("user:123", user);   // Сохраняем
}
return user;

// vs Set или List
Set<CacheEntry> cache = new HashSet<>();
CacheEntry found = null;
for (CacheEntry entry : cache) {
    if (entry.getKey().equals("user:123")) {
        found = entry;
        break;  // Нужна цепочка действий
    }
}
if (found == null) {
    User user = database.getUser(123);
    cache.add(new CacheEntry("user:123", user));  // Более многословно
} else {
    return found.getValue();
}

Причина 3: Встроенная обработка пересечений (collision handling)

У HashMap есть встроенный механизм для обработки коллизий хеша:

// HashMap автоматически разрешает коллизии
Map<String, String> cache = new HashMap<>();
cache.put("user1", "data1");
cache.put("user2", "data2");

// Если хеши совпадают, HashMap использует linked list или красно-чёрное дерево
// Это полностью прозрачно для пользователя

// vs реализация своего хеша
class SimpleCache {
    private Object[] buckets = new Object[16];
    
    public void put(String key, Object value) {
        int hash = key.hashCode() % buckets.length;
        if (buckets[hash] != null) {
            // Что делать с коллизией?
            // Нужна своя реализация обработки
        }
        buckets[hash] = value;
    }
}

Практические примеры кэширования с Map

Пример 1: Простой кэш запросов

public class RequestCache {
    private final Map<String, Response> cache = new HashMap<>();
    
    public Response getResponse(String url) {
        return cache.computeIfAbsent(url, key -> {
            // Если нет в кэше, вычислить
            return fetchFromServer(key);
        });
    }
}

// Почему Map? Потому что:
// 1. Привязка URL -> Response
// 2. O(1) поиск по URL
// 3. computeIfAbsent — встроенный паттерн кэширования

Пример 2: LRU кэш (LinkedHashMap)

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

// LinkedHashMap — подкласс Map с порядком элементов
// Идеален для LRU, потому что основан на Map

Пример 3: Асинхронный кэш

public class AsyncCache {
    private final Map<String, CompletableFuture<Data>> cache = new ConcurrentHashMap<>();
    
    public CompletableFuture<Data> get(String key) {
        return cache.computeIfAbsent(key, k -> 
            CompletableFuture.supplyAsync(() -> fetchData(k))
        );
    }
}

// Map позволяет:
// 1. Хранить futures (асинхронные результаты)
// 2. ConcurrentHashMap обеспечивает потокобезопасность
// 3. computeIfAbsent запускает загрузку один раз для одного ключа

Пример 4: Кэш с временем жизни (TTL)

public class TTLCache<K, V> {
    private final Map<K, CacheEntry<V>> cache = new HashMap<>();
    private final long ttl;
    
    private static class CacheEntry<V> {
        V value;
        long expirationTime;
        
        CacheEntry(V value, long ttl) {
            this.value = value;
            this.expirationTime = System.currentTimeMillis() + ttl;
        }
        
        boolean isExpired() {
            return System.currentTimeMillis() > expirationTime;
        }
    }
    
    public V get(K key) {
        CacheEntry<V> entry = cache.get(key);
        if (entry != null && !entry.isExpired()) {
            return entry.value;
        }
        cache.remove(key);
        return null;
    }
}

// Map удобен для привязки ключа -> запись с metadata

Сравнение структур для кэша

Альтернативы: когда не использовать Map

// Если нужен простой счётчик (не кэш)
int hitCount = 0;

// Если нужно хранить упорядоченные данные
NavigableMap<LocalDateTime, Event> timeline = new TreeMap<>();

// Если нужна потокобезопасность
ConcurrentMap<K, V> cache = new ConcurrentHashMap<>();

// Если нужен распределённый кэш
Cache<K, V> cache = CacheBuilder.newBuilder()
    .expireAfterWrite(10, TimeUnit.MINUTES)
    .build();

Заключение

Map используется для кэшей потому что:

1. Естественная семантика: кэш = набор пар (ключ, значение)
2. O(1) поиск: HashMap даёт мгновенный доступ к кэшированным данным
3. Встроенные паттерны: computeIfAbsent, putIfAbsent идеальны для кэширования
4. Гибкость: LinkedHashMap, TreeMap, ConcurrentHashMap — семейство решений
5. Правильная абстракция: выражает намерение (это кэш, это K->V映射)
6. Производительность: хеш-таблица оптимальна для random access

Другие структуры (List, Set) либо медленнее (List), либо менее выразительны (Set) для этого конкретного случая.