• 介绍
• 实现方式
  • 实现一
  • 实现二
    • 对象关系图：

介绍

LRU是Least Recently Used 的简写，字面意思则是最近最少使用。

通常用于缓存的淘汰策略，由于内存比较宝贵，需要根据某种规则剔除数据保证内存不被撑满。

实现方式

1.通过双向链表来实现，新数据插入到链表头部;
2.每当缓存命中(即缓存 数据被访问)，则将数据移到链表头部;
3.当链表满的时候，将链表尾部的数据丢弃。

实现一

需求：

• 实现一个LRU缓存，当缓存数据达到N之后需要淘汰掉最近最少使用的数据。
• N小时之内没有访问的数据也要被淘汰。

思路：

1. 采用HashMap一样的保存数据的方式；
2. 内部采用队列保存每次写入的数据
3. 写入的时候判断缓存是否大于阈值N，如果满足则根据队列的FIFO特性(先进先出)将队列头的数据删除；
4. 再开启一个守护线程用于判断最先放进去的数据是否超时(最先放进去的数据最有可能满足超时条件)

实现二

优化：

• 要记录最少使用，需要一个有序集合保证写入的顺序
• 在使用了数据之后能够更新顺序

思路：(链表)

1. 每次写入数据的时候将数据放入链表头节点
2. 使用数据时候将数据移动到头节点
3. 缓存数量超过阈值时移除链表尾部数据

实现重点：

1. 数据是直接利用HashMap存放
2. 内部使用了一个双向链表存放数据，所以有一个头节点header与尾节点tailer
3. 每次写入头节点，删除尾节点都是利用header和tailer，
4. 使用数据移动到链表头时，第一步需要在双向链表中找到该节点。链表一个比较大的问题就是查找效率比较低，O(N)。之后依赖于当前节点进行移动。
5. 在写入头节点时，需要判断链表大小等于2时需要删除初始化的头尾节点。因为初始化的时候生成双向节点没有数据，只是为了形成一个数据结构，当真实数据进入之后需要删除方便后续操作
6. 以上所有操作都是线程不安全

对象关系图：

初始化

写入数据

LRUMap<String,Integer> lruMap = new LRUMap(3) ;
lruMap.put("1",1) ;

lruMap.put("2",2) ;

lruMap.put("3",3) ;

lruMap.put("4",4) ;

获取数据

Integer integer = lruMap.get("2");