详解LRU缓存算法[通俗易懂]

详解LRU缓存算法

大家好,又见面了,我是全栈君。

一、什么是缓存

这里说的缓存是一种广义的概念,在计算机存储层次结构中,低一层的存储器都可以看做是高一层的缓存。比如Cache是内存的缓存,内存是硬盘的缓存,硬盘是网络的缓存等等。

缓存可以有效地解决存储器性能与容量的这对矛盾,但绝非看上去那么简单。如果缓存算法设计不当,非但不能提高访问速度,反而会使系统变得更慢。

从本质上来说,缓存之所以有效是因为程序和数据的局部性(locality)。程序会按固定的顺序执行,数据会存放在连续的内存空间并反复读写。这些特点使得我们可以缓存那些经常用到的数据,从而提高读写速度。

缓存的大小是固定的,它应该只保存最常被访问的那些数据。然而未来不可预知,我们只能从过去的访问序列做预测,于是就有了各种各样的缓存替换策略。本文介绍一种简单的缓存策略,称为最近最少使用(LRU,Least Recently Used)算法。

二、LRU的实现

我们以内存访问为例解释缓存的工作原理。假设缓存的大小固定,初始状态为空。每发生一次读内存操作,首先查找待读取的数据是否存在于缓存中,若是,则缓存命中,返回数据;若否,则缓存未命中,从内存中读取数据,并把该数据添加到缓存中。向缓存添加数据时,如果缓存已满,则需要删除访问时间最早的那条数据,这种更新缓存的方法就叫做LRU。

实现LRU时,我们需要关注它的读性能和写性能,理想的LRU应该可以在O(1)的时间内读取一条数据或更新一条数据,也就是说读写的时间复杂度都是O(1)。

此时很容易想到使用HashMap,根据数据的键访问数据可以达到O(1)的速度。但是更新缓存的速度却无法达到O(1),因为需要确定哪一条数据的访问时间最早,这需要遍历所有缓存才能找到。

因此,我们需要一种既按访问时间排序,又能在常数时间内随机访问的数据结构。

这可以通过HashMap+双向链表实现。HashMap保证通过key访问数据的时间为O(1),双向链表则按照访问时间的顺序依次穿过每个数据。之所以选择双向链表而不是单链表,是为了可以从中间任意结点修改链表结构,而不必从头结点开始遍历。

如下图所示,黑色部分为HashMap的结构,红色箭头则是双向链表的正向连接(逆向连接未画出)。可以清晰地看到,数据的访问顺序是1->3->5->6->10。我们只需要在每次访问过后改变链表的连接顺序即可。

详解LRU缓存算法[通俗易懂]

HashMap+双向链表

实现代码如下:

详解LRU缓存算法[通俗易懂]

详解LRU缓存算法[通俗易懂]

详解LRU缓存算法[通俗易懂]

详解LRU缓存算法[通俗易懂]

详解LRU缓存算法[通俗易懂]

每个方法和成员变量前都有中文注释,不必过多解释。

值得一提的是,Java API中其实已经有数据类型提供了我们需要的功能,就是LinkedHashMap这个类。该类内部也是采用HashMap+双向链表实现的。使用这个类实现LRU就简练多了。

详解LRU缓存算法[通俗易懂]

详解LRU缓存算法[通俗易懂]

只需要覆写LinkedHashMap的removeEldestEntry方法,在缓存已满的情况下返回true,内部就会自动删除最老的元素。

感兴趣的同学可以做一下LeetCode 146. LRU Cache这道题,尝试一下如何实现这个算法。

详解LRU缓存算法[通俗易懂]

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/111943.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 戴尔服务器的远程开机和关机

    戴尔服务器的远程开机和关机手上有一台戴尔的DELLPowerEdgeR210服务器,闲来无事,研究了一下它的远程开机和关机。Dell的服务器默认都带BMC,这个用来做管理的网口和操作系统是共用的同一个网口(注意必需是第一个网口,即服务器上标有1的那个),只要BMC里设置的IP地址和操作系统的IP不一样就可以了。BMC的设置很简单,按以下步骤进行设置:1、在服务器启动时看到Press<Ct…

  • Java Calendar获取年、月、日、时间[通俗易懂]

    Java Calendar获取年、月、日、时间[通俗易懂]Calendarc=Calendar.getInstance(TimeZone.getTimeZone(“GMT+08:00”));//获取东八区时间intyear=c.get(Calendar.YEAR);//获取年intmonth=c.get(Calendar.MONTH)+1;//获取月份,0表示1月份intday=c.get(Calend…

  • BNUOJ34973Liserious战队

    BNUOJ34973Liserious战队

    2021年12月15日
  • 重复字符串 leetcode_字符串中出现最多的子串 leetcode

    重复字符串 leetcode_字符串中出现最多的子串 leetcode原题链接给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入: s = “abcabcbb”输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。示例 2:输入: s = “bbbbb”输出: 1解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。示例 3:输入: s = “pwwkew”输出: 3解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。 请注意,你的答案必须是 子串 的长度,”pwk

  • 视频试看5分钟[通俗易懂]

    缺陷:用户在控制台能直接拿到视频url地址<!DOCTYPEhtml><html><head><title></title></head><styletype=”text/css”>.videobox{position:relative;width:300px;…

  • QT之Android下获取手机传感器数据学习笔记

    QT之Android下获取手机传感器数据学习笔记QT+=coreguisensorspositioning其中sensors是获取手机上传感器数据的组件,positioning是获取位置信息的组件1、获取陀螺仪传感器数据#include&lt;QGyroscope&gt;QGyroscope*gyroscope;QGyroscopeReading*reader;gyroscope=newQGyro…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号