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;
}
