为了提高效率,很多数据是可以放在内存中的,但是内存空间是有限的,假如数据满了,再添加数据,应该清除哪些数据了。LRU就是一种清除数据的策略,LRU是Least Recently Used的缩写,即最近最少使用的数据可以清除
我们使用HashMap来存放数据,再使用双向链表来维护最近最少使用的顺序,双向链表从头到尾依次最近最少使用的到最近最多使用的
上图中,依次加入A,B,C这时候访问一下A,则把A放在链表的尾部
如果空间只够存储3个元素,这时候要加D了,就需要头部的B弹出,把D放在尾部。
所以,每次访问的元素或者添加的元素就放在队尾,也就是最近最常用的元素,那么放在头部的就是最近最少使用的元素。
JAVA中的LinkedHashMap其实就是这样一个结构,Map中这几个方法没有实现,LinkedHashMap实现了。
可以使用HashMap和链表来实现,下面的代码是链表中的几个关键步骤:
定义数据结构(节点,双向链表,一个头,一个尾):
添加节点操作
容量满了删除最近最少使用的
每次访问都把元素放在尾部