总结一下缓存置换算法。

  • LFU(Least Frequently Used) 算法

  最近最不常使用，缓存容量满的时候，置换使用频次最小的那个。

  • LRU(Least Recently Used) 算法

  最近最少使用，缓存容量满的时候，置换最长时间没有使用的那个。

  • LRU-K 算法

  LRU-k 有两个队列，一个队列是数据队列，一个队列是缓存队列，只有当数据队列数据的访问次数到达 K次，才将它放入缓存队列。

缓存队列按照 LRU 的方法置换数据。

常见的 LFU、LRU算法设计思路

  • LFU 设计思路

HashMap 加上小顶堆。每次排序，容量满则置换堆头。

  • LRU 设计思路

HashMap 加上双向链表。访问过的数据就移动到链表头，容量满了删除链表尾。

  • LRU-K 设计思路

HashMap 加上多级(0 ~ k - 1)队列，每多访问一次就放入下一个队列，达到 K 则放入缓存队列。

数据队列(链表)采用 FIFO 的思想：来一个新数据就放入队列尾，若访问了旧数据则把其移出到下一个队列或缓存队列，若容量满则删除队列头。

缓存队列和普通的LRU设计一样。

缓存污染问题

缓存污染说的是，历史记录的信息不再有用，导致命中率极剧下降。

  • LFU的缓存污染

如果新数据在后续过程中没有经常被访问，则会导致新数据不断被置换出去（因为新数据的频率始终是1）

  • LRU的缓存污染

周期性的访问数据会导致命中率急剧下降（如先访问 0~100范围的，然后访问其他范围，再回过头来访问0~100）

解决方法则是使用 LRU-K，目前综合性能 LRU-2最好。

C++ LRU实现

struct LRUNode{
    int key;
    int value;
    LRUNode *prev;
    LRUNode *next;
    LRUNode(int k, int v):key(k),value(v),prev(nullptr),next(nullptr){}
};

class LRUCache{
public:
    LRUCache(int length):length(length),size(0){}
    void set(int key, int value){
        auto find = indexes.find(key);
        if (find != indexes.end())
            return;

        if (size >= length){
            deleteTail();
        } else
            ++size;

        LRUNode *node = new LRUNode(key, value);
        if (head){
            node->next = head;
            head->prev = node;
        }else
            tail = node;
        head = node;
        indexes[key] = node;
    }

    int get(int key){
        auto find = indexes.find(key);
        if (find == indexes.end())
            return -1;

        moveToHead(find->second);
        return find->second->value;
    }

    void printValue(){
        for (auto beg = indexes.begin(); beg != indexes.end(); ++beg){
            cout << "key: " << beg->first << " value: " << beg->second->value << endl;
        }
    }

private:
    int length;
    int size;
    unordered_map<int, LRUNode *> indexes;
    LRUNode *head = nullptr;
    LRUNode *tail = nullptr;

    void deleteTail(){
        if (!tail)
            return;
        indexes.erase(tail->key);
        LRUNode *tailTmp = tail;
        if (tailTmp->prev){
            tailTmp->prev->next = nullptr;
            tail = tailTmp->prev;
        } else
            tail = nullptr;
        delete tailTmp;
    }

    void moveToHead(LRUNode *node){
        if (node == head)
            return;
        if (node == tail)
            tail = node->prev;

        if (node->prev)
            node->prev->next = node->next;
        if (node->next)
            node->next->prev = node->prev;

        node->next = head;
        head->prev = node;
        head = node;
    }
};