LRU 缓存淘汰策略

LRU 全称 Least Recently Use，广泛应用于缓存机制中。

应用场景：缓存使用的空间达到上限后，就需要从已有的数据中淘汰一部分以维持缓存的可用性，而如何淘汰数据，就是通过 LRU 算法完成的。

如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。

原理

当访问一个数据时：

1. 该数据不在容器之中，那么设置该数据的优先级为最高并放入容器中
2. 该数据在容器中，那么设置该数据的优先级为最高

数据的总量达到上限后，则移除容器中优先级最低的数据。

解析

使用哈希表和双向链表进行实现。

哈希表通过缓存数据的键映射到其在双向链表中的位置（也即指针）

双向链表存储键值对，靠近头部的键值对是最近使用的，靠近尾部的键值对是最久未使用的。

这样，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1) 时间内完成 get 或 put 操作。

get

1. 如果 key 存在，则 key 对应的节点是最近被使用的节点，通过哈希表定位到节点在双向链表中的位置，然后将其移动到双向链表的头部，最后返回该节点的值即可
2. 如果 key 不存在，直接返回 -1

put

1. 如果 key 存在，则类似于 get 操作，首先通过哈希表定位，然后将对应节点的值更新为 value，并将该节点移动至双向链表的头部
2. 如果 key 不存在，首先构造一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加到哈希表中。然后判断双向链表的节点数是否超出容量，如果超出，则删除双向链表的尾部节点，并删除哈希表中对应的项

示例代码

struct DListNode {
  int key;
  int value;
  DListNode *next;
  DListNode *prev;
  DListNode() : key(0), value(0), next(nullptr), prev(nullptr) {}
  DListNode(int x) : key(x), value(0), next(nullptr), prev(nullptr) {}
};

class LRUCache {
private:
  unordered_map<int, DListNode *> map;
  DListNode *head;
  DListNode *tail;
  int capacity;
  int size;

private:
  void AddToHead(DListNode *node) {
    node->prev = head;
    node->next = head->next;
    head->next->prev = node;
    head->next = node;
  }
  void RemoveNode(DListNode *node) {
    DListNode *prev = node->prev;
    DListNode *next = node->next;
    prev->next = next;
    next->prev = prev;
  }

  DListNode *RemoveTail() {
    DListNode *node = tail->prev;
    RemoveNode(node);
    return node;
  }

  void MoveItemHead(DListNode *node) {
    RemoveNode(node);
    AddToHead(node);
  }

public:
  LRUCache(int capacity) : capacity(capacity), size(0) {
    head = new DListNode();
    tail = new DListNode();
    head->next = tail;
    tail->prev = head;
  }

  int get(int key) {
    if (map.find(key) == map.end())
      return -1;
    else {
      DListNode *node = map[key];
      MoveItemHead(node);
      return node->value;
    }
  }

  void put(int key, int value) {
    if (map.find(key) != map.end()) {
      DListNode *node = map[key];
      node->value = value;
      MoveItemHead(node);
      return;
    }
    DListNode *node = new DListNode(key);
    node->value = value;
    AddToHead(node);
    map[key] = node;
    size++;
    if (size > capacity) {
      DListNode *rm = RemoveTail();
      map.erase(rm->key);
      delete rm;
      size--;
    }
  }
};