算法描述

LRU实际上是设计一个数据结构，有如下要求：

  • 包含容量capacity和当前元素数量size
  • 包含插入方法put和获取get
  • 时间复杂度为O(1);

    算法设计

    一般来说通过两个数据结构来实现LRU机制，即

    • 哈希表：用于存取【鍵-节点】对
    • 双向链表：用于存取【键-值】对，尾节点为最新加入的节点，头节点的后一结点为LRU节点

    LRU缓存机制结构 - 图1

  1. struct Node{
  2.     int key,value;
  3.     Node *pre,*next;
  4.     Node(int _k,int _v):
  5.         key(_k),value(_v),pre(nullptr),next(nullptr){}
  6. };
  7. class LRUCache {
  8.     const int MAXSIZE=3001;
  9.     Node* head;                
  10.     Node* tail;                /* for tail insertion method */
  11.     vector<Node*> cache_;
  12.     int capacity;
  13.     int size;
  14. public:
  15.     LRUCache(int c):
  16.         size(0),capacity(c) {
  17.             head=new Node(-1,-1);
  18.             tail=head;
  19.             cache_.resize(MAXSIZE,nullptr);
  20.     }
  22.     int get(int key) {
  23.         if(cache_[key]==nullptr){
  24.             /* not existed */
  25.             return -1;
  26.         }else{
  27.             /* existed */
  28.             Node* cur=cache_[key];
  29.             /* if cur is tail, ignore update*/
  30.             if(cur!=tail){
  31.                 /* release from original position */
  32.                 cur->pre->next=cur->next;
  33.                 cur->next->pre=cur->pre;
  34.                 /* update position to tail */
  35.                 tail->next=cur;
  36.                 cur->pre=tail;
  37.                 cur->next=nullptr;
  38.                 tail=cur;
  39.             }
  40.             return cur->value;
  41.         }
  42.     }
  44.     void put(int key, int value) {
  45.         if(get(key)==-1){
  46.             /* existed */
  47.             if(size<capacity){
  48.                 size++;
  49.             }else{
  50.                 /* delete the head->next node */
  51.                 Node *popNode=head->next;
  52.                 if(popNode==tail){
  53.                     tail->next=nullptr;
  54.                     tail->pre=nullptr;
  55.                     head->next=nullptr;
  56.                     tail=head;
  57.                 }else{
  58.                     head->next=popNode->next;
  59.                     popNode->next->pre=head;
  60.                 }
  61.                 popNode->next=nullptr;
  62.                 popNode->pre=nullptr;
  63.                 /* important! remove it from cache */
  64.                 cache_[popNode->key]=nullptr;
  65.                 delete popNode;
  66.             }
  67.             /* create new node (tail insertion)*/
  68.             Node *newNode=new Node(key,value);
  69.             cache_[key]=newNode;
  70.             tail->next=newNode;
  71.             newNode->pre=tail;
  72.             tail=newNode;
  73.         }else{
  74.             cache_[key]->value=value;
  75.         }
  76.     }
  77. };