嘿,大家好,我是你们的技术分享小伙伴——小米!今天给大家带来一个超级实用的算法实现——手写LRU Cache。大家在日常开发中,可能经常会遇到需要缓存的场景,而LRU(Least Recently Used)Cache 是一种非常高效的缓存淘汰策略。这篇文章将从理论讲解到代码实现,手把手教你写一个简单的 LRU Cache!
目录
- LRU Cache 简介
- 实现思路解析
- 手写 LRU Cache 代码(Java 实现)
- 代码讲解与分析
- 扩展与优化
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 算法的核心思想,并能应用到实际开发中。
如果大家有任何疑问或者希望我讲解其他技术点,欢迎留言交流哦!我们下期再见啦~
点赞、转发、收藏一波,支持小米继续写作~
小米的小Tips
- LRU Cache 是面试中的经典问题,不仅考察算法能力,还考察数据结构的运用。
- 平时多动手写一写,有助于更好地掌握知识点!
期待大家的反馈和建议,我会根据大家的需求推出更多有趣的技术文章!
我是小米,一个喜欢分享技术的29岁程序员。如果你喜欢我的文章,欢迎关注我的微信公众号“软件求生”,获取更多技术干货!