LRU (Least recently used，最近最少使用 ) 和 LFU (Least frequently used，最不经常使用)是两种经典的cache管理算法。其主要差别在于其核心思想：

• LRU：如果数据最近被访问过，那么将来被访问的几率也更高
• LFU：如果数据在最近一段时间内访问次数越少，那么将来被访问的几率也越低

LRU和LFU具备的操作主要是：get and put.

• get(key) - 返回key对应的值，如果key不存在，则返回-1
• put(key, value) - 如果key存在则将其对应的值设置为value，如果key不存在，则插入新的节点。如果cache已经满了，则需要以某种准则（满足某种函数f(x)）去除cache中已存在的节点。

这一数据结构的核心在于当存储空间满了要插入新的节点时，以何种规则（即所谓的f(x)）丢弃相应的节点。在设计LRU 和 LFU时的主要差别也在于此。

LRU的设计与实现

为了快速找到最早更新的节点，可选的数据结构有：queue，heap，linked list。由于题目又要求快速访问指定节点，并且在访问之后要更新它的时间顺序，queue和heap不太适用。因此考虑使用linked list，这里我们选用double linked list，简化节点的删除操作，实现O(1)的删除效率。并用hash table以便实现O(logn)时间随机访问节点。

首先是双链表的节点定义：

struct Node{
        Node *pre;
        Node *next;
        int key;
        int val;
        Node(int k,int v):key(k),val(v),pre(NULL),next(NULL){}
    };

使用map将key与相应的节点对应起来，实现以O(logn)时间随机访问linked list中的相应节点，并进行删除更新等相关操作。另外在构造函数中还需指定capacity的大小：

class LRUCache {
public：
LRUCache(int capacity) {
        capacity_ = capacity;
        head = NULL;
        tail = NULL;
        keyToNode.clear();
    }
private:
    int capacity_; 
    Node *head;//头节点
    Node *tail;//尾节点
    unordered_map<int,Node*> keyToNode;//key与节点Node的map
};

下面设计辅助函数。由于我们将节点按照使用的时间顺序插入double linked list当中，所以头节点是最少最近使用的节点，而尾节点是最近使用的节点。因此首先设计三个函数：删除头节点：removeHead()以及插入新节点：insertToEnd(int k, int v)，以及更新已存在节点在双链表中的顺序：moveToEnd(int key)。

    void insertToEnd(int k, int v){
        //if full or already exist, return
        if(isFull()||keyToNode.count(k)!=0) return;
        
        Node *nd = new Node(k,v);
        keyToNode[k] = nd;
        //if head = tail = NULL
        if(!head){
            head = tail = nd;
        }
        else{
            tail->next = nd;
            nd->pre = tail;
            tail = tail->next;
        }
    }
    
    void removeHead(){
        //if head not exist
        if(!head) return;
        keyToNode.erase(head->key);
        Node *tmp = head;
        if(head == tail)//if only one node
        {
            head = tail = NULL;
        }
        else{
            head = head->next;
            head->pre = NULL;
        }
        delete tmp;
    }
    
    void moveToEnd(int key){
        //if key not exist or already in the end
        if(keyToNode.count(key) == 0|| keyToNode[key] == tail) return;
        
        Node *nd = keyToNode[key];
        if(nd == head)//if at the front
        {
            head = head->next;
            head->pre = NULL;
        }
        else{
            nd->pre->next = nd->next;
            nd->next->pre = nd->pre;
        }
        tail->next = nd;
        nd->pre = tail;
        nd->next = NULL;
        tail = tail->next;
    }

get(int key)函数的设计比较简单，直接查找map中key值是否存在，如果不存在返回-1，反之，更新节点位置到链表尾端并返回其值即可。

    int get(int key) {
        if(keyToNode.count(key) == 0) return -1;
        //如果存在，将节点更新到链表尾端
        moveToEnd(key);
        return keyToNode[key]->val;
    }

put(int key, int value)分为以下情况：1.如果节点存在，只需要更新节点的值并更新节点在链表中的位置(moveToEnd)即可。这里我们使用get函数判断节点是否存在，则可以省略moveToEnd操作。2.如果节点不存在，则插入节点前需要判断是否溢出，如果溢出，则先将头节点删除再在尾节点插入新节点即可。

    void put(int key, int value) {
        //if already exist, update value
        if(get(key)!=-1){
            keyToNode[key]->val = value;
            return;
        }
        
        //if not exist, insert
        if(isFull()) removeHead();
        insertToEnd(key,value);
    }

代码清单： https://github.com/ShulinLiu/DataStructure-Algorithm/blob/master/LeetCode/LRUCache.hpp

以上即是LRU详解与C++实现，LFU的详解与实现将在下一篇文章介绍，敬请期待。