LRU算法

LRU

LRU 的全称是 Least Recently Used，是一种缓存淘汰策略，他的意思是最近使用过的数据放在最前面，如果需要删除数据，则删除最久没有用过的数据。LRU有很广泛的应用，比如说我们的内存策略等。我们的缓存容量是有限的，当我们需要载入新的数据时，必然要删除部分已有的数据，LRU就是这样的算法。

LRU的数据结构实现

朴素的看，这没什么难度啊，当我们使用某一数据时，我们只需要将其放在最初始的位置，然后其他数据的位置依次向后调整，当我们需要删除的时候，直接把最后一个数据删除掉即可。可是如果我们要求这些操作均为o(1)呢？这就有难度了。

我们首先看，我们需要哪些操作

• 任意点插入和删除的时间复杂度为o(1)，这个链表可以解决
• 查找的时间复杂度为o(1)， 这个hash表可以解决

那么如果要实现上面的两个，那么就需要使用LinkedHashSet了。

算法实现

• 实现一个双向链表
• 实现一个hashMap

#include "map"

using namespace std;

typedef struct Node {
    int key;
    int value;
    Node* prev;
    Node* next;
    Node(int k, int v) : key(k), value(v) {}
} Node;

class DoubleList {
public:
    DoubleList() {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->prev = nullptr;
        head->next = tail;
        tail->prev = head;
        tail->next = nullptr;
        size = 0;
    }
    void AddLast(Node* node) {
        node->prev = tail->prev;
        node->next = tail;
        node->prev->next = node;
        tail->prev = node;
        size++;
    }
    void RemoveNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
        size--;
    }
    Node* RemoveFirst() {
        if (head->next == tail) {
            return nullptr;
        }
        Node* node = head->next;
        RemoveNode(node);
        return node;
    }

    int GetSize() {
        return size;
    }
private:
    Node* head;
    Node* tail;
    int size;
}

class LRUCache {
public:
    LRUCache(int cap) : capacity(cap) {}
private:
    unordered_map<int, Node*> hashMap;
    DoubleList cache;
    int capacity;
}

146. LRU 缓存

这个题目就是上面的LRU的实际应用，我们可以直接将上面的代码运用上

• LRU就使用上面的数据结构
• 需要根据题目要求，抽象出几个API，以免重复的使用LRU中的原始接口，不好理解，容易出错且出错不好定位

  #include "map"
  
  using namespace std;
  
  typedef struct Node {
      int key;
      int value;
      Node* prev;
      Node* next;
      Node(int k, int v) : key(k), value(v) {}
  } Node;
  
  class DoubleList {
  public:
      DoubleList() {
          head = new Node(0, 0);
          tail = new Node(0, 0);
          head->prev = nullptr;
          head->next = tail;
          tail->prev = head;
          tail->next = nullptr;
          size = 0;
      }
      void AddLast(Node* node) {
          node->prev = tail->prev;
          node->next = tail;
          node->prev->next = node;
          tail->prev = node;
          size++;
      }
      void RemoveNode(Node* node) {
          node->prev->next = node->next;
          node->next->prev = node->prev;
          size--;
      }
      Node* RemoveFirst() {
          if (head->next == tail) {
              return nullptr;
          }
          Node* node = head->next;
          RemoveNode(node);
          return node;
      }
  
      int GetSize() {
          return size;
      }
  private:
      Node* head;
      Node* tail;
      int size;
  };
  
  class LRUCache {
  public:
      LRUCache(int cap) : capacity(cap) {
          cache = new DoubleList();
      }
      
      int get(int key) {
          if (hashMap.count(key)) {
              makeResently(key);
              return hashMap[key]->value;
          }
          return -1;
      }
      
      void put(int key, int value) {
          if (hashMap.count(key)) {
              deleteKey(key);
              addRencently(key, value);
              return;
          }
  
          if (capacity == cache->GetSize()) {
              removeLast();
          }
          addRencently(key, value);
      }
  
      void deleteKey(int key) {
          Node* node = hashMap[key];
          cache->RemoveNode(node);
          hashMap.erase(key);
      }
  
      void addRencently(int key, int value) {
          Node* node = new Node(key, value);
          hashMap.insert(pair(key, node));
          cache->AddLast(node);
      }
  
      void makeResently(int key) {
          Node* node = hashMap[key];
          cache->RemoveNode(node);
          cache->AddLast(node);
      }
  
      void removeLast() {
          Node* node = cache->RemoveFirst();
          hashMap.erase(node->key);
      }
  
  private:
      unordered_map<int, Node*> hashMap;
      DoubleList* cache;
      int capacity;
  };