常见缓存算法汇总

缓存算法是一种用于管理计算机系统中缓存数据的策略和方法，其目的是在有限的缓存空间内，通过合理地存储和替换数据，尽可能提高缓存的命中率，从而减少对慢速存储设备（如硬盘）的访问，提高系统的性能和响应速度。常见的缓存算法有：

先进先出（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 fifoQueue;

std::unordered_map cacheMap;

public:

// 构造函数，初始化缓存容量

FIFOCache(int capacity) : capacity(capacity) {}

// 获取关键字的值

int get(int key)

{

// 检查关键字是否存在于缓存中

if (cacheMap.find(key) != cacheMap.end