LRU-кэш

Источник: https://leetcode.com/problems/lru-cache/

Создайте структуру данных для  Least Recently Used (LRU) cache. Эта структура поддерживает две операции: get и put.

get(key) - извлекает значение (всегда положительное) по ключу key, если ключ присутствует в кэше, а в противном случае возвращает -1.
put(key, value) - помещает или изменяет значение по ключу.  Когда кэш достигает своей вместимости, наименее используемые элемент можно удалить и поместить новый элемент.

Кэш инициализируется положительной вместимостью.

Сделайте так, чтобы обе операции выполнялись за время со сложностью O(1), то есть за константу.

Пример 1:

Входные данные
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Результат
[null, null, null, 1, null, -1, null, -1, 3, 4]

Пояснение
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // используемость элементов (от самого свежего к самому старому): 1
lRUCache.put(2, 2); // используемость: 2, 1; вместимость заполнена
lRUCache.get(1);    // возвращает 1, используемость: 1, 2
lRUCache.put(3, 3); // удаляет ключ 2, как менее используемый, помещает 3, вместимость: 3,1
lRUCache.get(2);    // возвращает -1 (нет такого ключа)
lRUCache.put(4, 4); // удаляет ключ 1, как менее используемый, помещает 4, используемость: 4, 3
lRUCache.get(1);    // возвращает -1 
lRUCache.get(3);    // возвращает 3, используемость: 3, 4
lRUCache.get(4);    // возвращает 4, используемость: 4, 3

 

Ограничения:

• 1 <= вместимость capacity <= 3000
• 0 <= ключ key <= 3000
• 0 <= значения <= 104
• Не более3 * 104вызовов функций get и put может быть.

Идея решения

Будем использовать хэшмап и двойной связный список. 

Имплементация

public class LRUCache {

  class DLinkedNode {
    int key; // ключ
    int value; //  значение
    DLinkedNode prev; // предыдущий узел
    DLinkedNode next; // следующий узел
  }

  private void addNode(DLinkedNode node) {
    /**
     * Новый узел добавляется всегда после "головы" списка
     */
    node.prev = head; // предыдущий элемент нового узла - голова списка
    node.next = head.next; // следущий элемент - бывший элемент после головы (бывший первый)

    head.next.prev = node; // бывший первый элемент теперь в качестве пред. имеет новый узел
    head.next = node; // голова указыает на новый узел, как на следующий
  }

  private void removeNode(DLinkedNode node){
    /**
     * Удаляем элемент из списка
     */
    DLinkedNode prev = node.prev; // запоминаем предыдущий удаляемого элемента
    DLinkedNode next = node.next; // запоминаем следующий удаляемого элемента

    prev.next = next; // предыдущий указывает на следующий
    next.prev = prev; // следующий указывает на предыдущий
// а поскольку на node больше нет указателей из других элементов, то он удален
  }

  private void moveToHead(DLinkedNode node){
    /**
     * Переместить элемент к "голове" (показатель свежеиспользованности)
     */
    removeNode(node); // удалим элемент из списка
    addNode(node); // добавим элемент в список,
// а добавление у нас сделано так, чтобы после "головы"
  }

// поля нашей структуры данных
  private Map<Integer, DLinkedNode> cache = new HashMap<>(); // хэшмап
  private int size; // размер
  private int capacity; // вместимость
  private DLinkedNode head, tail; // голова и хвост

// конструктор с инициализацией вместимости
  public LRUCache(int capacity) {
    this.size = 0; // структура пустая после создания, значит размер = 0
    this.capacity = capacity; // вместимость положительная

    head = new DLinkedNode(); // создаем голову
    // head.prev = null;

    tail = new DLinkedNode(); // создаем хвост
    // tail.next = null;

// связываем хвост и голову в список
    head.next = tail; // голова указывает на хвост
    tail.prev = head; // хвост указывает на голову
  }

private DLinkedNode popTail() {
    /**
     * Получить хвост списка
     */
    DLinkedNode res = tail.prev; // предыдущий перед фиктивным хвостом и есть хвост
    removeNode(res); // удаляем реальный хвост
    return res; // возвращаем удаленный узел
  }

// метод доступа по ключу
  public int get(int key) {
    DLinkedNode node = cache.get(key); // просто берем из хэшмапа
    if (node == null) return -1; // если не существует, то -1

    // если существует, то этот узел только что использован, переместим его к голове
    moveToHead(node);

    return node.value; // и вернем значение узла
  }

// метод добавления ключа и значения в кэш
  public void put(int key, int value) {
    DLinkedNode node = cache.get(key); // может уже есть такой ключ

    if(node == null) { // если такого ключа нет, то
// создаем узел
      DLinkedNode newNode = new DLinkedNode();
      newNode.key = key; // назначаем ему ключ
      newNode.value = value; // назначаем ему значение

      cache.put(key, newNode); // помещаем в кэш ключ-узел
      addNode(newNode); // добавляем узел в список (идет сразу после головы)

      ++size; // увеличиваем размер

// проверяем, не достигли ли вместимости
// и если достигли, то
      if(size > capacity) {
        // находим элемент в хвосте (наименее использованный) и удаляем его из списка
        DLinkedNode tail = popTail();
        cache.remove(tail.key); // удаляем узел из кэша по ключу
        --size; // уменьшаем размер структуры
      }
    } else { // если узел уже существует
      // обновляем значение узла.
      node.value = value;
      moveToHead(node); // узел только что использовался, помещаем его после головы
    }
  }
}

Сложность алгоритма

• Сложность по времени : $\mathcal{O}(1)$ для обеих операций put и get.

• Сложность по памяти : $\mathcal{O}(capacity)$ поскольку нам нужно место для хэшмапа и для двойного связного списка, и в каждой из этих структур у нас не более capacity + 1 элементов.