LRU（Least Recently Used）原理及算法实现

1.前言        

        LRU（Least Recently Used，最近最少使用） 是一种经典的 缓存淘汰算法，用于在缓存空间不足时决定哪些数据应被移除。其核心思想是：优先淘汰最长时间未被访问的数据，保留最近被访问的数据。

        这里制定的规则是最近最少使用，如果等效为优先级最高，那么其实和RTOS任务切换的最高优先级任务选择的场景是几乎相同的。当然，RTOS中使用了双向链表维护就绪态任务列表数组，并按优先级进行了排序。

2.实现方式   

        LRU 缓存的核心规则是：
①当访问（get）或插入（put）数据时，将该数据标记为 “最近使用”。
②当缓存满时，新插入数据会淘汰 “最久未被使用” 的数据。

        要实现这一规则，需要高效支持两个操作：
①快速查找数据（判断是否存在）。
②快速移动或删除数据（更新 “最近使用” 状态）。

1. 双向链表 + 哈希表（O(1)复杂度）

         如上图所示，通过哈希映射来快速定位节点位置，双向链表用于维护节点信息，越接近链表尾部的节点最近使用最少。相关实现涉及的操作如下：

• 访问数据：将节点移到链表头部；

• 淘汰数据：删除链表尾部节点；

• 新增数据：插入链表头部；

2. 代码实现

class LRUCache 
{
private:list<pair<int, int>> cache; // 双向链表：key-valueunordered_map<int, list<pair<int, int>>::iterator> map; // key->链表节点指针int capacity;  //缓存的最大容量，超过此容量时需要淘汰数据。public:LRUCache(int cap) : capacity(cap) {}//根据key查找缓存中的值，若存在则返回值，并将该数据标记为 “最近使用”；若不存在则返回-1。int get(int key){if(map.find(key) == map.end()) {            return -1;  //若不存在，返回-1。}         cache.splice(cache.begin(), cache, map[key]);   //移至链表头部（标记最近使用）       return map[key]->second;     //返回该节点的value}//插入新的key-value，或更新已有key的值，并将其标记为 “最近使用”；若缓存满，则淘汰最久未使用的数据。void put(int key, int value) {        if(map.find(key) != map.end())  //若key已存在{            map[key]->second = value;   //更新值            cache.splice(cache.begin(), cache, map[key]);   //用splice将节点移到链表头部return;}if(cache.size() == capacity) // 缓存满，淘汰尾部{auto last = cache.back();map.erase(last.first); // 从哈希表删除该节点的keycache.pop_back();     // 从链表删除尾部节点}// 新数据插入头部cache.emplace_front(key, value);map[key] = cache.begin();}
};

 3.汽车 ADAS 系统的传感器缓存

        在资源有限的嵌入式系统中，优先保留最近使用的传感器数据（如刹车温度），可快速响应紧急事件。

#define CACHE_SIZE 10
typedef struct {int sensor_id;float data;uint32_t last_access;bool valid;  // 增加有效性标志位
} SensorCache;SensorCache cache[CACHE_SIZE] = {0}; // 初始化全为invalid// 时间戳获取函数（1us分辨率）
uint32_t get_timestamp() 
{return DWT->CYCCNT / (SystemCoreClock / 1000000); 
}void update_cache(int id, float value) 
{int empty_slot = -1;       // 记录可用空槽int lru_index = -1;        // 真实LRU槽位uint32_t oldest = 0xFFFFFFFF;// 第一遍扫描：查找匹配和空槽for(int i=0; i<CACHE_SIZE; i++) {// 情况1：找到匹配传感器if(cache[i].valid && cache[i].sensor_id == id) {cache[i].data = value;cache[i].last_access = get_timestamp();return; // 直接返回}// 情况2：记录空槽位置if(!cache[i].valid) {empty_slot = i; // 不break，继续找可能的匹配项}}// 第二遍扫描：仅当无空槽时寻找真实LRUif(empty_slot == -1) {for(int i=0; i<CACHE_SIZE; i++) {if(cache[i].valid && cache[i].last_access < oldest) {oldest = cache[i].last_access;lru_index = i;}}} else {lru_index = empty_slot; // 优先使用空槽}// 更新缓存cache[lru_index].sensor_id = id;cache[lru_index].data = value;cache[lru_index].last_access = get_timestamp();cache[lru_index].valid = true; // 标记有效
}