✏️原理概述：LRU（Least Recently Used)，最近最少使用原则实现的缓存淘汰算法。
❌“最近最少”的误解：很多人看字面意思很可能理解为“最近使用和最少使用的被淘汰”，理解几乎完全相反了。
✔️“最近最少”的正确理解：基于这一种准则：刚使用过的、最新添加的元素，被（再次）使用到的概率更大，因此要放到队列读取的最前端，最先淘汰队列尾端的元素（说明它被添加的时间很长了而且很少被访问到过，若是新添加的、经常被访问过的应该在靠近读取端头部）。
看这样一个例子：面试题 16.25. LRU 缓存
//简单删了几个方法
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.put(4, 4); // 该操作会使得密钥 1 作废✏️下面是图解:
💠实现方式① ：利用LinkedHashMap的accessOrder
class LRUCache {
private int capacity;
private Map<Integer, Integer> map;
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new LinkedHashMap(capacity); //单纯使用LinkedHashMap的插入顺序与输出顺序一致
}
public int get(int key) {
if (!map.containsKey(key))
return -1;
int val = map.get(key);
//重新put，将访问过的元素提到队头（访问方向）
map.remove(key);
map.put(key, val);
return val;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
map.remove(key);
map.put(key, value);
return;
}
//超过容器大小，删除队尾。
//刚好LinkedHashMap的迭代指针默认指向队尾，所以直接删除指针第一个
if (map.size() >= capacity)
map.remove(map.keySet().iterator().next());
map.put(key, value);
}
}
💠实现方式②：继承LinkedHashMap重写
LinkedHashMap的最大价值就是缓存淘汰实现，其内部已经被实现了LRU基础功能，需要修改的是removeEldestEntry方法，即在什么情况下才会触发删除策略，我们这里是当容器满了的时候，触发删除策略。
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
//增加负载因子，超过容量会自动删除
private static final Float CAPACITY_FACTOR = 0.75f;
public LRUCache(int capacity) {
super(capacity, CAPACITY_FACTOR, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
//重写removeEldestEntry方法，当超过容器元素时移除最“老”元素
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
//size()为 父类已有的方法
return size() > capacity;
}
}💠实现方式③：HashMap + 双向链表
操作方式：读取在链表尾，删除在链表头，所以要增加移动到链表尾的操作。
注意，双向链表中，head和tail是哨兵节点，不存储实际值，实际链表的值在两者之间。
public class LRUCache{
private int capacity;
private Map<Integer, ListNode> map; //key->node
private ListNode head; // dummy head
private ListNode tail; // dummy tail
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
head = new ListNode(-1, -1);
tail = new ListNode(-1, -1);
head.next = tail;
tail.pre = head;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
ListNode node = map.get(key);
// 先删除该节点，再接到尾部
node.pre.next = node.next;
node.next.pre = node.pre;
moveToTail(node);
return node.val;
}
public void put(int key, int value) {
// 直接调用这边的get方法，如果存在，它会在get内部被移动到尾巴，不用再移动一遍,直接修改值即可
if (get(key) != -1) {
map.get(key).val = value;
return;
}
// 若不存在，new一个出来,如果超出容量，把头去掉
ListNode node = new ListNode(key, value);
map.put(key, node);
moveToTail(node);
if (map.size() > capacity) {
map.remove(head.next.key);
head.next = head.next.next;
head.next.pre = head;
}
}
// 把节点移动到尾巴
private void moveToTail(ListNode node) {
node.pre = tail.pre;
tail.pre = node;
node.pre.next = node;
node.next = tail;
}
// 定义双向链表节点
private class ListNode {
int key;
int val;
ListNode pre;
ListNode next;
public ListNode(int key, int val) {
this.key = key;
this.val = val;
pre = null;
next = null;
}
}
}
💠实现方式④：HashMap + 单向链表
public class LRUCache{
private int capacity;
private Map<Integer, ListNode> map; //key -> node.pre
private ListNode head; // dummy
private ListNode tail;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
head = new ListNode(-1, -1);
tail = head;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
// map中存放的是要找的节点的前驱
ListNode pre = map.get(key);
ListNode cur = pre.next;
// 把当前节点删掉并移到尾部
if (cur != tail) {
pre.next = cur.next;
// 更新它后面 node 的前驱
map.put(cur.next.key, pre);
map.put(cur.key, tail);
moveToTail(cur);
}
return cur.val;
}
public void put(int key, int value) {
if (get(key) != -1) {
map.get(key).next.val = value;
return;
}
// 若不存在则 new 一个
ListNode node = new ListNode(key, value);
// 当前 node 的 pre 是 tail
map.put(key, tail);
moveToTail(node);
if (map.size() > capacity) {
map.remove(head.next.key);
map.put(head.next.next.key, head);
head.next = head.next.next;
}
}
private void moveToTail(ListNode node) {
node.next = null;
tail.next = node;
tail = tail.next;
}
// 定义单链表节点
private class ListNode {
int key, val;
ListNode next;
public ListNode(int key, int val) {
this.key = key;
this.val = val;
this.next = null;
}
}
}