一.什么是LRU算法？ LRU的全名是Least Recently Used，LRU算法是一种操作系统级的页面替换算法，用于丢弃最近最少使用的页面。
二、基于双向链表Map实现LRU算法，为什么选择双向链表为cache？
思想：将多次访问的节点移动到开头节点，将访问少的节点移动到末尾节点。
通过双向链表的特性，可以方便地找到上一个节点和下一个节点，节点操作相对容易。 单向无法找到上一个节点，并且在操作期间无法遍历当前节点的上一个节点。
1 .把双向链表看成cache缓存，在链表的各个节点存储数据。 使用cache时，主要有两个操作。 一个是向cache添加数据，另一个是从cache获取数据。
对于get操作：
1 ) map中不存在时，直接返回null。
2 )如果在map中，找到要将节点移动到双向链表中的标头。
put操作：时
1 )判断为先通过上述get操作获取了节点，在不存在节点时，用history.size(==capcity )判断容量是否已满，如果已满，则从map中删除尾节点，同时删除双向链表的
2 )存在节点时，cache (双向链表)中对应节点移动到链表的头部。
2 .用map记录访问cache的记录，访问cache后将节点放置在map上。 3 .通过移动节点和淘汰策略的过程图解，可以看出双向链表的优点得到了体现。
三.完整代码package sort； import java.util.Map； import Java.util.concurrent.concurrent hashmap；/* * @ author bing bing * @ date 2021/5/700079336058 */publicclasslrucachev { private int capacity=1024； private static MapString，node history=newconcurrenthashmap (； 节点头； 节点tail； publiclrucache(intcapacity ) { this )； this.capacity=capacity； } public LRUCache () { head=new Node )； tail=new Node (； head.next=tail； head.pre=null； tail.pre=head； tail.next=null； }privatevget(stringkey ) nodenode=history.get ) key； if (空值==节点) { return null； //标头node.pre.next=node.next； node.next.pre=node.pre； node.next=head.next； head.next.pre=node； head.next=node； node.pre=head； return(v ) node； }privatevoidput(stringkey，V value ) nodenode=history.get ) key； if(null==node )//确定容量是否已满if (history.size )==capacity ) (history.remove ) tail.Pre.key )； tail.pre=tail.next； tail.next=null； tail=tail.pre； }//插入标头node=(Node ) value； history.put(key，node )； node.next=head.next； head.next.pre=node； head.next=node； node.pre=head； } static class Nodek，v { private k key； 权限v value； Nodek，v pre； Nodek，v next； Publicnode(kkey，v value ) ) { this.key=key； this.value=value； } public Node () } publicstaticvoidmain (string [ ] args ) (Lrucachenodecache=newLrucache ) ) 4； NodeString，Integer node1=new NodeString，integer('K1 '，1 )； NodeString，Integer node2=new NodeString，integer('K2 '，2 )； NodeString，Integer node3=new NodeString，integer('K3 '，3 )； NodeString，Integer node4=new NodeString，integer('K4 '，4 )； NodeString，Integer node5=new NodeString，integer('K5 '，5 )； che.put(k1 )、node1)； che.put('K2 '，node2)； che.put(k3 )、node3)； che.put(k4 )、node4)； //cache.get('k1 )； che.put(k5 )、node5)； nodenode=cache.get('k1 )； system.out.println(node )； }效果演示：
1 )注释cache.get(k1 ) )，从cache中取k1，查看结果
null 2)放开cache.get('k1 ) )，从cache中取k1，查看结果
sort.LRUCache$Node@14ae5a5的初始容量只有4，如果遵从最小使用规则的话，k1将被淘汰，因此初始测试结果为null，由于在第2次测试中新获得了k1，k1将移动到头部节点
参照：
3359 blog.csdn.net/belongtocode/article/details/102989685
3359 blog.csdn.net/QQ _ 26440803/article/details/83795122