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

简介: 嗨,大家好!我是你们的技术小伙伴——小米。今天带大家深入了解并手写一个实用的LRU Cache(最近最少使用缓存)。LRU Cache是一种高效的数据淘汰策略,在内存有限的情况下特别有用。本文将从原理讲起,带你一步步用Java实现一个简单的LRU Cache,并探讨其在真实场景中的应用与优化方案,如线程安全、缓存持久化等。无论你是初学者还是有一定经验的开发者,都能从中受益。让我们一起动手,探索LRU Cache的魅力吧!别忘了点赞、转发和收藏哦~



嘿,大家好,我是你们的技术分享小伙伴——小米!今天给大家带来一个超级实用的算法实现——手写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,值为对应的链表节点;
  • 初始化双向链表的 headtail 哨兵节点,方便管理节点的插入与删除。
  • get 方法:
  • HashMap 中查找是否存在该 key
  • 如果存在,调用 moveToHead 方法将该节点移动到链表头部;
  • 如果不存在,返回 null 表示缓存未命中。
  • put 方法:
  • 如果该 key 已经存在于缓存中,更新其值并将其移动到链表头部;
  • 如果该 key 不存在,创建一个新节点,并将其加入链表头部;
  • 如果缓存已满,移除链表尾部的节点(即最久未使用的节点),并从 HashMap 中删除该节点。
  • moveToHead 方法:
  • 先从链表中移除该节点,再将其插入到链表头部,标记为最近使用的节点。
  • removeTail 方法:
  • 直接移除链表的尾部节点,并返回该节点。尾部节点即是最久未使用的节点。

扩展与优化

  • 线程安全:目前这个 LRU Cache 版本是非线程安全的。如果你的应用场景涉及多线程环境,可以考虑在 getput 方法上加锁,或者使用 ConcurrentHashMap 来替代 HashMap,配合 ReentrantLock 保证线程安全。
  • 缓存持久化:在某些应用场景下,你可能需要缓存的持久化存储。可以将 LRUCache 结合 Redis、文件系统等,实现持久化缓存,防止缓存数据丢失。
  • 缓存容量动态调整:可以扩展 LRUCache 的功能,使其支持动态调整缓存容量,方便应对不同的场景需求。

总结

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

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

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

小米的小Tips

  • LRU Cache 是面试中的经典问题,不仅考察算法能力,还考察数据结构的运用。
  • 平时多动手写一写,有助于更好地掌握知识点!

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

我是小米,一个喜欢分享技术的29岁程序员。如果你喜欢我的文章,欢迎关注我的微信公众号软件求生,获取更多技术干货!

相关文章
|
9天前
|
存储 缓存 监控
HTTP:强缓存优化实践
HTTP强缓存是提升网站性能的关键技术之一。通过精心设计缓存策略,不仅可以显著减少网络延迟,还能降低服务器负载,提升用户体验。实施上述最佳实践,结合持续的监控与调整,能够确保缓存机制高效且稳定地服务于网站性能优化目标。
20 3
|
20天前
|
缓存 监控 负载均衡
在使用CDN时,如何配置缓存规则以优化性能
在使用CDN时,如何配置缓存规则以优化性能
|
1月前
|
缓存 JavaScript 中间件
优化Express.js应用程序性能:缓存策略、请求压缩和路由匹配
在开发Express.js应用时,采用合理的缓存策略、请求压缩及优化路由匹配可大幅提升性能。本文介绍如何利用`express.static`实现缓存、`compression`中间件压缩响应数据,并通过精确匹配、模块化路由及参数化路由提高路由处理效率,从而打造高效应用。
84 5
|
1月前
|
缓存 NoSQL Java
瑞吉外卖项目笔记+踩坑2——缓存、读写分离优化
缓存菜品、套餐数据、mysql主从复制实现读写分离、前后端分离
瑞吉外卖项目笔记+踩坑2——缓存、读写分离优化
|
1月前
|
存储 缓存 前端开发
缓存技术在软件开发中的应用与优化策略
缓存技术在软件开发中的应用与优化策略
|
2月前
|
Java 开发者 JavaScript
Struts 2 开发者的秘籍:隐藏的表单标签库功能,能否成为你下个项目的大杀器?
【8月更文挑战第31天】Struts 2表单标签库是提升Web页面交互体验的神器。它提供丰富的标签,如`<s:textfield>`和`<s:select>`,简化表单元素创建与管理,支持数据验证和动态选项展示。结合示例代码,如创建文本输入框并与Action类属性绑定,显著提升开发效率和用户体验。通过自定义按钮样式等功能,Struts 2表单标签库让开发者更专注于业务逻辑实现。
41 0
|
2月前
|
缓存 NoSQL 数据库
【超实用秘籍】FastAPI高手教你如何通过最佳实践构建高效Web应用:从代码组织到异步编程与缓存优化的全方位指南!
【8月更文挑战第31天】FastAPI凭借出色性能和易用性成为现代Web应用的首选框架。本文通过示例代码介绍构建高效FastAPI应用的最佳实践,包括开发环境搭建、代码模块化组织、异步编程及性能优化等。通过模块化设计和异步数据库操作,结合缓存技术,大幅提升应用性能与可维护性,助您轻松应对高并发场景。
75 0
|
4天前
|
存储 缓存 NoSQL
数据的存储--Redis缓存存储(一)
数据的存储--Redis缓存存储(一)
28 1
|
4天前
|
存储 缓存 NoSQL
数据的存储--Redis缓存存储(二)
数据的存储--Redis缓存存储(二)
16 2
数据的存储--Redis缓存存储(二)
|
5天前
|
缓存 NoSQL 关系型数据库
redis和缓存及相关问题和解决办法 什么是缓存预热、缓存穿透、缓存雪崩、缓存击穿
本文深入探讨了Redis缓存的相关知识,包括缓存的概念、使用场景、可能出现的问题(缓存预热、缓存穿透、缓存雪崩、缓存击穿)及其解决方案。
21 0
redis和缓存及相关问题和解决办法 什么是缓存预热、缓存穿透、缓存雪崩、缓存击穿