详解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)
blank

相关推荐

发表回复

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

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