Least Recently Used 算法--LRU

2026-01-09 算法

解决什么问题为了提高效率，很多数据是可以放在内存中的，但是内存空间是有限的，假如数据满了，再添加数据，应该清除哪些数据了。LRU就是一种清除数据的策略，LRU是Least Recently Used的缩写，即最近最少使用的数据可以清除
数据结构我们使用HashMap来存放数据，再使用双向链表来维护最近最少使用的顺序，双向链表从头到尾依次最近最少使用的到最近最多使用的

Least Recently Used 算法--LRU

文章插图

上图中，依次加入A，B，C这时候访问一下A，则把A放在链表的尾部

Least Recently Used 算法--LRU

文章插图

如果空间只够存储3个元素，这时候要加D了，就需要头部的B弹出，把D放在尾部。
【Least Recently Used 算法--LRU】所以，每次访问的元素或者添加的元素就放在队尾，也就是最近最常用的元素，那么放在头部的就是最近最少使用的元素。
代码JAVA中的LinkedHashMap其实就是这样一个结构，Map中这几个方法没有实现，LinkedHashMap实现了。

Least Recently Used 算法--LRU

文章插图

可以使用HashMap和链表来实现，下面的代码是链表中的几个关键步骤：
定义数据结构（节点，双向链表，一个头，一个尾）：

Least Recently Used 算法--LRU

文章插图

Least Recently Used 算法--LRU

文章插图

添加节点操作

Least Recently Used 算法--LRU

文章插图

容量满了删除最近最少使用的

Least Recently Used 算法--LRU

文章插图

每次访问都把元素放在尾部

Least Recently Used 算法--LRU

文章插图

推荐阅读

上一篇：铁壶泡茶不仅能改善水质还有很多好处

下一篇：好铁壶能加强水的口感,铁壶好坏取决于内壁