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

LRU Cache 简介

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

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

• 如果数据已经在缓存中，将其提升为“最近使用”；
• 如果数据不在缓存中，则将其插入缓存中；
• 如果缓存已满，会淘汰最久未使用的数据。

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

实现思路解析

LRU Cache 的核心需求有两个：

• 快速访问数据： O(1) 时间复杂度。
• 快速更新访问顺序： 当某个数据被访问时，需要将其提升为最近使用的数据。

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

• 哈希表（HashMap）： 提供 O(1) 时间复杂度的数据查找。
• 双向链表： 提供 O(1) 时间复杂度的插入、删除操作，保证缓存顺序的维护。

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

手写 LRU Cache 代码（Java 实现）

好了，废话不多说，直接上代码吧！下面我会用 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 算法的核心思想，并能应用到实际开发中。