在竞争激烈的技术求职市场中，百度、字节等大厂的面试以高标准著称，LRU 缓存算法是面试常客，在算法类面试题中出现概率名列前茅，足见其重要性。大厂青睐 LRU 缓存算法，原因有二。

其一，它是计算机科学领域经典的缓存淘汰策略，广泛应用于操作系统、数据库、浏览器等场景。理解和实现该算法，能直接反映候选人对数据结构、算法设计及时间复杂度分析等基础知识的掌握程度。

其二，它能考察候选人的问题解决能力和编程思维。实际工作中，工程师常遇性能优化和资源管理问题，LRU 缓存算法涉及的高效维护数据访问顺序、有限资源下合理淘汰等思想方法，与实际工作场景紧密相关。熟练解决此类问题的候选人，在面对复杂工作问题时，往往具备更强的分析和解决能力。

Part1LRU算法核心原理

1.1 LRU概述

LRU，即 Least Recently Used，直译为 “最近最少使用” 。在缓存管理的语境下，LRU 是一种缓存淘汰策略。我们知道，缓存的容量是有限的，就像一个大小固定的容器，当新的数据要存入缓存，而缓存已经满了的时候，就需要决定淘汰掉哪些旧数据，为新数据腾出空间。LRU 算法的核心假设是：如果一个数据在最近一段时间内没有被访问过，那么在未来它被访问的可能性也较低。因此，当缓存空间不足时，LRU 算法会优先淘汰最近最少被使用的数据。

为了更好地理解 LRU，我们可以用整理书架的场景来类比。假设你的书架空间有限，只能摆放一定数量的书籍。随着你不断购买新书，书架逐渐被填满。这时，如果你又买了一本新书，就需要清理掉一些旧书来给新书腾地方。你会怎么选择呢？通常，你会优先清理掉那些你已经很久没有翻阅过的书籍，因为你近期再次阅读它们的可能性相对较小。而那些你经常翻阅的书籍，你会更倾向于保留在书架上，方便随时取用。这里，书架就相当于缓存，书籍相当于缓存中的数据，而 LRU 算法就像是你决定清理哪些旧书的策略。

1.2工作机制剖析

LRU 算法的工作机制主要围绕着两个关键操作：数据访问和缓存淘汰。当缓存中的数据被访问时，LRU 算法会将该数据标记为最近使用，通常的做法是将其移动到一个记录访问顺序的数据结构的头部（假设头部表示最近使用）。这样，随着时间的推移，那些最近没有被访问的数据会逐渐移动到数据结构的尾部（假设尾部表示最久未使用）。

当缓存已满，需要插入新数据时，LRU 算法会直接淘汰掉位于数据结构尾部的数据，因为它是最近最少被使用的。例如，假设我们有一个容量为 3 的 LRU 缓存，初始时缓存为空 。依次访问数据 A、B、C，此时缓存中存储的数据为 [A, B, C]（假设顺序从最久未使用到最近使用）。当再次访问数据 A 时，根据 LRU 算法，A 会被移动到最近使用的位置，缓存中的数据变为 [B, C, A]。接下来，如果要插入新数据 D，由于缓存已满，位于最久未使用位置的 B 就会被淘汰，缓存中的数据变为 [C, A, D]。

再比如，在一个网页浏览器的缓存中，LRU 算法用于管理缓存的网页资源。当用户浏览网页时，浏览器会将网页的 HTML、CSS、图片等资源缓存起来。如果用户再次访问相同或相关页面时，若资源在缓存中，浏览器可直接从缓存读取，减少网络请求，加快页面加载速度。随着用户浏览的网页增多，缓存空间会逐渐被占满。此时，LRU 算法会将最近最少访问的网页资源淘汰，确保缓存中始终保留最有可能再次被访问的内容。比如，用户之前浏览过多个新闻页面，一段时间后又频繁访问购物网站，那么那些较早浏览且长时间未再次访问的新闻页面缓存资源就可能被 LRU 算法淘汰，为购物网站的缓存资源腾出空间。

Part2用C++实现LRU缓存算法

2.1所需数据结构

实现 LRU 缓存算法，主要用到双向链表和哈希表这两种数据结构。双向链表在 LRU 缓存算法中扮演着维护数据访问顺序的关键角色 。链表中的每个节点代表一个缓存数据，其插入和删除操作的时间复杂度均为 O (1)，这使得在频繁进行缓存操作时，能够快速地对链表进行调整。链表的头部表示最近最少使用的数据，而尾部表示最近使用的数据。例如，当有新数据被访问时，对应的节点会被移动到链表尾部，表明它是最新被使用的；当缓存已满需要淘汰数据时，直接删除链表头部的节点即可。

哈希表则用于快速定位数据在双向链表中的位置 。它以数据的键作为索引，存储对应数据在双向链表中的节点指针。通过哈希表，我们可以在 O (1) 的时间复杂度内找到对应的数据节点，然后根据节点指针在双向链表中进行操作。比如，在查找某个键对应的数据时，通过哈希表可以迅速定位到该数据在双向链表中的位置，避免了在链表中逐个遍历查找，大大提高了查找效率。

将双向链表和哈希表结合起来，就可以高效地实现 LRU 缓存算法 。哈希表提供了快速查找数据的能力，双向链表则保证了数据的访问顺序能够被有效维护，二者相辅相成，使得 LRU 缓存算法的各项操作都能在较低的时间复杂度内完成。

2.2C++代码逐行解读

下面是完整的 C++ 实现 LRU 缓存算法的代码：

#include <iostream>
#include <list>
#include <unordered_map>

using namespace std;

class LRUCache {
private:
    // 定义双向链表节点结构
    struct Node {
        int key;
        int value;
        Node(int k, int v) : key(k), value(v) {}
    };

    // 双向链表，用于维护数据的访问顺序
    list<Node> cacheList; 
    // 哈希表，用于快速定位数据在双向链表中的位置
    unordered_map<int, list<Node>::iterator> cacheMap; 
    int capacity; // 缓存容量

public:
    // 构造函数，初始化缓存容量
    LRUCache(int cap) : capacity(cap) {} 

    // 获取操作
    int get(int key) {
        // 如果键不在哈希表中，说明数据不在缓存中，返回 -1
        if (cacheMap.find(key) == cacheMap.end()) { 
            return -1;
        }
        // 将访问的数据移动到双向链表的尾部（表示最近使用）
        moveToTail(cacheMap[key]); 
        // 返回对应的值
        return cacheMap[key]->value; 
    }

    // 插入操作
    void put(int key, int value) {
        // 如果键已存在，更新其值并将其移动到双向链表的尾部
        if (cacheMap.find(key) != cacheMap.end()) { 
            cacheMap[key]->value = value;
            moveToTail(cacheMap[key]);
            return;
        }

        // 如果缓存已满，删除双向链表头部的节点（最近最少使用）
        if (cacheList.size() == capacity) { 
            cacheMap.erase(cacheList.front().key);
            cacheList.pop_front();
        }

        // 将新节点插入到双向链表的尾部，并更新哈希表
        cacheList.emplace_back(key, value); 
        cacheMap[key] = --cacheList.end();
    }

private:
    // 将指定节点移动到双向链表的尾部
    void moveToTail(list<Node>::iterator it) { 
        Node node = *it;
        cacheList.erase(it);
        cacheList.emplace_back(node);
        cacheMap[node.key] = --cacheList.end();
    }
};

下面按函数功能对代码进行逐行解释：

• 构造函数：LRUCache (int cap)，用于初始化 LRU 缓存的容量。它接受一个参数 cap，表示缓存的最大容量，并将其赋值给成员变量 capacity。同时，它初始化了双向链表 cacheList 和哈希表 cacheMap，为后续的缓存操作做好准备。

• get 函数：int get (int key)，用于获取指定键对应的值。首先，它通过哈希表 cacheMap 查找键 key 是否存在。如果不存在，说明数据不在缓存中，直接返回 - 1。如果存在，通过 moveToTail 函数将对应的数据节点移动到双向链表的尾部，表示该数据是最近使用的，然后返回对应的值。

• put 函数：void put (int key, int value)，用于插入或更新键值对。首先检查键 key 是否已经存在于哈希表中。如果存在，更新对应节点的值，并将其移动到双向链表的尾部。如果不存在，判断缓存是否已满。若已满，删除双向链表头部的节点（即最近最少使用的数据），并从哈希表中移除对应的键值对。然后，在双向链表的尾部插入新的节点，并在哈希表中记录键 key 和对应节点的迭代器。

• moveToTail 函数：void moveToTail(list::iterator it)，这是一个私有函数，用于将指定的节点移动到双向链表的尾部。它首先保存当前节点的值，然后从链表中删除该节点，再将保存的节点插入到链表的尾部，并更新哈希表中该节点的迭代器。

2.3复杂度分析

在 LRU 缓存算法中，get 和 put 操作的时间复杂度均为 O (1) 。这得益于双向链表和哈希表的巧妙结合。在 get 操作中，通过哈希表可以在 O (1) 的时间内快速判断键是否存在于缓存中，并获取对应的数据节点在双向链表中的位置。然后，将该节点移动到双向链表的尾部，由于双向链表的插入和删除操作时间复杂度也是 O (1)，所以整个 get 操作的时间复杂度为 O (1)。

对于 put 操作，如果键已存在，同样可以通过哈希表在 O (1) 时间内找到对应节点，更新其值并移动到双向链表尾部，时间复杂度为 O (1)。若键不存在，在插入新节点时，虽然可能需要删除双向链表头部的节点，但删除操作时间复杂度为 O (1)，插入新节点到链表尾部以及更新哈希表的操作时间复杂度也均为 O (1)，所以整体 put 操作的时间复杂度仍为 O (1)。这种高效的时间复杂度使得 LRU 缓存算法在实际应用中能够快速响应用户的请求，提高系统性能 。

在空间复杂度方面，LRU 缓存算法主要取决于哈希表和双向链表所占用的空间。哈希表存储了缓存中所有数据的键值对映射，双向链表存储了缓存中的数据节点，因此空间复杂度为 O (capacity)，其中 capacity 是缓存的容量。这意味着随着缓存容量的增加，算法所占用的内存空间也会相应线性增长。

Part3实战演练与案例分析

3.1测试代码展示

为了验证 LRU 缓存算法的正确性，我们编写如下测试代码：

int main() {
    LRUCache cache(2); // 创建容量为2的LRU缓存

    cache.put(1, 100); // 插入键值对 (1, 100)
    cache.put(2, 200); // 插入键值对 (2, 200)

    // 测试 get 操作
    cout << "Get key 1: " << cache.get(1) << endl; // 输出: Get key 1: 100
    cout << "Get key 3: " << cache.get(3) << endl; // 输出: Get key 3: -1

    cache.put(3, 300); // 插入键值对 (3, 300)，此时缓存已满，2将被淘汰
    cout << "Get key 2: " << cache.get(2) << endl; // 输出: Get key 2: -1
    cout << "Get key 3: " << cache.get(3) << endl; // 输出: Get key 3: 300

    cache.put(1, 400); // 更新键1的值
    cout << "Get key 1: " << cache.get(1) << endl; // 输出: Get key 1: 400

    return 0;
}

在上述测试代码中，我们首先创建了一个容量为 2 的 LRU 缓存。然后，进行了一系列的插入（put）和查询（get）操作。从测试结果可以看出，当缓存已满时，新插入的数据会淘汰最近最少使用的数据。并且，对于已存在的键，更新其值后，该键值对会被标记为最近使用 。

3.2实际应用场景

LRU 算法在实际应用中有着广泛的场景，以下是几个典型的例子：

• 操作系统内存管理：在操作系统中，物理内存的空间是有限的。当进程请求内存时，如果内存不足，操作系统需要决定将哪些页面置换出去。LRU 算法被广泛应用于页面置换策略，通过淘汰最近最少使用的页面，为新的页面腾出空间。例如，在 Windows 和 Linux 操作系统中，都采用了类似 LRU 的思想来管理内存页面，有效提高了内存的利用率和系统的整体性能。

• 浏览器缓存优化：浏览器在加载网页时，会将网页的资源（如 HTML、CSS、图片等）缓存到本地。当用户再次访问相同或相关的页面时，浏览器可以直接从缓存中读取资源，减少网络请求，加快页面加载速度。LRU 算法用于管理浏览器的缓存，确保缓存中保留的是用户最近最常访问的网页资源。比如，Chrome 浏览器就利用 LRU 算法来优化缓存管理，提升用户的浏览体验。

• 数据库缓存：数据库系统中，为了减少磁盘 I/O 操作，会将经常访问的数据页缓存到内存中。LRU 算法用于决定哪些数据页应该保留在缓存中，哪些应该被淘汰。例如，MySQL 数据库的 InnoDB 存储引擎就使用了 LRU 算法来管理缓冲池中的数据页，提高了数据库的查询性能。

Part4面试答题技巧与拓展

4.1面试应对策略

当在面试中遇到 LRU 算法题时，不要急于立刻开始写代码 。首先，要冷静地向面试官阐述自己的解题思路，这不仅能让面试官了解你的思考过程，还能帮助你自己理清逻辑。比如，可以先说明使用双向链表和哈希表结合的方案，解释双向链表如何维护数据的访问顺序，哈希表如何实现快速查找。

在写代码过程中，要注意代码的规范性和可读性，适当添加注释，提高代码的清晰度。完成代码后，务必进行时间复杂度分析，向面试官清晰地解释为什么 get 和 put 操作的时间复杂度都是 O (1)，展示你对算法性能的深入理解。同时，也可以提及空间复杂度，表明你在设计算法时对资源利用的考虑 。

4.2算法拓展思考

LRU 算法虽然经典且应用广泛，但在某些场景下，它可能并不是最优选择。例如，在一些访问模式较为特殊的场景中，数据的访问频率可能比访问时间更能反映数据的重要性，这时就需要考虑 LRU 算法的变体，如 LFU（Least Frequently Used，最不经常使用）算法 。LFU 算法根据数据的访问频率来淘汰数据，它认为访问频率低的数据在未来被访问的可能性也较低。与 LRU 算法不同，LFU 算法会记录每个数据的访问次数，当缓存满时，淘汰访问次数最少的数据。

再比如，在一些对缓存命中率要求极高的场景中，可以考虑使用 LRU-K 算法。LRU-K 算法是 LRU 算法的扩展，它通过记录数据的 K 次访问历史，来更准确地判断数据的使用情况。在实际应用中，我们可以根据具体的业务场景和数据访问特点，对 LRU 算法进行改进和优化 。比如，在数据库缓存中，如果能够提前预测数据的访问模式，就可以针对性地调整 LRU 算法的淘汰策略，提高缓存的命中率。

这份完整版的大模型 AI 学习和面试资料已经上传CSDN，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费】

AI大模型学习路线

如果你对AI大模型入门感兴趣，那么你需要的话可以点击这里大模型重磅福利：入门进阶全套104G学习资源包免费分享！

这是一份大模型从零基础到进阶的学习路线大纲全览，小伙伴们记得点个收藏！

第一阶段： 从大模型系统设计入手，讲解大模型的主要方法；

第二阶段： 在通过大模型提示词工程从Prompts角度入手更好发挥模型的作用；

第三阶段： 大模型平台应用开发借助阿里云PAI平台构建电商领域虚拟试衣系统；

第四阶段： 大模型知识库应用开发以LangChain框架为例，构建物流行业咨询智能问答系统；

第五阶段： 大模型微调开发借助以大健康、新零售、新媒体领域构建适合当前领域大模型；

第六阶段： 以SD多模态大模型为主，搭建了文生图小程序案例；

第七阶段： 以大模型平台应用与开发为主，通过星火大模型，文心大模型等成熟大模型构建大模型行业应用。

100套AI大模型商业化落地方案

大模型全套视频教程

200本大模型PDF书籍

👉学会后的收获：👈

• 基于大模型全栈工程实现（前端、后端、产品经理、设计、数据分析等），通过这门课可获得不同能力；

• 能够利用大模型解决相关实际项目需求： 大数据时代，越来越多的企业和机构需要处理海量数据，利用大模型技术可以更好地处理这些数据，提高数据分析和决策的准确性。因此，掌握大模型应用开发技能，可以让程序员更好地应对实际项目需求；

• 基于大模型和企业数据AI应用开发，实现大模型理论、掌握GPU算力、硬件、LangChain开发框架和项目实战技能， 学会Fine-tuning垂直训练大模型（数据准备、数据蒸馏、大模型部署）一站式掌握；

• 能够完成时下热门大模型垂直领域模型训练能力，提高程序员的编码能力： 大模型应用开发需要掌握机器学习算法、深度学习框架等技术，这些技术的掌握可以提高程序员的编码能力和分析能力，让程序员更加熟练地编写高质量的代码。

LLM面试题合集

大模型产品经理资源合集

大模型项目实战合集

👉获取方式：
😝有需要的小伙伴，可以保存图片到wx扫描二v码免费领取【保证100%免费】🆓