简单的LRU Cache设计与实现

get(key)：若缓存中存在key，返回对应的value，否则返回-1

set(key,value):若缓存中存在key，替换其value，否则插入key及其value，如果插入时缓存已经满了，应该使用LRU算法把最近最久没有使用的key踢出缓存。

设计1：

cache使用数组，每个key再关联一个时间戳，时间戳可以直接用个long long类型表示，在cache中维护一个最大的时间戳：

• get的时候把key的时间戳变为最大时间戳+1
• set的时候， 数据从前往后存储
  如果key存在，更新key的时间戳为当前cache中最大的时间戳+1，并更新value；
  如果key不存在，
                若缓存满，在整个缓存中查找时间戳最小的key，其存储位置作为新key的存储位置，设置key的时间戳为最大时间戳+1
                若缓存未满，设置key的时间戳为最大时间戳+1，存储位置为第一个空闲位置

分析下时间空间复杂度，get的时候，需要从前往后找key，时间为O(N)，set的时候，也要从前往后找key，当缓存满的时候，还得找到时间戳最小的key，时间复杂度为O(N)。除了缓存本身，并没有使用其他空间，空间复杂度为O(1)。 这个速度显然是比较慢的，随着数据量的增大，get和set速度越来越慢。可能有人会想到用哈希表作为底层存储，这样get的时间复杂度确实可以减低为O(1)，set的时候，只要缓存没有满，也可以在O(1)的时间完，但在缓存满的时候，依然需要每次遍历找时间戳最小的key，时间复杂度还是O(N)。

设计2：

cache底层使用单链表，同时用一个哈希表存储每个key对应的链表结点的前驱结点，并记录链表尾结点的key

• get时，从哈希表中找到key对应的链表结点，挪到链表头，更新指向尾结点的key
• set时，如果key存在，那么找到链表结点，并挪到链表头，更新指向尾结点的key
            如果key不存在，
                                若缓存满，重用链表尾结点，设置新key和value，并挪到链表头，更新指向尾结点的key
                         若缓存未满，直接插入结点到链表头，若是第一结点，更新指向尾结点的key

get,set时间复杂度O(1)，总的空间复杂度O(N)。比前面的设计好一点。下面的再来看下关于设计2的两个实现

实现1，自定义链表

为了方便链表的插入与删除，使用了带头结点head的链表，所以真正有效的第一个结点是head->next。另外，只是简单的实现，没有容错，不支持并发，简单的内存管理

ps. 用双向链表来实现会简单写，这里用单链表和哈希表共同实现了双向链表的功效，也就是哈希除了用来查找，还指示了key对应的结点的前驱结点。

struct Node{      int _key;      int _value;      Node* _next;      Node(int key,int value,Node* next):_key(key),_value(value),_next(next){}  };    class LRUCache{  public:      LRUCache(int capacity) {          _capacity   = capacity;          _size       = 0;          _last       = 0;          _cur_begin  = _begin = (char *) malloc(sizeof(Node)*(capacity+1));          _head       = new (_cur_begin) Node(0,0,NULL);//在指定内存上构造对象          _cur_begin += sizeof(Node);      }        ~LRUCache(){          if(_begin!=NULL){              while(_cur_begin > _begin){                  _cur_begin -= sizeof(Node);                  ((Node*)_cur_begin)->~Node();//先释放内存上的对象              }              free(_begin);//再释放内存          }      }        int get(int key) {            int value             = -1;//初始时假设key对应的结点不存在            Node* pre_node_of_key = umap_prenodes[key];//key对应的结点的前驱结点            if(pre_node_of_key !=NULL){//key结点存在                Node* node             = pre_node_of_key->_next;//key对应的结点              pre_node_of_key->_next = node->_next;              if(pre_node_of_key->_next!=NULL){                  umap_prenodes[pre_node_of_key->_next->_key] = pre_node_of_key;              }                node->_next            = _head->_next;              if(node->_next!=NULL){//node有后继，更新后继的前驱结点                  umap_prenodes[node->_next->_key] = node;              }                _head->_next           = node;              umap_prenodes[key]     = _head;                              /*更新_last*/              if(_last == key ){                  _last = ( pre_node_of_key == _head ? key : pre_node_of_key->_key );               }                value = node->_value;          }          return value;      }        void set(int key, int value) {          Node* node            = NULL;          Node* pre_node_of_key = umap_prenodes[key];//key对应的结点的前驱结点            if(pre_node_of_key != NULL){//key对应的结点存在，孤立key对应的结点，也就是从链表中把结点取出来，重新链接链表                node                   = pre_node_of_key->_next;//key对应的结点              pre_node_of_key->_next = node->_next;                if(pre_node_of_key->_next!=NULL){                  umap_prenodes[pre_node_of_key->_next->_key] = pre_node_of_key;//更新前驱              }                node->_value           = value; //重置结点值                /*更新_last*/              if(_last == key ){                  _last = ( pre_node_of_key == _head ? key : pre_node_of_key->_key );               }          }else{//结点不存在                if(_capacity == 0){//缓冲区为空                  return ;              }                if(_size == _capacity){//缓存满，重用最后一个结点                    Node* pre_node_of_last    = umap_prenodes[_last];//最后一个结点的前驱结点                    umap_prenodes[pre_node_of_last->_next->_key] = NULL;                                    node                      = new (pre_node_of_last->_next) Node(key,value,NULL);//重用最后一个结点                    pre_node_of_last->_next   = NULL;//移出最后一个结点                    _last = ( pre_node_of_last == _head ? key : pre_node_of_last->_key ); //更新指向最后一个结点的key                }else{//缓冲未满，使用新结点                    node    = new (_cur_begin) Node(key,value,NULL);                  _cur_begin += sizeof(Node);                  _size++;                  if(_size==1){                      _last = key;                  }              }          }            /*把node插入到第一个结点的位置*/          node->_next            = _head->_next;          if(node->_next!=NULL){//node有后继，更新后继的前驱结点              umap_prenodes[node->_next->_key] = node;          }          _head->_next           = node;          umap_prenodes[key]     = _head;          }    private:      int   _size;      int   _capacity;      int   _last;//_last是链表中最后一个结点的key      Node* _head;      unordered_map<int,Node*> umap_prenodes;//存储key对应的结点的前驱结点，链表中第一个结点的前驱结点为_head            char* _begin;//缓存的起始位置       char* _cur_begin;//用于分配结点内存的起始位置  };

实现2，使用stl的list

这个版本的实现来自 LeetCode discuss

class LRUCache{      size_t m_capacity;      unordered_map<int,  list<pair<int, int>>::iterator> m_map; //m_map_iter->first: key, m_map_iter->second: list iterator;      list<pair<int, int>> m_list;                               //m_list_iter->first: key, m_list_iter->second: value;  public:      LRUCache(size_t capacity):m_capacity(capacity) {      }      int get(int key) {          auto found_iter = m_map.find(key);          if (found_iter == m_map.end()) //key doesn't exist              return -1;          m_list.splice(m_list.begin(), m_list, found_iter->second); //move the node corresponding to key to front          return found_iter->second->second;                         //return value of the node      }      void set(int key, int value) {          auto found_iter = m_map.find(key);          if (found_iter != m_map.end()) //key exists          {              m_list.splice(m_list.begin(), m_list, found_iter->second); //move the node corresponding to key to front              found_iter->second->second = value;                        //update value of the node              return;          }          if (m_map.size() == m_capacity) //reached capacity          {             int key_to_del = m_list.back().first;              m_list.pop_back();            //remove node in list;             m_map.erase(key_to_del);      //remove key in map          }          m_list.emplace_front(key, value);  //create new node in list          m_map[key] = m_list.begin();       //create correspondence between key and node      }  };

通过两个版本的实现，可以看到，使用stl的容器代码非常简洁，但也不是说自定义链表版本的实现就不好，如果从并发的角度来说，自定义的结构，在实现并发时，锁的粒度会小一点，而直接使用stl容器，锁的粒度为大一点，因为，使用stl，必须锁定一个函数，而使用自定义结构可以只锁定某个函数内部的某些操作，而且更方便实现无锁并发。另外，从leetcode的测试结果来看，这两个版本的性能差不多。