人生有涯,学海无涯。
《Java 极客技术》公众号已经有很多优质的原创文章了,但是纵观公号的历史文章总感觉少了点啥,那就是算法相关的内容。算法可以说是编程人员不可避免的一个难题,而且算法也是一个非常难的课题,很多人一提到数据结构与算法都会瑟瑟发抖。学算法是一个持久战,后续我们会慢慢增加算法相关的文章,尽量的为大家提供一些帮助,今天让我们来看一个经典的算法 LRU(最近最少使用)算法。
LRU 简介
Least Recently Used的缩写,即最近最少使用,可以用来作为路由或者淘汰算法。很多开源的框架或者一些第三方的项目都会采用到这个算法,比如 Redis 的 key 的缓存失效,比如一些路由功能。
算法的思想是:如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小。正是由于这个特性,所以我们可以将使用不到的数据淘汰,或者如果是路由,我们就可以将数据路由到这台机器,实现负载。
这里我们以淘汰数据为例,提供两种实现方式。
算法实现
基于链表的 LRU 实现
思路:每次新插入数据的时候将新数据插到链表的头部;每次缓存命中(即数据被访问),则将数据移到链表头部;那么当链表满的时候,就将链表尾部的数据淘汰。
代码实现
1 |
|
基于 HashMap 和 Linkedlist 的 LRU 实现
这种实现方式其他跟上面的实现方式类似,区别的地方是在这种方式采用的是 JDK 封装好的,给大家参考如下
1 |
|
总结
今天给大家介绍了一下 LRU 算法的两种实现,还有很多变种的实现方式大家可以自行的搜索学习。
我们只要记住 LRU 的核心思想:新增和最近被访问的数据需要移到到链表前,淘汰的是链表最后的一个数据。
在算法的道路上还有很多路要走,大家一起加油。