写点什么

从一道 LRU 算法题说到缓存淘汰策略,Java 常用面试集合

用户头像
极客good
关注
发布于: 刚刚

当我看到这段注释的时候,特意去查了一下用 LinkedHashMap 实现 LRU 的方法。


public class LRUCache {


private int cacheSize;


private LinkedHashMap<Integer,Integer> linkedHashMap;


public LRUCache(int capacity) {


this.cacheSize = capacity;


linkedHashMap = new LinkedHashMap<Integer,Integer>(capacity,0.75F,true){


@Override


protected boolean removeEldestEntry(Map.Entry eldest) {


return size()>cacheSize;


}


};


}


public int get(int key) {


return this.linkedHashMap.getOrDefault(key,-1);


}


public void put(int key, int value) {


this.linkedHashMap.put(key,value);


}


}


这是根据这道题的写法,如果不限定这个题目的话,可以让 LRUCache 继承 LinkedHashMap,然后再重写 removeEldestEntry 方法即可。


看到没,就是这么简单,LinkedHashMap 已经完美实现了 LRU,这个方法是在插入键值对的时候调用的,如果返回 true,就删除最近最少使用的元素,所以只要判断 size()是否大于 cacheSize 即可,cacheSize 就是缓存的最大容量。


提交,顺利通过,完美!



LRU


【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


简单实现


===========================================================================


你以为这么简单就完了吗,并没有。当我查看官方题解的时候,发现里面是这么说的。


在 Java 语言中,同样有类似的数据结构 LinkedHashMap。这些做法都不会符合面试官的要求。


什么,这么完美还不符合面试官要求,面试官是什么要求呢?面试官的要求是考考你 LRU 的原理,让你自己实现一个。


那咱们就由 LinkedHashMap 介绍一下最基础的 LRU 实现。简单概括 LinkedHashMap 的实现原理就是 HashMap+双向链表的结合。


双向链表用来维护元素访问顺序,将最近被访问(也就是调动 get 方法)的元素放到链表尾部,一旦超过缓存容量的时候,就从链表头部删除元素,用双向链表能保证元素移动速度最快,假设访问了链表中的某个元素,只要把这个元素移动链表尾部,然后修改这个元素的 prev 和 next 节点的指向即可。


双向链表节点的类型的基本属性如下:


static class Node {


/**


  • 缓存 key


*/


private int key;


/**


  • 缓存值


*/


private int value;


/**


  • 当前节点的前驱节点


*/


private Node prev;


/**


  • 当前节点的后驱节点


*/


private Node next;


public Node(int key, int value) {


this.key = key;


this.value = value;


}


}


HashMap 用来存储 key 值对应的节点,为的是快速定位 key 值在链表中的位置,我们都知道,这是因为 HashMap 的 get 方法的时间复杂度为 O(1)。而如果不借助 HashMap,那这个过程可就慢了。如果要想找一个 key,要从链表头或链表尾遍历才行。



按上图的展示, head 是链表头,也是最长时间未被访问的节点,tail 是最近被访问的元素,假设缓存最大容量是 4 。


插入元素


=======================================================================


当有新元素被插入,先判断缓存容量是否超过最大值了,如果超过,就将头节点删除,然后将头节点的 next 节点设置为 head,同时删除 HashMap 中对应的 key。然后将插入的元素放到链表尾部,设置此元素为尾节,并在 HashMap 中保存下来。


如果没超过最大容量,直接插入到尾部。


访问元素


=======================================================================


当访问其中的某个 key 时,先从 HashMap 中快速找到这个节点。如果这个 key 不是尾节点,那么就将此节的前驱节点的 next 指向此节点的后驱节点,此节点的后驱节点的 prev 指向此节点的前驱节点。同时,将这个节点移动到尾部,并将它设置为尾结点。


下面这个动图,演示了 get key2 时的移动情况。



删除元素


=======================================================================


如果是删除头节点,则将此节点的后驱节点的 prev 设置为 null,并将它设置为 head,同时,删除 HashMap 中此节点的 key。


如果是删除尾节点,则将此节点的前驱节点的 next 设置为 null,并将它设置为 tail,同时,删除 HashMap 中此节点的 key。


如果是中间节点,则将此节的前驱节点的 next 指向此节点的后驱节点,此节点的后驱节点的 prev 指向此节点的前驱节点,同时,删除 HashMap 中此节点的 key。


动手实现


=======================================================================


思路就是这么一个思路,有了这个思路我撸起袖子开始写代码,由于自身算法比较渣,而且又好长时间不刷算法,所以我的惨痛经历如下。



先是执行出错,后来又解答错误,顿时开始怀疑人生,怀疑智商。最后发现,确实是智商问题。



总归就是这么一个意思,你也去写一遍试试吧,看看效果如何。原题地址:https://leetcode-cn.com/problems/lru-cache/


除了 LRU 还有 LFU


================================================================================


还有一种常用的淘汰策略叫做 LFU(Least Frequently Used),最不经常使用。相比于 LFU 更加注重访问频次。在 LRU 的基础上增加了访问频次。


看下图,举个例子来说,假设现在 put 进来一个键值对,并且超过了最大的容量,那就要删除一个键值对。假设 key2 是在 5 分钟之前访问过一次,而 key1 是在 10 分钟之前访问过,以 LRU 的策略来说,就会删除头节点,也就是图中的 key1。但是如果是 LFU 的话,会记录每个 key 的访问频次,虽然 key2 是最近一次访问晚于 key1,但是它的频次比 key1 少,那要淘汰一个 key 的话,还是要淘汰 key2 的。只是举个例子,真正的 LFU 数据结构比 LRU 要复杂。


看 LeetCode 上的难度等级就知道了,LFU 也有一道对应的题目,地址:https://leetcode-cn.com/problems/lfu-cache/,它的难度是困难,而 LRU 的难度是中等。



还有一种 FIFO ,先进先出策略,先进入缓存的会先被淘汰,比起上面两种,它的命中率比较低。


优缺点分析


========================================================================


LRU 的优点:LRU 相比于 LFU 而言性能更好一些,因为它算法相对比较简单,不需要记录访问频次,可以更好的应对突发流量。


LRU 的缺点:虽然性能好一些,但是它通过历史数据来预测未来是局限的,它会认为最后到来的数据是最可能被再次访问的,从而给予它最高的优先级。有些非热点数据被访问过后,占据了高优先级,它会在缓存中占据相当长的时间,从而造成空间浪费。


LFU 的优点:LFU 根据访问频次访问,在大部分情况下,热点数据的频次肯定高于非热点数据,所以它的命中率非常高。


LFU 的缺点:LFU 算法相对比较复杂,性能比 LRU 差。有问题的是下面这种情况,比如前一段时间微博有个热点话题热度非常高,就比如那种可以让微博短时间停止服务的,于是赶紧缓存起来,LFU 算法记录了其中热点词的访问频率,可能高达十几亿,而过后很长一段时间,这个话题已经不是热点了,新的热点也来了,但是,新热点话题的热度没办法到达十几亿,也就是说访问频次没有之前的话题高,那之前的热点就会一直占据着缓存空间,长时间无法被剔除。


针对以上这些问题,现有的缓存框架都会做一系列改进。比如 JVM 本地缓存 Caffeine,或者分布式缓存 Redis。

用户头像

极客good

关注

还未添加个人签名 2021.03.18 加入

还未添加个人简介

评论

发布
暂无评论
从一道 LRU 算法题说到缓存淘汰策略,Java常用面试集合