LRU和LFU

Node(k,v)存储最方便的应当是哈希表，但假设的是内存资源是有限的，所以在到达内存阈值的时候必须淘汰一些旧数据以存放新数据，这个时候的策略最常见的有LRU和LFU。LRU是“最近最久未使用”，淘汰的是最久未使用的数据。LFU是“最近最少使用算法”，淘汰的是使用频度最低的元素。通常有public方法：

int get(int key);
int put(int key, int value);

LRU

一个哈希表+一个双链表
哈希表存储Node(k,v)映射，淘汰则由std::list负责（尾部的是旧数据，头部的是最新数据)，实现较为简单：

class LRUCache{
    public:
        void put(int key, int val);
        int get(int key);
    private:
        struct Node{
            public:
                Node(int k, int v):key(k),value(v){}
            private:
                int key;
                int value;
        };
        int ksize;
        unordered_map<int,std::list<Node>::iterator> map;
        std::list<Node> LRUList;
};

关于更新数据：get和put都会更新最近最久未使用的数据，只需要将对应的Node*转移到list首部

int LRUCache::get(int key){
     if(map.find(key)==map.end()){
         return -1;   
    }
    LRUList.splice(LRUList.begin(),LRUList,map[key]);
    map[key]=LRUList.begin();
    return map[key]->val;
}
void LRUCache::put(int key,int val){
     if(map.find(key)!=map.end()){
        LRUList.splice(LRUList.begin(),LRUList,map[key]);
        map[key]=LRUList.begin();
        map[key]->val=val;
    }else{
         if(LRUList.size()==ksize){
             map.erase(LRUList.back()->key);
            LRUList.pop_back();
        }
         LRUList.push_front(Node(key,val));
         map[key]=LRUList.begin();   
    }
}

LFU

一个哈希表+用频率哈希映射多个双链表

双向链表节点：

struct Node {
    int key;
    int val;
    int freq;//频率
    Node* prev;
    Node* next;
    Node () : key(-1), val(-1), freq(0), prev(nullptr), next(nullptr) {}
    Node (int _k, int _v) : key(_k), val(_v), freq(1), prev(nullptr), next(nullptr) {}
};

频率的双向链表：

struct FreqList {
    int freq;
    //给双向链表加上了虚拟的头结点和尾结点，并在初始化的时候首尾相接。
    Node* head;
    Node* tail;
    FreqList (int _f) : freq(_f), head(new Node()), tail(new Node()) {
        head->next = tail;
        tail->prev = head;
    }
};

有了两个基本结构，就可以思路较清晰地写出LFU了：

class LFUCache{
    public:
        LFUCache (int capacity) : size(capacity) {}
        void put(int key, int val);
        int get(int key);
    private:
        int size;
        unordered_map<int,Node*> kvMap;
        unordered_map<int,FreqList*> freqMap;
        int min_freq;
    private:
        bool empty(FreqList* l);
        void removeNode(Node* t);
        void insertNode(Node* t);
        void popMinFreqList();
};

关于min_freq:

    每次get() 时，都有可能改变min_freq，所以每次都要查询对应的链表是否为空，为空说明min_freq被操作了一次，需要+1；
    每次put() 时，如果是新插入的值，那么其freq一定是1，是最小的，所以此时把min_freq重置为1；

关于更新数据：

由于put和get都会使得节点的频率增加，就需要跨频率链表移动节点，这需要辅助函数的支持：

    bool empty(FreqList* l) {
        return l->head->next == l->tail ? true : false;
    }
    void removeNode (Node* t) {
        t->prev->next = t->next;
        t->next->prev = t->prev;
    }
    void insertNode (Node* t) {
        int freq = t->freq;
        if (freqMap.find(freq) == freqMap.end()) {
            freqMap[freq] = new FreqList(freq);
        }
        FreqList* l = freqMap[freq];
        t->next = l->head->next;
        l->head->next->prev = t;
        t->prev = l->head;
        l->head->next = t;
    }
    void popTail () {
        Node* t = freqMap[min_freq]->tail->prev;
        removeNode(t);
        kvMap.erase(t->key);
    }

get和put

    int get (int key) {
        int res = -1;
        if (kvMap.find(key) != kvMap.end()) {
            Node* t = kvMap[key];
            res = t->val;
            removeNode(t);
            t->freq++;
            if (empty(freqMap[min_freq])) min_freq++;//最少频率更新
            insertNode(t);
        }
        return res;
    }

    void put (int key, int value) {
        if (size == 0) return;
        if (get(key) != -1) {
            kvMap[key]->val = value;
        }else {
            if (kvMap.size() == size) {
                popTail();
            }
            Node* t = new Node(key, value);
            kvMap[key] = t;
            min_freq = 1;//新插入的 频率一定最少, 为1
            insertNode(t);
        }
    }