嘿,大家好,我是你们的技术分享小伙伴——小米!今天给大家带来一个超级实用的算法实现——手写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 算法的核心思想,并能应用到实际开发中。
如果大家有任何疑问或者希望我讲解其他技术点,欢迎留言交流哦!我们下期再见啦~
点赞、转发、收藏一波,支持小米继续写作~
小米的小TipsLRU Cache 是面试中的经典问题,不仅考察算法能力,还考察数据结构的运用。
平时多动手写一写,有助于更好地掌握知识点!
期待大家的反馈和建议,我会根据大家的需求推出更多有趣的技术文章!