LRU-LFU缓存算法

文章目录

- 缓存算法
- - LRU缓存算法
  - LFU缓存算法
  - - 定义
    - 实现
    - - 方法一：哈希表+平衡二叉树
      - 方法二：双哈希表+哈希链表
      - 方法三：双哈希表

缓存算法

LRU缓存算法

https://labuladong.online/algo/data-structure/lru-cache/

LRU（Least Recently Used）

LFU缓存算法

定义

LFU:Least Frequently Used，也就是每次淘汰那些使用次数最少的数据。

实现

方法一：哈希表+平衡二叉树

比较直观的想法就是我们用哈希表 key_table 以键 key 为索引存储缓存，建立一个平衡二叉树 S 来保持缓存根据 (cnt，time) 双关键字由于。在 C++ 中，我们可以使用 STL 提供的 std::set 类，set 背后的实现是红黑树：

对于 get(key) 操作，我们只要查看一下哈希表 key_table 是否有 key 这个键即可，有的话需要同时更新哈希表和集合中该缓存的使用频率以及使用时间，否则返回 -1。

对于 put(key, value) 操作，首先需要查看 key_table 中是否已有对应的键值。如果有的话操作基本等同于 get(key)，不同的是需要更新缓存的 value 值。如果没有的话相当于是新插入一个缓存，这时候需要先查看是否达到缓存容量 capacity，如果达到了的话，需要删除最近最少使用的缓存，即平衡二叉树中最左边的结点，同时删除 key_table 中对应的索引，最后向 key_table 和 S 插入新的缓存信息即可。


/*
https://leetcode.cn/problems/lfu-cache/description/
*/

struct Node {
    int timeStamp;
    int freq;
    int key;
    int val;

    Node (int key, int val, int freq, int timeStamp) : key(key), val(val), freq(freq), timeStamp(timeStamp) {}
    
    bool operator< (const Node& rhs) const
    {
        // 第一优先级，最久未使用的：频率小的
        if (freq != rhs.freq) {
            return freq < rhs.freq;
        }

        // 第二优先级,最久未使用的：时间老的
       
        return timeStamp < rhs.timeStamp;
    }
};

// leetCode 
class LFUCache {
public:
    LFUCache(int capacity) {
        capacity_ = capacity;
        curTime_ = 0;
        keyToCache_.clear();
    }
    
    int get(int key) {
        if (capacity_ == 0) {
            return -1;
        }

        // 找不到则返回-1
        auto iter = keyToCache_.find(key); 
        if (iter == keyToCache_.end()) {
            return -1;
        }

        // 找到了需要更新各属性
        Node& cache = iter->second;
        // 从平衡二叉树中删除旧的缓存
        cacheSet_.erase(cache);

        cache.timeStamp = ++curTime_;
        cache.freq++;

        // 将新缓存重新放入哈希表和平衡二叉树中
        cacheSet_.insert(cache);
        iter->second = cache;
        return cache.val;
    }
    
    void put(int key, int value) {
        if (capacity_ == 0) {
            return;
        }

        auto it = keyToCache_.find(key);
        // 缓存中没有
        if (it == keyToCache_.end()) {
            // 如果到达缓存容量上限
            if (keyToCache_.size() == capacity_) {
                // 从哈希表和平衡二叉树中删除最近最少使用的缓存
                keyToCache_.erase(cacheSet_.begin()->key); // 在set中存key的原因
                cacheSet_.erase(cacheSet_.begin());
            }
            // 创建新的缓存
            Node cache = Node(key, value, 1, ++curTime_);
            // 将新缓存放入哈希表和平衡二叉树中
            keyToCache_.insert(make_pair(key, cache));
            cacheSet_.insert(cache);
        } else { // 缓存中已经有了，则更新各个属性
            Node cache = it->second;
            // 从平衡二叉树中删除旧的缓存
            cacheSet_.erase(cache);

            cache.timeStamp = ++curTime_;
            cache.freq++;
            cache.val = value;

            // 将新缓存重新放入哈希表和平衡二叉树中
            cacheSet_.insert(cache);
            it->second = cache;
        }
    }

private:
    int capacity_;
    int curTime_;
    unordered_map<int, Node> keyToCache_; // 指向cache的key-val
    set<Node> cacheSet_; // cache 队列
};

在这里插入图片描述

方法二：双哈希表+哈希链表

参考：https://blog.csdn.net/sj15814963053/article/details/122731147
一定先从最简单的开始，根据 LFU 算法的逻辑，我们先列举出算法执行过程中的几个显而易见的事实：

1、调用 get(key) 方法时，要返回该 key 对应的 val。

2、只要用 get 或者 put 方法访问一次某个 key，该 key 的 freq 就要加一。

3、如果在容量满了的时候进行插入，则需要将 freq 最小的 key 删除，如果最小的 freq 对应多个 key，则删除其中最旧的那一个。

好的，我们希望能够在 O(1) 的时间内解决这些需求，可以使用基本数据结构来逐个击破：

1、使用一个 HashMap 存储 key 到 val 的映射，就可以快速计算 get(key)。

unordered_map<int, int> keyToVal;

2、使用一个 HashMap 存储 key 到 freq 的映射，就可以快速操作 key 对应的 freq。

unordered_map<int, int> keyToFreq;

3、这个需求应该是 LFU 算法的核心，所以我们分开说。

a.首先，肯定是需要freq到key的映射，用来找到freq最小的key。
b.将freq最小的key删除，那你就得快速得到当前所有key最小的freq是多少。想要时间复杂度 O(1) 的话，肯定不能遍历一遍去找，那就用一个变量minFreq来记录当前最小的freq吧。
c.可能有多个key拥有相同的freq，所以 freq对key是一对多的关系，即一个freq对应一个key的列表。
d.希望freq对应的key的列表是存在时序的，便于快速查找并删除最旧的key。
e.希望能够快速删除key列表中的任何一个key，因为如果频次为freq的某个key被访问，那么它的频次就会变成freq+1，就应该从freq对应的key列表中删除，加到freq+1对应的key的列表中。

HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
int minFreq = 0;

介绍一下这个LinkedHashSet，它满足我们 cde 这几个要求。你会发现普通的链表LinkedList能够满足 cd 这两个要求，但是由于普通链表不能快速访问链表中的某一个节点，所以无法满足 3.5 的要求。

LinkedHashSet顾名思义，是链表和哈希集合的结合体。链表不能快速访问链表节点，但是插入元素具有时序；哈希集合中的元素无序，但是可以对元素进行快速的访问和删除。

那么，它俩结合起来就兼具了哈希集合和链表的特性，既可以在 O(1) 时间内访问或删除其中的元素，又可以保持插入的时序，高效实现 e 这个需求。

put() 流程图：
在这里插入图片描述

删除某个键key肯定是要同时修改三个映射表的，借助minFreq参数可以从FK表中找到freq最小的keyList，根据时序，其中第一个元素就是要被淘汰的deletedKey，操作三个映射表删除这个key即可。

但是有个细节问题，如果keyList中只有一个元素，那么删除之后minFreq对应的key列表就为空了，也就是minFreq变量需要被更新。如何计算当前的minFreq是多少呢？

实际上没办法快速计算minFreq，只能线性遍历FK表或者KF表来计算，这样肯定不能保证 O(1) 的时间复杂度。

但是，其实这里没必要更新minFreq变量，因为你想想removeMinFreqKey这个函数是在什么时候调用？在put方法中插入新key时可能调用。而你回头看put的代码，插入新key时一定会把minFreq更新成 1，所以说即便这里minFreq变了，我们也不需要管它。

更新某个key的freq肯定会涉及FK表和KF表，所以我们分别更新这两个表就行了。

和之前类似，当FK表中freq对应的列表被删空后，需要删除FK表中freq这个映射。如果这个freq恰好是minFreq，说明minFreq变量需要更新。

能不能快速找到当前的minFreq呢？这里是可以的，因为我们刚才把key的freq加了 1 嘛，所以minFreq也加 1 就行了。

至此，经过层层拆解，LFU 算法就完成了。

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译。
// 本代码的正确性已通过力扣验证，如有疑问，可以对照我的 java 代码查看。

#include <unordered_map>
#include <unordered_set>
#include <list>
using namespace std;

class LFUCache {
    // key 到 val 的映射，我们后文称为 KV 表
    unordered_map<int, int> keyToVal;
    // key 到 freq 的映射，我们后文称为 KF 表
    unordered_map<int, int> keyToFreq;
    // freq 到 key 列表的映射，我们后文称为 FK 表
    unordered_map<int, list<int>> freqToKeys;
    // 记录最小的频次
    int minFreq;
    // 记录 LFU 缓存的最大容量
    int cap;

public:
    LFUCache(int capacity) {
        this->cap = capacity;
        this->minFreq = 0;
    }

    int get(int key) {
        if (keyToVal.find(key) == keyToVal.end()) {
            return -1;
        }
        // 增加 key 对应的 freq
        increaseFreq(key);
        return keyToVal[key];
    }

    void put(int key, int val) {
        if (this->cap <= 0) return;

        // 若 key 已存在，修改对应的 val 即可
        if (keyToVal.find(key) != keyToVal.end()) {
            keyToVal[key] = val;
            // key 对应的 freq 加一
            increaseFreq(key);
            return;
        }

        // key 不存在，需要插入
        // 容量已满的话需要淘汰一个 freq 最小的 key
        if (this->cap <= keyToVal.size()) {
            removeMinFreqKey();
        }

        // 插入 key 和 val，对应的 freq 为 1
        // 插入 KV 表
        keyToVal[key] = val;
        // 插入 KF 表
        keyToFreq[key] = 1;
        // 插入 FK 表
        freqToKeys[1].push_back(key);
        // 插入新 key 后最小的 freq 肯定是 1
        this->minFreq = 1;
    }

private:
    void increaseFreq(int key) {
        int freq = keyToFreq[key];
        // 更新 KF 表
        keyToFreq[key] = freq + 1;
        // 更新 FK 表
        // 将 key 从 freq 对应的列表中删除
        freqToKeys[freq].remove(key);
        // 将 key 加入 freq + 1 对应的列表中
        freqToKeys[freq + 1].push_back(key);
        // 如果 freq 对应的列表空了，移除这个 freq
        if (freqToKeys[freq].empty()) {
            freqToKeys.erase(freq);
            // 如果这个 freq 恰好是 minFreq，更新 minFreq
            if (freq == this->minFreq) {
                this->minFreq++;
            }
        }
    }

    void removeMinFreqKey() {
        // freq 最小的 key 列表
        auto& keyList = freqToKeys[this->minFreq];
        // 其中最先被插入的那个 key 就是该被淘汰的 key
        int deletedKey = keyList.front();
        // 更新 FK 表
        keyList.pop_front();
        if (keyList.empty()) {
            freqToKeys.erase(this->minFreq);
            // 问：这里需要更新 minFreq 的值吗？
        }
        // 更新 KV 表
        keyToVal.erase(deletedKey);
        // 更新 KF 表
        keyToFreq.erase(deletedKey);
    }
};

方法三：双哈希表

/*
freq_table: 以频率 freq 为索引，每个索引存放一个双向链表，这个链表里存放所有使用频率为 freq 的缓存，缓存里存放三个信息，分别为键 key，值 value，以及使用频率 freq
key_table: 以键值 key 为索引，每个索引存放对应缓存在 freq_table 中链表里的内存地址
minfreq: 同时需要记录一个当前缓存最少使用的频率 minFreq，这是为了删除操作服务的。
*/

// 缓存的节点信息
struct Node {
    int key, val, freq;
    Node(int key, int val, int freq): key(key), val(val), freq(freq){}
};
class LFUCache {
    int minfreq; // 当前缓存最少使用的频率 minFreq，这是为了删除操作服务的。
    int capacity;
    unordered_map<int, list<Node>::iterator> key_table;
    unordered_map<int, list<Node>> freq_table;
public:
    LFUCache(int _capacity) {
        minfreq = 0;
        capacity = _capacity;
        key_table.clear();
        freq_table.clear();
    }
    
    int get(int key) {
        if (capacity == 0) {
            return -1;
        }

        auto it = key_table.find(key);
        if (it == key_table.end()) {
            return -1;
        }

        list<Node>::iterator node = it->second;
        int val = node->val
        int freq = node->freq;
        freq_table[freq].erase(node);

        // 如果当前链表为空，我们需要在哈希表中删除，且更新minFreq
        if (freq_table[freq].size() == 0) {
            freq_table.erase(freq);
            if (minfreq == freq) {
                minfreq += 1;
            }
        }
        // 插入到 freq + 1 中
        freq_table[freq + 1].push_front(Node(key, val, freq + 1));
        key_table[key] = freq_table[freq + 1].begin();
        return val;
    }
    
    void put(int key, int value) {
        if (capacity == 0) {
            return;
        }

        auto it = key_table.find(key);
        if (it == key_table.end()) {
            // 缓存已满，需要进行删除操作
            if (key_table.size() == capacity) {
                // 通过 minFreq 拿到 freq_table[minFreq] 链表的末尾节点
                auto it2 = freq_table[minfreq].back();
                key_table.erase(it2.key);
                freq_table[minfreq].pop_back();
                if (freq_table[minfreq].size() == 0) {
                    freq_table.erase(minfreq);
                }
            } 
            freq_table[1].push_front(Node(key, value, 1));
            key_table[key] = freq_table[1].begin();
            minfreq = 1;
        } else {
            // 与 get 操作基本一致，除了需要更新缓存的值
            list<Node>::iterator node = it->second;
            int freq = node->freq;
            freq_table[freq].erase(node);
            if (freq_table[freq].size() == 0) {
                freq_table.erase(freq);
                if (minfreq == freq) {
                    minfreq += 1;
                }
            }
            freq_table[freq + 1].push_front(Node(key, value, freq + 1));
            key_table[key] = freq_table[freq + 1].begin();
        }
    }
};

在这里插入图片描述

在这里插入图片描述
更新的时候为什么是插入到链表头，这其实是为了保证缓存在当前链表中从链表头到链表尾的插入时间是有序的，为下面的删除操作服务。

对于 put(key, value) 操作，我们先通过索引 key在 key_table 中查看是否有对应的缓存，如果有的话，其实操作等价于 get(key) 操作，唯一的区别就是我们需要将当前的缓存里的值更新为 value。如果没有的话，相当于是新加入的缓存，如果缓存已经到达容量，需要先删除最近最少使用的缓存，再进行插入。

先考虑插入，由于是新插入的，所以缓存的使用频率一定是 1，所以我们将缓存的信息插入到 freq_table 中 1 索引下的列表头即可，同时更新 key_table[key] 的信息，以及更新 minFreq = 1。

那么剩下的就是删除操作了，由于我们实时维护了 minFreq，所以我们能够知道 freq_table 里目前最少使用频率的索引，同时因为我们保证了链表中从链表头到链表尾的插入时间是有序的，所以 freq_table[minFreq] 的链表中链表尾的节点即为使用频率最小且插入时间最早的节点，我们删除它同时根据情况更新 minFreq ，整个时间复杂度均为 O(1)。