Реализация LRU Cache

Реализация LRU Cache

Объяснение задачи

LRU Cache (Least Recently Used) — это кэш, который автоматически удаляет наименее недавно используемый элемент при достижении максимальной ёмкости.

Основные операции:

• get(key) — O(1) получить значение
• put(key, value) — O(1) добавить/обновить
• При переполнении удаляется самый старый неиспользованный элемент

Решение 1: LinkedHashMap (элегантное и простое)

LinkedHashMap поддерживает режим access-order:

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache {
    private LinkedHashMap<Integer, Integer> cache;
    private int capacity;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        // access-order LinkedHashMap: true включает режим доступа
        this.cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > capacity;  // Удалить когда превышена ёмкость
            }
        };
    }
    
    /**
     * Получить значение по ключу
     * get() сам переместит элемент в конец (самый свежий)
     */
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        return cache.get(key);  // get() обновляет order в access-order режиме
    }
    
    /**
     * Добавить или обновить значение
     */
    public void put(int key, int value) {
        cache.put(key, value);
    }
}

Как работает LinkedHashMap в access-order режиме:

1. При создании с true в третьем параметре включается access-order
2. При каждом get() элемент перемещается в конец
3. removeEldestEntry() переопределяем для удаления старого элемента
4. Первый элемент (eldest) автоматически удаляется при переполнении

Пример работы:

LRUCache cache = new LRUCache(2);
cache.put(1, 1);     // {1}
cache.put(2, 2);     // {1, 2}
cache.get(1);        // {2, 1} - 1 переместился в конец (самый свежий)
cache.put(3, 3);     // {1, 3} - 2 удалился как старый
cache.get(2);        // -1 (не найден)

Решение 2: HashMap + Doubly Linked List (полный контроль)

Для полного понимания механизма:

public class LRUCache {
    
    // Node для двусвязного списка
    class Node {
        int key;
        int value;
        Node prev;
        Node next;
        
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private HashMap<Integer, Node> cache;
    private Node head;  // Самый недавно использованный
    private Node tail;  // Самый давно используемый
    private int capacity;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node(-1, -1);  // Dummy head
        this.tail = new Node(-1, -1);  // Dummy tail
        head.next = tail;
        tail.prev = head;
    }
    
    /**
     * Получить значение и переместить элемент в начало
     */
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        
        Node node = cache.get(key);
        moveToHead(node);  // Переместить в начало (самый свежий)
        return node.value;
    }
    
    /**
     * Добавить или обновить значение
     */
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            // Обновляем существующий узел
            Node node = cache.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            // Добавляем новый узел
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            
            // Если превышена ёмкость, удаляем старый
            if (cache.size() > capacity) {
                removeOldest();
            }
        }
    }
    
    /**
     * Переместить узел в начало (самый свежий)
     */
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
    
    /**
     * Добавить узел в начало
     */
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    
    /**
     * Удалить узел из списка
     */
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    /**
     * Удалить самый старый узел (перед tail)
     */
    private void removeOldest() {
        Node oldest = tail.prev;
        removeNode(oldest);
        cache.remove(oldest.key);
    }
}

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

Структура памяти:
head ↔ [Node 1] ↔ [Node 2] ↔ [Node 3] ↔ tail
(последний слева = самый старый, последний справа = самый свежий)

put(1, 1):
head ↔ [1] ↔ tail

put(2, 2):
head ↔ [2] ↔ [1] ↔ tail

get(1):
head ↔ [1] ↔ [2] ↔ tail  (1 переместился в начало)

put(3, 3) при capacity=2:
head ↔ [3] ↔ [1] ↔ tail
2 удалён как самый старый

Решение 3: С использованием List (простое)

Более простой вариант без explicit двусвязного списка:

import java.util.HashMap;
import java.util.LinkedList;

public class LRUCache {
    private HashMap<Integer, Integer> cache;
    private LinkedList<Integer> order;  // Порядок использования
    private int capacity;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.order = new LinkedList<>();
    }
    
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        
        // Переместить в конец (самый свежий)
        order.remove((Integer) key);
        order.addLast(key);
        
        return cache.get(key);
    }
    
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            order.remove((Integer) key);
        } else if (cache.size() >= capacity) {
            // Удалить самый старый
            int oldest = order.removeFirst();
            cache.remove(oldest);
        }
        
        cache.put(key, value);
        order.addLast(key);
    }
}

Минус: remove() на LinkedList — O(n), поэтому put() и get() не совсем O(1).

Полные тесты

public class LRUCacheTest {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        
        cache.put(1, 1);
        System.out.println("put(1, 1)");
        
        cache.put(2, 2);
        System.out.println("put(2, 2)");
        
        System.out.println("get(1) = " + cache.get(1));      // 1
        
        cache.put(3, 3);
        System.out.println("put(3, 3) - удаляет 2");
        
        System.out.println("get(2) = " + cache.get(2));      // -1
        
        cache.put(4, 4);
        System.out.println("put(4, 4) - удаляет 1");
        
        System.out.println("get(1) = " + cache.get(1));      // -1
        System.out.println("get(3) = " + cache.get(3));      // 3
        System.out.println("get(4) = " + cache.get(4));      // 4
    }
}

Сравнение подходов

Вывод для интервью

На интервью рекомендуется:

1. Сначала: LinkedHashMap решение — показывает знание API Java
2. Затем: если интервьюер просит, реализуйте HashMap + Doubly Linked List для полного понимания
3. Объясните: почему нужна именно двусвязный список (O(1) удаление)
4. Упомянуть: trade-off между простотой и контролем

Ключевые моменты:

• LRU Cache требует O(1) для всех операций
• LinkedHashMap встроена и эффективна
• Doubly Linked List даёт полный контроль
• Тестируйте edge cases (capacity=1, повторные puts)