LRU缓存策略

英文全称Least Recently Used，是页面置换算法的一种，即淘汰掉最长时间不使用的页面。
在缓存中，是一种缓存淘汰策略，优先删除很久没有用过的数据。

实现思路分析

设计put和get方法，实现O(1)时间的查找插入删除，应该用散列表；但散列表是无序的，要实现有序性，应该用链表结构。因此，一个哈希链表的结构符合我们的要求。

实现代码

题目来源：LeetCode 146
解法来源：LeetCode用户 labuladong

• 所需的数据结构（双向链表）

  //双向链表
  struct Node{
    size_t  key, val;
    Node* next;
    Node* pre;
    Node(size_t k, size_t v): key(k), val(v), next(nullptr), pre(nullptr) {}    
  };

• 双向链表需要的一些接口函数

  class DoubleList{
  private:
    Node head, tail;  //头尾哨兵节点
    size_t  size;  //链表长度
  public:
    //新建双向链表
    DoubleList(){
        head = new Node(0,0);
        tail = new Node(0,0);
        head->next = tail;
        tail->pre = head;
        size = 0;
    }
    //在头部添加节点
    void addToHead(Node n){
        Node* temp = head->next;
        n->next = temp;
        temp->pre = n;
        n->pre = head;
        head->next = x;
        size++;
    }
    //删除链表中n节点
    void deleteNode(Node n){
        Node* temp = n->next;
        n->pre->next = temp;
        temp->pre = n->pre;
        size--;
        delete n;
    }
    //删除链表最后一个节点并返回
    Node* deleteLast(){
        if(tail->pre==head) return nullptr;
        Node* last = tail->pre;
        last->pre->next = tail;
        tail->pre = last->pre;
        delete last;
        return last;
    }
    size_t getSize(){
        return size;
    }
  };

• 实现逻辑
  size = 2 容量大小为2
  put(1,1)，put(2,2); 把1和2 放进缓存中
  get(1,1) return 1; 查找1，找到返回1；
  put(3,3); 此时废除2
  get(2,2) return -1; 2已被废除，找不到返回-1

  LRUCache(int capacity) {
    }
  //key和Node映射
  unordered_map<size_t k, Node* pNode> hashmap;
  DoubleList cache;
  int get(int key){
    //没找到返回-1
    if(hashmap.find(key)==hashmap.end())  return -1;
    //找到了就把数据提到开头
    else{
        cache.addToHead(hashmap[key]);
        return hashmap[key]->val;
    }
  }
  int put(int key, int val){
    Node x = new Node(key, val);  //新插入的节点 x
    //如果插入的key已经存在就把旧的数据删除再插入，不存在就直接插入即可
    if(hashmap.find(key)!=hashmap.end()){
        cache.delete(hashmap[key]);
        cache.addToHead(x);
    }
    else{
        //如果cache满了，那就删除链表最后一个位置
        if(cache.getSize()==capcity){
            cache.deleteLast();
        }
        cache.addToHead(x);
        hashmap[key] = x;
    }
  }        

  C++解法（list+unordered_map）

  class LRUCache {
  private:
    int cap;
    list<pair<int, int>> cache;  //双向链表
    unordered_map<int key, list<pair<int, int>::iterator> > hashmap;
  }
  public:
    LRUCache(int capacity) {
        this->cap = capacity; 
    }
    int get(int key){
        auto it = hashmap[key];
        if(it==hashmap.end()) return -1;  //没找到
        pair<int, int> kv = *hashmap[key];
        cache.erase(map[key]);
        cache.push_front(kv);
        hashmap[key] = cache.begin();  //map中存的是迭代器，注意这一点！！
        return kv.second;
    }
    void put(int key, int value){
        auto it = hashmap[key];
        if(it==hashmap.end()){
            if(cache.size()==cap){
                auto lastPair = cache.back();
                map.erase(lastPair.first);
                cache.pop_back();
            }
            cache.push_front(make_pair<key, value>);
            hashmap[key] = cache.begin();
        }
        else{
            cache.erase(map[key]);
            cache.push_front(make_pair<key, value>);
            hashmap[key] = cache.begin();
        }
    }
  };