LRU在很多缓存失效策略中会涉及，本质是一种更公平的节约资源策略
比如使用redis缓存数据，不可能将所有资源都缓存起来，内存耗不起
但也不能一刀切的设定一个过期时间，自动过期，因为可能热点数据它经常被访问到
LRU算法思想应运而生，LRU是Least Recently Used的缩写，即最近最少使用
在资源有限的情况下，我们要将最近最少使用的对象解除资源占用，给更需要的场景
java中的LinkedHashMap就有自带的实现LRU
简单说一下LinkedHashMap这种数据结构，本质是HashMap+双向链表，不仅有HashMap的特性，还能维护元素的顺序，示意图如下
使用LinkedHashMap实现简单的LRU
杨家将父子打扑克，跑得快，一局只能有四个人参与，但杨家将父子有八人
约定赢了（被访问次数多）的前两位留下，输了（访问次数少）的出局，给后面的新进的腾位置
....;
..;
..;
..;
, {
;
, ;
( ) {
().( .) ;
, (, , ) {
(. ) {
() ;
}
};
}
( , ) {
.(, );
}
( ) {
.();
}
( ) {
.();
}
( ) {
.();
}
([] ) {
, , ();
., ..();
.(, );
.(, );
.(, );
.(, );
..();
(., :){
..(.().());
}
.();
.();
..();
.(, );
.(, );
..();
(., :){
..(.().());
}
.();
.();
..();
.(, );
.(, );
..();
(., :){
..(.().());
}
..();
}
}核心思想
1、构造LinkedHashMap时accessOrder传true
2、LinkedHashMap特性，元素在被访问时，accessOrder为true，会进行重排序
( ) {
, ;
(( ((), )) )
;
()
();
.;
}afterNodeAccess，将元素排到最后
(, ) {
., ;
( ( ) ) {
.,
(.,), ., .;
. ;
( )
;
. ;
( )
. ;
;
( )
;
{
. ;
. ;
}
;
;
}
}3、覆写LinkedHashMap的removeEldestEntry方法，写自己的触发removeEldestEntry逻辑，什么情况下将最近最少使用元素移除，即双向链表的头部元素
我这里是只要内部元素大于4个就移除
移除逻辑源代码在LinkedHashMap中
( ) {
., ;
( ( ) ()) {
.;
((), , , , );
}
}而removeNode还是HashMap的
, ( , , ,
, ) {
,[] ; , ; , ;
(( ) ( .)
( [ ( ) ]) ) {
, , ; ; ;
(.
(( .) ( .())))
;
(( .) ) {
( )
((,)).(, );
{
{
(.
(( .)
( .()))) {
;
;
}
;
} (( .) );
}
}
( ( ( .)
( .()))) {
( )
((,)).(, , );
( )
[] .;
. .;
;
;
();
;
}
}
;
}先进先出，有点类似栈
