【leetcode】缓存淘汰策略题目总结

146. LRU 缓存

我们使用了一个双向链表cache来存储数据，同时使用一个哈希表hash_map来映射键和链表节点的迭代器。当调用get(key)函数时，我们首先检查hash_map中是否存在该key，如果存在则将之前位置移到链表头部并返回值；当调用put(key, value)函数时，我们先检查hash_map中是否存在该key，存在的话将该节点从链表中删除，不管存在与否都需要考虑是否需要删除旧数据（缓存已满的情况）。

class LRUCache {
private:
    int _capacity;
    list<pair<int, int>> _cache;
    unordered_map<int, list<pair<int, int>>::iterator> _hashmap;
 
public:
    LRUCache(int capacity) {
        _capacity = capacity;
    }
    
    int get(int key) {
        if (_hashmap.find(key) == _hashmap.end()) {
            return -1;
        }
        auto iter = _hashmap[key];
        int value = iter->second;
        _cache.erase(iter);
        _cache.push_front({key, value});
        _hashmap[key] = _cache.begin();
        return value;
    }
    
    void put(int key, int value) {
        if (_hashmap.find(key) != _hashmap.end()) {
            auto iter = _hashmap[key];
            _cache.erase(iter);
        } else if (_cache.size() >= _capacity) {
            auto hashKey = _cache.back().first;
            _hashmap.erase(hashKey);
            _cache.pop_back();
        }
        _cache.push_front({key, value});
        _hashmap[key] = _cache.begin();
    }
};
 
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

460. LFU 缓存

我们定义两个哈希表，

第一个 freq_table 以频率 freq 为索引，每个索引存放一个双向链表，这个链表里存放所有使用频率为 freq 的缓存，缓存里存放三个信息，分别为键 key，值 value，以及使用频率 freq。

第二个 key_table 以键值 key 为索引，每个索引存放对应缓存在 freq_table 中链表里的内存地址，这样我们就能利用两个哈希表来使得两个操作的时间复杂度均为 O(1)。

同时需要记录一个当前缓存最少使用的频率 minFreq，这是为了删除操作服务的。

struct Node
{
    int key;
    int val;
    int freq;
    Node(int _key, int _val, int _freq) : key(_key), val(_val), freq(_freq) {}
};
 
class LFUCache {
private:
    int capacity;
    int minfreq;
    unordered_map<int, list<Node>> freq_table;
    unordered_map<int, list<Node>::iterator> key_table;
 
public:
    LFUCache(int _capacity) {
        minfreq = 0;
        capacity = _capacity;
        key_table.clear();
        freq_table.clear();
    }
    
    int get(int key) {
        // 啥也没有
        if (capacity == 0) {
            return -1; 
        }
 
        // 没有这个key
        if (!key_table.count(key)) {
            return -1;
        }
 
        auto iter = key_table[key];
        int val  = iter->val;
        int freq = iter->freq;
 
        //查到删除旧的，增加新的
        freq_table[freq].erase(iter);
        //中间要判断一下此freq的链表是不是空了
        if (freq_table[freq].size() == 0) {
            //删除
            freq_table.erase(freq);
            //更新 minfreq
            if(minfreq == freq) minfreq += 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; 
        }
 
        // 没有的话，加进去
        if (!key_table.count(key))
        {
            // 存储key的数量满了
            if (key_table.size() == capacity) 
            {
                // 删掉频率最小的最早使用的
                auto node = freq_table[minfreq].back();
                int k = node.key;
                key_table.erase(k);
                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; //注意这里要更新minfreq,容易出现错误
 
        } else {//存在
            // 更新
            // 先删，后频率增加，插入
            auto node = key_table[key];
            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();
        }
 
    }
};
/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

FIFO 缓存

先进先出，明显使用哈希+队列

#include <iostream>
#include <queue>
#include <unordered_map>
 
class FIFOCache {
private:
    std::queue<int> fifoQueue; // 存放key
    std::unordered_map<int, int> cache; // 存放key-value
    int capacity;
 
public:
    FIFOCache(int capacity) : capacity(capacity) {}
 
    int get(int key) {
        if (cache.find(key) != cache.end()) {
            return cache[key];
        }
        return -1;
    }
 
    void put(int key, int value) {
        if (cache.size() >= capacity) {
            int keyToRemove = fifoQueue.front();
            fifoQueue.pop();
            cache.erase(keyToRemove);
        }
 
        cache[key] = value;
        fifoQueue.push(key);
    }
};
 
int main() {
    FIFOCache cache(2);
 
    cache.put(1, 1);
    cache.put(2, 2);
    std::cout << cache.get(1) << std::endl; // 输出：1
    cache.put(3, 3);
    std::cout << cache.get(2) << std::endl; // 输出：-1，因为元素2被淘汰了
 
    return 0;
}