当前位置：首页 > news >正文

LRU缓存机制完全实战：链表的工程落地与面试通关

news 2025/7/13 10:11:23

📖 推荐阅读：《Yocto项目实战教程:高效定制嵌入式Linux系统》
🎥 更多学习视频请关注 B 站：嵌入式Jerry

LRU缓存机制完全实战：链表的工程落地与面试通关

前言

“链表会了，真能写好LRU吗？”——LRU缓存机制是算法和工程面试的超高频考题，也是链表+哈希表综合应用的经典场景。本文以实战为主，手把手讲透核心实现思路与关键技巧，让你从“会链表”迈向“能设计高效缓存”。

一、什么是LRU缓存机制？

LRU（Least Recently Used）意为“最近最少使用”。在限定容量的缓存中，每次数据被访问，都认为它“最新”；容量满时，要踢掉最久没用的数据。
在这里插入图片描述

典型需求

**get(key)：**查找key的值，若命中，则成为最新（移动到队头）。
**put(key, value)：**写入key，若容量超，踢掉最旧的key。

要求：

get 和 put 操作都要 O(1) 完成！

二、为何必须用链表+哈希表？

哈希表：O(1)查找节点。
双向链表：O(1)插入/删除/移动节点，随时把任意节点挪到表头或表尾。

这两个结构组合起来，完美满足 LRU 所有需求，是工程界公认的标准方案！

三、实战代码：手写LRU缓存机制（C++完整版）

1. 设计思路图

哈希表 key -> 双向链表节点
双向链表：head <-> node1 <-> node2 <-> ... <-> nodeN <-> tail
- 最新的节点在 head 后面
- 最旧的节点在 tail 前面

2. 双向链表节点定义

struct Node {int key, value;Node *prev, *next;Node(int k, int v): key(k), value(v), prev(nullptr), next(nullptr) {}
};

3. 核心成员变量与辅助操作

class LRUCache {
private:unordered_map<int, Node*> cache; // key -> 节点映射int capacity;Node *head, *tail; // 虚拟头尾节点，简化插入/删除逻辑// 把节点从链表中摘除void remove(Node* node) {node->prev->next = node->next;node->next->prev = node->prev;}// 把节点插入到链表头（head后面）void insertToHead(Node* node) {node->next = head->next;node->prev = head;head->next->prev = node;head->next = node;}
public:// 构造函数LRUCache(int cap): capacity(cap) {head = new Node(0,0);tail = new Node(0,0);head->next = tail;tail->prev = head;}

4. 核心操作 get & put 实现

get操作

查找哈希表，若存在：
- 将节点挪到链表头，返回值；
- 否则返回-1。

    int get(int key) {if (cache.count(key)) {Node* node = cache[key];remove(node);insertToHead(node); // 访问后变最新return node->value;}return -1; // 不存在}

put操作

key已存在：更新值，并挪到链表头；
key不存在：
- 如已满，则删掉最旧节点（链表尾部）。
- 新建节点插入到头，并加入哈希表。

    void put(int key, int value) {if (cache.count(key)) {Node* node = cache[key];node->value = value;remove(node);insertToHead(node);} else {if (cache.size() == capacity) {Node* last = tail->prev;remove(last);cache.erase(last->key);delete last;}Node* node = new Node(key, value);cache[key] = node;insertToHead(node);}}
};