date
Oct 14, 2021
summary
LRU（Least Recently Used)，最近最少使用原则算法浅析。
status
Published
type
Post
slug
lru
icon
tags
算法
JAVA
✏️原理概述：LRU（Least Recently Used)，最近最少使用原则实现的缓存淘汰算法。
❌“最近最少”的误解：很多人看字面意思很可能理解为“最近使用和最少使用的被淘汰”，理解几乎完全相反了。
✔️“最近最少”的正确理解：基于这一种准则：刚使用过的、最新添加的元素，被（再次）使用到的概率更大，因此要放到队列读取的最前端，最先淘汰队列尾端的元素（说明它被添加的时间很长了而且很少被访问到过，若是新添加的、经常被访问过的应该在靠近读取端头部）。
看这样一个例子：面试题 16.25. LRU 缓存
✏️下面是图解:
💠实现方式① ：利用LinkedHashMap的accessOrder
💠实现方式②：继承LinkedHashMap重写
LinkedHashMap的最大价值就是缓存淘汰实现，其内部已经被实现了LRU基础功能，需要修改的是removeEldestEntry方法，即在什么情况下才会触发删除策略，我们这里是当容器满了的时候，触发删除策略。
💠实现方式③：HashMap + 双向链表
操作方式：读取在链表尾，删除在链表头，所以要增加移动到链表尾的操作。
注意，双向链表中，head和tail是哨兵节点，不存储实际值，实际链表的值在两者之间。
💠实现方式④：HashMap + 单向链表
- 作者:zion
- 链接:https://gendlee.github.io/lru
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
