嘿，大家好，我是你们的技术分享小伙伴——小米！今天给大家带来一个超级实用的算法实现——手写LRU Cache。大家在日常开发中，可能经常会遇到需要缓存的场景，而LRU（Least Recently Used）Cache 是一种非常高效的缓存淘汰策略。这篇文章将从理论讲解到代码实现，手把手教你写一个简单的 LRU Cache！

LRU Cache 简介

实现思路解析

手写 LRU Cache 代码（Java 实现）

代码讲解与分析

扩展与优化

LRU（Least Recently Used）算法的核心思想是：最近使用的数据将被保留，最久未使用的数据将被淘汰。这种策略适用于内存有限、但又需要高频访问的数据场景，比如缓存系统、页面置换算法等。

简单来说，LRU Cache 会维护一个固定大小的缓存，每次访问数据时：

如果数据已经在缓存中，将其提升为“最近使用”；

如果数据不在缓存中，则将其插入缓存中；

如果缓存已满，会淘汰最久未使用的数据。

这种机制可以有效避免缓存中存放的数据很久没有被使用，从而浪费内存空间。

LRU Cache 的核心需求有两个：

快速访问数据：O(1) 时间复杂度。

快速更新访问顺序：当某个数据被访问时，需要将其提升为最近使用的数据。

要实现以上功能，最直接的想法就是结合哈希表和双向链表：

哈希表（HashMap）：提供 O(1) 时间复杂度的数据查找。

双向链表：提供 O(1) 时间复杂度的插入、删除操作，保证缓存顺序的维护。

双向链表的设计思路是：每次访问或插入数据时，将该数据节点移到链表头部；如果缓存满了，则淘汰链表尾部的节点。

好了，废话不多说，直接上代码吧！下面我会用 Java 来手写一个 LRU Cache。

这个手写的 LRU Cache 实现里，我们使用了双向链表来维护缓存的数据顺序，用 HashMap 来实现 O(1) 时间复杂度的查找。

主要实现逻辑：

构造函数：

初始化一个capacity表示缓存的容量；

使用HashMap存储缓存的数据，键为K，值为对应的链表节点；

初始化双向链表的head和tail哨兵节点，方便管理节点的插入与删除。

get 方法：

从HashMap中查找是否存在该key；

如果存在，调用moveToHead方法将该节点移动到链表头部；

如果不存在，返回null表示缓存未命中。

put 方法：

如果该key已经存在于缓存中，更新其值并将其移动到链表头部；

如果该key不存在，创建一个新节点，并将其加入链表头部；

如果缓存已满，移除链表尾部的节点（即最久未使用的节点），并从HashMap中删除该节点。

moveToHead 方法：

先从链表中移除该节点，再将其插入到链表头部，标记为最近使用的节点。

removeTail 方法：

直接移除链表的尾部节点，并返回该节点。尾部节点即是最久未使用的节点。

线程安全：目前这个 LRU Cache 版本是非线程安全的。如果你的应用场景涉及多线程环境，可以考虑在get和put方法上加锁，或者使用ConcurrentHashMap来替代HashMap，配合ReentrantLock保证线程安全。

缓存持久化：在某些应用场景下，你可能需要缓存的持久化存储。可以将LRUCache结合Redis、文件系统等，实现持久化缓存，防止缓存数据丢失。

缓存容量动态调整：可以扩展LRUCache的功能，使其支持动态调整缓存容量，方便应对不同的场景需求。

今天我们一起动手实现了一个简易版的 LRU Cache，通过双向链表和哈希表的组合，保证了缓存操作的高效性。希望这篇文章能帮助大家更好地理解 LRU 算法的核心思想，并能应用到实际开发中。

如果大家有任何疑问或者希望我讲解其他技术点，欢迎留言交流哦！我们下期再见啦~

点赞、转发、收藏一波，支持小米继续写作~

LRU Cache 是面试中的经典问题，不仅考察算法能力，还考察数据结构的运用。

平时多动手写一写，有助于更好地掌握知识点！

期待大家的反馈和建议，我会根据大家的需求推出更多有趣的技术文章！