LFU算法（Least Frequently Used）与LRU算法（Least Recently Used）均为缓存淘汰算法。LRU用于淘汰最久未使用的数据，LFU用于淘汰最少使用的数据，如果使用频率相同的情况下，淘汰最久未使用的数据。所以实际上LFU算法要比LRU算法更复杂一些。

一、LRU算法

力扣：LRU算法（Least Recently Used），用于淘汰最久未使用的数据，LRU算法在力扣上的代码框架如下，需要实现get与put方法。

class LRUCache {
public:
    LRUCache(int capacity) {
        
    }
    
    int get(int key) {
        
    }
    
    void put(int key, int value) {
        
    }
};

先来梳理一下，每个函数里面要实现哪些功能。

class LRUCache {
public:
    int _capacity;
    int _size;
    unordered_map<int, DLinkedNode *> _map;
    DLinkedNode *virHead; /* 队列的队头，指向最久未使用的元素 */
    DLinkedNode *virTail; /* 队列的队尾，指向最近使用的元素 */
    LRUCache(int capacity) : _capacity(capacity) {
    }
    ~LRUCache() {
        /* 释放内存 */
    }
    int get(int key) {
        /* 1、通过key，获取指定的value，如未命中则返回-1 */
        /* 2、如果命中，由于该数据最近被访问，所以将该数据移动至最近使用数据 */
    }
    
    void put(int key, int value) {
        /* 1、插入kv数据，如果key已存在，则更新数据 */
        /* 2、如果数据不存在，则插入数据；插入数据需要判断当前容量是否已达到LRUCache容量，如果已达到容量，则弹出最久未使用的一条数据，如果尚未达到LRUCache容量，则直接插入数据 */
        /* 3、弹出数据时，要同时弹出链表中的数据，以及哈希表中的数据 */
        /* 4、由于插入的数据被操作，所以该数据需要放到最近使用数据的位置 */
    }
};

最终C++实现如下

#include <unordered_map>
#include <iostream>
using namespace std;
struct DLinkedNode {
    int key;
    int value;
    DLinkedNode *prev;
    DLinkedNode *next;
    DLinkedNode(int key, int value) : key(key), value(value), prev(nullptr), next(nullptr) {}
};
class LRUCache {
public:
    int _capacity;
    int _size;
    unordered_map<int, DLinkedNode *> _map;
    DLinkedNode *virHead; /* 队列的队头，指向最久未使用的元素 */
    DLinkedNode *virTail; /* 队列的队尾，指向最近使用的元素 */
    LRUCache(int capacity) : _capacity(capacity) {
        /* 指定LRUCache的容量大小 */
        virHead = new DLinkedNode(-1, -1);
        virTail = new DLinkedNode(-1, -1);
        virHead->next = virTail;
        virTail->prev = virHead;
    }
    ~LRUCache() {
        /* 释放内存 */
        DLinkedNode *node = virHead;
        while (node != nullptr) {
            DLinkedNode *tmp = node->next;
            delete node;
            node = tmp;
        }
    }
    void updateList(DLinkedNode *target) {
        target->prev->next = target->next;
        target->next->prev = target->prev;
        target->next = virTail;
        target->prev = virTail->prev;
        target->prev->next = target;
        virTail->prev = target;
    }
    void pop() {
        if (_map.size() == 0) { /* 没有元素可以pop */
            return;
        }
        DLinkedNode *needDelNode = virHead->next;
        _map.erase(needDelNode->key);
        virHead->next = virHead->next->next;
        virHead->next->prev = virHead;
        delete needDelNode;
    }
    void push(DLinkedNode *node) {
        node->next = virTail;
        node->prev = virTail->prev;
        node->prev->next = node;
        node->next->prev = node;
    }
    int get(int key) {
        /* 1、通过key，获取指定的value，如未命中则返回-1 */
        auto it = _map.find(key);
        if (it == _map.end()) {
            return -1;
        }
        /* 2、如果命中，由于该数据最近被访问，所以将该数据移动至最近使用数据 */
        DLinkedNode *target = it->second;
        updateList(target);
        return target->value;
    }
    
    void put(int key, int value) {
        /* 1、插入kv数据，如果key已存在，则更新数据 */
        auto it = _map.find(key);
        if (it != _map.end()) {
            it->second->value = value;
            updateList(it->second);
            return;
        }
        /* 2、如果数据不存在，则插入数据；插入数据需要判断当前容量是否已达到LRUCache容量，如果已达到容量，则弹出最久未使用的一条数据，如果尚未达到LRUCache容量，则直接插入数据，并更新当前size */
        if (_map.size() == _capacity) {
            pop();
        }
        DLinkedNode *node = new DLinkedNode(key, value);
        /* 3、由于插入的数据被操作，所以该数据需要放到最近使用数据的位置 */
        _map[key] = node;
        push(node);
    }
};
int main(int argc, char *argv[])
{
    LRUCache lRUCache(2);
    lRUCache.put(1, 1); // 缓存是 {1=1}
    lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
    cout << lRUCache.get(1) << endl;    // 返回 1
    lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
    cout << lRUCache.get(2) << endl;    // 返回 -1 (未找到)
    lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
    cout << lRUCache.get(1) << endl;    // 返回 -1 (未找到)
    cout << lRUCache.get(3) << endl;    // 返回 3
    cout << lRUCache.get(4) << endl;    // 返回 4
}

二、LFU算法

力扣：LFU算法（Last Frequently Used），用于淘汰使用频率最低的数据，LFU在力扣上的代码框架如下，同样需要实现get和put方法。

class LFUCache {
public:
    LFUCache(int capacity) {
        
    }
    
    int get(int key) {
        
    }
    
    void put(int key, int value) {
        
    }
};

先来梳理一下实现LFU的思路。

LFU的难点如下：

O(1)复杂度找到需要被弹出的元素（访问频次最低的元素中，最久未被使用的那个元素）

首先为了实现get方法，通过key能在O(1)复杂度内获取value，只能使用哈希表，映射key对应的value，因此新增成员变量_kvmap。

插入一个新元素，可能需要弹出一个旧的元素，需要找到需要被弹出的元素。被弹出的应该是访问频次最低的元素，那么我维护一个链表，仍然是把即将弹出的元素放在最前面，这样我可以O(1)地弹出元素，但是新元素在链表中应该插在什么位置，是无法在O(1)时间复杂度完成的，因为新元素的访问频次仅为1，而旧元素的访问频次可能远高于1，所以新元素不能插在队尾。对于链表如果不能插在队尾，那么就遍历链表节点了，这就不是O(1)复杂度了。

那么如何解决这个问题呢，首先我需要知道每个元素的访问频次，那么再维护一个哈希表，_kfmap，用于获取元素的访问频次。有了元素的访问频次之后，我们可以记录当前所有元素中最低的访问频次，那么如果能够由最低的访问频次，获取对应的元素，那么就可以找到那个被弹出的元素了。这样的话，我们可以维护一个访问频次与key之间的哈希映射关系，即_fkmap。

但是最低的访问频次，对应的是多个元素，不一定是单个元素，那么可以这样想，维护一个链表，在这个链表中，最久未被访问的元素放在队头，这样，通过哈希表定位到这个链表之后，就把链表头部元素弹出，这样就能在O(1)时间内把访问频次最低的最久未被使用的元素弹出。

到这里我们设想的数据结构，已经能在O(1)时间内，弹出目标元素，然后再插入元素时，同时维护_kvmap，_kfmap，以及_fkmap。维护_fkmap时，从f对应的链表中，把队头元素弹出，在freq = 1的链表的队尾插入新的元素即可。这样我们已经能够完成put方法的功能。

再来看get方法，访问一个元素，需要记录该元素被访问，增加该元素被访问的频次。那么该元素访问频次增加后，就需要从原来的_fkmap中删除，那么需要到该元素的freq对应的链表中，去定位该元素，并将元素删除，这就又要遍历链表了，因为被访问的元素，很可能并不是链表的队头也不是队尾元素，遍历链表的话，复杂度又超过了要求，因此_fkmap如果是freq通过哈希映射到一个链表的话，这种数据结构仍然不能满足需要。那么我们希望它在链表的基础上，还能实现O(1)的元素定位功能，那么实际上它应该是orderedhashmap这样一个结构。

用代码来整理一下刚才的思路：

未完待续…（实际上看了官方力扣题解，我的解题思路中有很多可以优化的点，首先kvmap和kfmap可以合并，这个点并不难想到，第二kvmap中，存储的并不是value的值，而是存储一个指针，指向value所在结构体的地址，这样在get方法中，就可以直接索引到节点所在的地址，有了地址，在链表中进行增删操作，其操作复杂度均为O(1)，官方题解用的是list::iterator，相当于指针，等我再来优化我的代码）

最终实现如下：

#include <unordered_map>
using namespace std;
class DoubleLinkedNode {
public:
    DoubleLinkedNode *last_ = nullptr;
    DoubleLinkedNode *next_ = nullptr;
    int key_;
    DoubleLinkedNode(int key):key_(key) {}
};
class DoubleLinkedList {
private:
    DoubleLinkedNode *head_;
    DoubleLinkedNode *tail_;
public:
    ~DoubleLinkedList() {
        while (head_ != nullptr) {
            DoubleLinkedNode *node = head_;
            head_ = head_->next_;
            delete node;
        }
    }
    int Front() {
        if (head_ != nullptr) {
            return head_->key_;
        }
        return 0;
    }
    void Push_back(DoubleLinkedNode *node) {
        if (tail_ == nullptr) {
            tail_ = node;
            head_ = tail_;
        } else {
            tail_->next_ = node;
            node->last_ = tail_;
            node->next_ = nullptr;
            tail_ = node;
        }
    }
    void Erase(DoubleLinkedNode *node) {
        if (node == nullptr) {
            return;
        }
        DoubleLinkedNode *lastNode = node->last_;
        DoubleLinkedNode *nextNode = node->next_;
        if (lastNode == nullptr) { /* 说明node就是head */
            head_ = nextNode;
        } else {
            lastNode->next_ = nextNode;
        }
        if (nextNode == nullptr) { /* 说明node就是tail */
            tail_ = lastNode;
        } else {
            nextNode->last_ = lastNode;
        }
        delete node;
    }
};
class OrderedHashSet {
private:
    /* <key, address of the key in keyList_> */
    unordered_map<int, DoubleLinkedNode *> keyMap_;
    DoubleLinkedList keyList_;
public:
    void Insert(int key) {
        DoubleLinkedNode *node = new DoubleLinkedNode(key);
        keyList_.Push_back(node);
        keyMap_[key] = node;
    }
    void Erase(int key) {
        if (keyMap_.find(key) == keyMap_.end()) { /* 如果找不到，说明key不存在，没有继续执行erase的必要 */
            return;
        }
        keyList_.Erase(keyMap_[key]);
        keyMap_.erase(key);
    }
    int Size() {
        return keyMap_.size();
    }
    int Front() {
        return keyList_.Front();
    }
};
class LFUCache {
private:
    unordered_map<int, int> kvMap_; /* key to value */
    unordered_map<int, int> kfMap_; /* key to freq */
    unordered_map<int, OrderedHashSet> freqToHashKeyMap_; /* freq to key */
    int maxCapacity_;
    int minFreq_ = 0;
public:
    LFUCache(int capacity):maxCapacity_(capacity) {
    }
    
    int get(int key) {
        if (kvMap_.find(key) == kvMap_.end()) {
            return -1;
        }
        int value = kvMap_[key];
        UpdateKeyFreqInVisit(key);
        return value;
    }
    
    void put(int key, int value) {
        if (kvMap_.find(key) == kvMap_.end()) {
            if (kvMap_.size() >= maxCapacity_) {
                /* 移除最不经常使用的一项 */
                int delKey = freqToHashKeyMap_[minFreq_].Front();
                FreqToHashKeyMapErase(minFreq_, delKey);
                kfMap_.erase(delKey);
                kvMap_.erase(delKey);
            }
            kfMap_[key] = 1;
            minFreq_ = 1;
            FKMapInsert(1, key);
        } else {
            UpdateKeyFreqInVisit(key);
        }
        kvMap_[key] = value;
    }
    void UpdateKeyFreqInVisit(int key) {
        int freq = kfMap_[key];
        FreqToHashKeyMapErase(freq, key);
        FKMapInsert(freq + 1, key);
        kfMap_[key]++;
    }
    void FreqToHashKeyMapErase(int freq, int key) {
        freqToHashKeyMap_[freq].Erase(key);
        if (freqToHashKeyMap_[freq].Size() == 0) {
            freqToHashKeyMap_.erase(freq);
/* minFreq_的变化分为两种情况：
一种是读了数据或者更新了数据，导致freq++，这时候，如果当前freq是minfreq，只需要minfreq++，因为freq将变为freq+1；
一种是插入数据时，纯粹地删掉minfreq的头部节点元素，这时候，如果minfreq的链表为空，minfreq将移动到下一个freq，而下一个freq并不一定是freq + 1
而到底下一个freq是多少，并不知道，但由于这时候，插入了一个新的元素，所以下一个freq是谁并不重要，因为minfreq将必然变为1 */
            if (freq == minFreq_) {
                minFreq_++;
            }
        }
    }
    void FKMapInsert(int freq, int key) {
        freqToHashKeyMap_[freq].Insert(key);
    }
};