概念
lru（least recently used)就是将最近不被访问的数据给淘汰掉，lru基于一种假设：认为最近使用过的数据将来被使用的概率也大，最近没有被访问的数据将来被使用的概率比较低。
原理
lru一般通过链表形式来存放缓存数据，新插入或被访问的数据放在链表头部，超过一定阈值后，自动淘汰链表尾部的数据。下图很形象的说明了lru缓存淘汰过程。（图片来自网络）
步骤：
1、新插入a， 将a放置在队列头部
2、新插入b， 将b放置在队列头部， a自动推举次席。
3、新插入c， 将c放置在队列头部， b自动推举次席。
4、新插入d， 将d放置在队列头部， c自动推举次席。
5、新插入e， 将e放置在队列头部， d自动推举次席。
6、新插入e， 将e放置在队列头部， 这时队列长度大于阈值，自动将尾部数据a给淘汰掉
7、访问数据c，然后将c重新放置在队列头部。
8、新插入e， 将e放置在队列头部， 这时队列长度大于阈值，自动淘汰尾部数据b
编码实现lru策略缓存
/**
* 2020/4/11.
*
* 使用链表 hashmap来实现, 这里没有考虑并发情况, 所以在代码中没有使用锁
*/
public class lrucache {
class cachenode {
public cachenode before;
public object key;
public object value;
public cachenode after;
public cachenode() {
}
}
private hashmap caches;
private int maxcapacity;
private int currentcachesize;
/**
* 头结点, 头结点不参与淘汰,只是作为标识链表中的第一个节点
*/
private cachenode head;
/**
* 尾节点, 尾节点不参与淘汰, 只是作为标识链表中最后一个节点
*/
private cachenode tail;
public lrucache(int maxcapacity) {
this.maxcapacity = maxcapacity;
caches = new hashmap<>(maxcapacity);
head = tail = new cachenode();
head.after = tail; //对head 的after节点赋值, 防止后续操作出现空指针异常
tail.before = head; // 对tail的before节点赋值, 防止后续操作出现空指针异常
}
public void put(k k, v v) {
cachenode node = caches.get(k);
if (node == null) {
if (currentcachesize >= maxcapacity) {
caches.remove(tail.before.key); //淘汰尾部的元素
removelast();
}
node = new cachenode();
node.key = k;
currentcachesize ;
}
node.value = v;
movetofirst(node); // lru策略, 新插入的元素放置到队列头部
caches.put(k, node);
}
public void movetofirst(cachenode node) {
cachenode n = head.after;
head.after = node;
node.before = head;
n.before = node;
node.after = n;
}
public void removelast() {
cachenode n = tail.before.before;
n.after = tail;
tail.before = n;
}
public object get(k k) {
cachenode node = caches.get(k);
if (node == null) {
return null;
}
object v = node.value;
movetofirst(node);
return v;
}
public object remove(k k) {
cachenode node = caches.get(k);
if (node == null) {
return null;
}
cachenode pre = node.before;
cachenode next = node.after;
pre.after = next;
next.before = pre;
caches.remove(k);
currentcachesize --;
return node.value;
}
}