公子王孙逐后尘，绿珠垂泪滴罗巾。侯门一入深如海，从此萧郎是路人。 ——唐.崔郊 《赠去婢》
一、概念
- LRU是Least Recently Used的缩写，即最近最少使用，常用于页面置换算法，是为虚拟页式存储管理服务的。
- 设计原则：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
二、实现
- 数组方式
- 用一个数组来存储数据，给每一个数据项标记一个访问时间戳；
- 每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中；
- 每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0；
- 当数组空间已满时，将时间戳最大的数据项淘汰。
- 链表方式
- 用一个链表来存储数据；
- 每次新插入数据的时候将新数据插到链表的头部；
- 每次数据被访问到将数据移到链表头部；
- 当链表满的时候，就将链表尾部的数据丢弃。
三、常见缓存淘汰算法
- FIFO：first in first out，先进先出，即假定刚刚加入的数据总会被访问到；
- LRU：least recently used，最近最少使用，判断最近被使用的时间，假定未被使用的时间越久就不可能在被使用；
- LFU：least frequently used，数据使用次数最少的，优先被淘汰。