如何动手撸一个LRU缓存
上篇文章介绍了，如何动手实现一个LFU缓存，今天我们来学习下如何动手实现一个LRU缓存，在这之前，我们还是先回顾下关于缓存置换算法的三种策略：
我们知道缓存置换算法主流的有三种，分别是：
(1) FIFO：First In First Out，先进先出策略
(2) LFU：Least Frequently Used，最不经常使用策略
(3) LRU：Least Recently Used，最近最少使用策略
LRU 全称 Least Recently Used，基于数据访问历史记录来执行淘汰策略，LRU是首先淘汰最长时间未被使用的页面，这种算法把近期最久没有被访问过的页面作为被替换的页面，与LFU不一样的是，LRU并不关注缓存数据的访问次数，它只关注该条数据的访问时间。核心思想：如果一个数据在最近一段时间内没被访问，则在将来一段时间内被访问的可能性也很小。
LRU缓存的实现相比LFU来说要简单一点，最关键的在于LRU缓存插入，查询和删除可以做到O（1）的时间复杂度，这一点相比LFU的O（logN）来说在大数据量下LRU表现更好，此外LRU非常适合存在热点数据的场景。
我们看下实现的代码：
public class LruCache {
//设置的虚拟头节点
Node head = new Node(0, 0);
//设置的虚拟尾部节点
Node tail = new Node(0, 0);
//使用map来提升查询性能
Map<Integer, Node> map = new HashMap<>();
int capacity;//缓存保存数据的大小
public LruCache(int capacity) {
this.capacity = capacity;
//初始化
head.next = tail;
tail.prev = head;
}
//查询数据
public int get(int key) {
//判断是否存在该条数据
if (map.containsKey(key)) {
Node node = map.get(key);
remove(node);
insert(node);
//如果存在，就直接返回，并把该条数据从原来的位置移除，放入链表的头部
return node.value;
} else {
//不存在就返回-1
return -1;
}
}
public void put(int key, int value) {
//如果该节点已经存在，就删除该节点
if (map.containsKey(key)) {
remove(map.get(key));
}
//判断缓存容量是否达到上限
if (map.size() == capacity) {
remove(tail.prev);//如果达到上限就移除链表最后的节点
}
//插入新节点
insert(new Node(key, value));
}
//移除无效的node
public void remove(Node node) {
map.remove(node.key);//移除目标节点
//建立双向链表关系
//目标节点的前置指向目标节点的后置
node.prev.next = node.next;
//目标节点的后置指向目标节点的前置
node.next.prev = node.prev;
}
//插入一个节点
private void insert(Node node) {
//将数据，放入map中，加速查询
map.put(node.key, node);
//将新插入的数据，放在链表的头部，这里使用头插法，性能O（1）
Node headNext = head.next;
head.next = node;
node.prev = head;
headNext.prev = node;
node.next = headNext;
}
//定义一个双向链表
class Node {
Node prev;
Node next;
int key;
int value;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
}代码非常简单，这里简单分析下原理。
首先让我们分析下LRU缓存为什么能达到O（1）的时间复杂度。众所周知，双向链表的插入和删除可以达到O（1）的时间复杂度，但双向链表的缺点在于，其查询的时间复杂度为O（n）这就是它的短板，那么如何加速查询？这里我们可以利用HashMap来当索引查询，从而使得双向链表的查询的时间复杂度也能达到O（1），没错LRU的实现原理，就是充分结合了两种数据结构的优点而衍生出来的。我们看下面的一张图就非常直观的显示了这种关系：
上图中HashMap的key就是链表数据的key，而value就是该Node在双向链表里面的位置，也就是指针地址。
明白了原理之后，我们在看代码逻辑就一目了然了，简单分析下：
（1）首先我们定义一个双向链表的结构：
//定义一个双向链表
class Node {
Node prev;
Node next;
int key;
int value;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}更通用的策略可以把key和value做成泛型
（2）在LRUcache类里面，我们定义了虚拟的head和tail节点其目的是为了方便操作删除动作，此外我们还定义了一个缓存容量和辅助的map结构来加速查询。
//设置的虚拟头节点
Node head = new Node(0, 0);
//设置的虚拟尾部节点
Node tail = new Node(0, 0);
//使用map来提升查询性能
Map<Integer, Node> map = new HashMap<>();
int capacity;//缓存保存数据的大小
public LruCache(int capacity) {
this.capacity = capacity;
//初始化
head.next = tail;
tail.prev = head;
}（3）put方法分析
put方法中，我们首先判断要插入的key是否存在，如果存在就删除掉，方便将其移动到链表头部位置，接着我们判断缓存的容量是否超出指定大小，如果超出就要淘汰最旧的数据，也就是位于链表尾部（尾部是虚拟的）的节点的前一个节点。最后执行插入方法。
（4）insert方法分析
insert方法非常简单，首先将要插入的节点，给加入到map里面建立索引，然后接着使用头插法，将节点插入链表的头部。
（5）remove方法分析
remove时候，首先要删除HashMap里面的索引数据，这样新的查询就不会查询到该条数据，接着删除自身，删除自身的方法非常简单，就是讲自身的前置节点的引用指向自身的next节点，然后将自身next节点的prev指针指向自身的prev节点。这样就完成 了删除操作，而自身由于没有对象再引用自己，所以在下次GC时可以回收掉这部分资源。
（6）get方法分析
get方法就查询方法，直接判断map里面是否存在该条数据，如果存在就返回，并把访问的节点移到链表的头部，代表最近访问过。如果不存在就返回-1代表查询的节点不存在。
可以看到实现一个LRU缓存并不是很难，如果大家对Java里面的LinkedHashMap比较熟悉的话，就会发现LinkedHashMap的原理就与我们上面分析的实现非常相似，这也是为什么LinkedHashMap本身也可以用来做LRU缓存的原因。如下：
LinkedHashMap<String, Integer> map = new LinkedHashMap<String, Integer>(16,0.75f,true);友情提示：代码块可左右滑动
LinkedHashMap的第三个参数，就是用来控制开启LRU功能的关键：
true代表LinkedHashMap使用访问顺序，这就是LRU缓存的功能
false代表LinkedHashMap使用插入顺序，这就维持自然的插入顺序。
本文主要结合代码介绍了LRU缓存的原理和实现，LRU缓存的应用场景主要在于互联网项目的热点数据访问，但对偶发性的、周期性的批量操作会导致LRU算法命中率急剧下降，从而降低其性能，这一点我们应该了解。
腾讯云开发者
