缓存优化利器:5分钟实现LRUCache,从原理到代码!

软件求生 2024-08-24 09:37:34



嘿,大家好,我是你们的技术分享小伙伴——小米!今天给大家带来一个超级实用的算法实现——手写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 是面试中的经典问题,不仅考察算法能力,还考察数据结构的运用。

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

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

0 阅读:13

软件求生

简介:从事软件开发,分享“技术”、“运营”、“产品”等。