缓存算法是一种用于管理计算机系统中缓存数据的策略和方法，其目的是在有限的缓存空间内，通过合理地存储和替换数据，尽可能提高缓存的命中率，从而减少对慢速存储设备（如硬盘）的访问，提高系统的性能和响应速度。常见的缓存算法有：
- 先进先出（FIFO）算法
- 最近最少使用（LRU）算法
- 最不经常使用（LFU）算法
- 随机替换（Random）算法
FIFO算法
FIFO 算法是一种基于队列数据结构的算法思想，FIFO的思想比较简单，FIFO认为先进入缓存的数据应该被先替换出去。
原理
FIFO 算法的工作原理是当缓存已满，需要替换数据时，选择最早进入缓存的那个数据进行替换，它不考虑数据的使用频率、访问模式等其他因素，只是简单地按照数据进入缓存的先后顺序来操作。
代码实现
这里我们设计一个满足 FIFO 约束的数据结构。
FIFOCache 类：
- FIFOCache(int capacity)：以 正整数 作为容量 capacity 初始化缓存
- int get(int key)：如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
- void put(int key, int value)：如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出最先进入缓存的关键字。
函数 get 和 put 都以O(1)的平均时间复杂度运行。
我们使用 unordered_map 存储键值对，实现键值对增删改查均为O(1)时间复杂度。同时我们使用一个队列 queue 维护元素的插入顺序，缓存满时，队首就是待逐出的元素。
class FIFOCache
{
private:int capacity;std::queue<int> fifoQueue;std::unordered_map<int, int> cacheMap;public:// 构造函数，初始化缓存容量FIFOCache(int capacity) : capacity(capacity) {}// 获取关键字的值int get(int key) {// 检查关键字是否存在于缓存中if (cacheMap.find(key) != cacheMap.end()) {return cacheMap[key];}return -1;}// 插入或更新关键字的值void put(int key, int value) {// 检查关键字是否已经存在if (cacheMap.find(key) != cacheMap.end()) {// 如果存在，更新其值cacheMap[key] = value;} else {// 如果不存在，插入新的键值对cacheMap[key] = value;fifoQueue.push(key);// 检查是否超过容量if (cacheMap.size() > capacity) {// 逐出最久未使用的关键字int oldestKey = fifoQueue.front();fifoQueue.pop();cacheMap.erase(oldestKey);}}}
};LRU算法
LRU算法即最近最少使用算法，是一种常见的页面置换算法和缓存淘汰策略。
原理
LRU 算法的核心思想是，如果数据最近被访问过，那么将来被访问的概率也会更高；相反，长时间没有被访问的数据，在未来一段时间内被访问的可能性相对较低。因此，当需要淘汰数据以腾出空间时，优先选择淘汰最长时间未被使用的数据。
代码实现
这里我们设计一个满足 LRU 约束的数据结构。
LRUCache 类：
- LRUCache(int capacity)：以 正整数 作为容量 capacity 初始化缓存
- int get(int key)：如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
- void put(int key, int value)：如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出最久未使用的关键字。
函数 get 和 put 都以O(1)的平均时间复杂度运行。
想象一下这里有一摞书：
我们维护一个双向链表作为书堆，使用 unorder_map 存储键与链表迭代器的映射关系：
class LRUCache {
public:list<pair<int,int>> _list;unordered_map<int,std::list<pair<int,int>>::iterator> _map;int _capacity;int _size;LRUCache(int capacity) :_capacity(capacity),_size(0){}void move_front(auto it){int key=it->second->first;int value=it->second->second;_list.erase(it->second);_list.push_front({key,value});_map[key]=_list.begin();}int get(int key) {auto it=_map.find(key);if(it==_map.end()){return -1;}else{int value=it->second->second;move_front(it);return value;}}void put(int key, int value) {auto it=_map.find(key);//已存在if(it!=_map.end()){it->second->second=value;move_front(it);}//未存在else{//满了if(_size==_capacity){int k=_list.back().first;_list.pop_back();_map.erase(k);_size--;}_list.push_front({key,value});_map[key]=_list.begin();_size++;}}
};
LFU算法
LFU算法即最不经常使用页面置换算法，常用在虚拟存储管理页面置换算法。
原理
LFU 算法基于一个简单的假设，如果一个数据在过去被访问的频率很低，那么在未来它被访问的可能性也相对较低。该算法为数据项维护一个访问频率计数器，每当一个数据被访问时，其访问频率计数器就会增加。当内存空间不足，需要置换数据时，LFU 算法会选择访问频率最低的数据进行置换。如果有多个数据具有相同的最低访问频率，则通常选择最早进入内存的那个数据进行置换。
代码实现
这里我们设计一个满足 LFU 约束的数据结构。
LFUCache 类：
- LFUCache(int capacity)：以 正整数 作为容量 capacity 初始化缓存
- int get(int key)：如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
- void put(int key, int value)：如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出使用频率最小的关键字。
函数 get 和 put 都以O(1)的平均时间复杂度运行。
我们使用一个 unordermap<int,list<Node>> 记录所有书堆，同时使用另一个 unordermap<int,list<Node>::iterator> 记录书的位置。
struct Node
{int key;int value;int freq;Node(int k,int v,int f):key(k),value(v),freq(f){}
};class LFUCache
{
public:int _capacity,_minfreq;unordered_map<int,std::list<Node>> _kv;unordered_map<int,std::list<Node>::iterator> _kit;LFUCache(int capacity) :_capacity(capacity),_minfreq(0){ }int get(int key) {auto it=_kit.find(key);if(it==_kit.end()){return -1;} auto node=it->second;int val=node->value;int freq=node->freq;_kv[freq].erase(node);if(_kv[freq].empty()){_kv.erase(freq);if(_minfreq==freq) _minfreq++;}_kv[freq+1].push_front(Node(key,val,freq+1));_kit[key]=_kv[freq+1].begin();return val;}void put(int key, int value) {int size=_kit.size();auto it=_kit.find(key);if(it!=_kit.end()){auto node=it->second;node->value=value;int freq=node->freq;_kv[freq].erase(node);if(_kv[freq].empty()){_kv.erase(freq);if(_minfreq==freq) _minfreq++;}_kv[freq+1].push_front(Node(key,value,freq+1));_kit[key]=_kv[freq+1].begin();}else{//删除if(size==_capacity){auto node=_kv[_minfreq].back();_kit.erase(node.key);_kv[_minfreq].pop_back();if(_kv[_minfreq].empty())_kv.erase(_minfreq);}_kv[1].push_front(Node(key,value,1));_kit[key]=_kv[1].begin();_minfreq=1;}}
};
Random算法
Random算法是一种在计算机科学和数据处理等领域广泛应用的简单算法。
原理
随机替换算法的核心原理是在需要进行替换操作时，从给定的候选集合中随机选择一个元素来进行替换。它不考虑元素的任何特定属性或顺序，完全基于随机原则进行选择。例如，在缓存管理中，当缓存已满需要替换一个缓存块时，随机替换算法会从所有缓存块中随机挑选一个进行替换。
代码实现
因为实现非常简单，这里就不给出实现代码了，大家可以自行实现。
