本文已收录到 ，技术和职场问题，请关注公众号 [彭旭锐] 提问。
前言
大家好，我是小彭。
在上一篇文章里，我们聊到了 的实现原理和源码分析，在源码分析的过程中，我们发现一些 相关的源码，当时没有展开，现在它来了。
那么， 与 有什么区别呢？其实， 的使用场景非常明确 —— LRU 缓存。今天，我们就来讨论 是如何实现 LRU 缓存的。
本文源码基于 Java 8 。
思维导图：
1. 认识 LRU 缓存淘汰算法1.1 什么是缓存淘汰算法？
缓存是提高数据读取性能的通用技术，在硬件和软件设计中被广泛使用，例如 CPU 缓存、Glide 内存缓存，数据库缓存等。由于缓存空间不可能无限大，当缓存容量占满时，就需要利用某种策略将部分数据换出缓存，这就是缓存的替换策略 / 淘汰问题。常见缓存淘汰策略有：
FIFO 与 LRU 策略
1.2 向外看：LRU 的变型
其实，在标准的 LRU 算法上还有一些变型实现，这是因为 LRU 算法本身也存在一些不足。例如，当数据中热点数据较多时，LRU 能够保证较高的命中率。但是当有偶发的批量的非热点数据产生时，就会将热点数据寄出缓存，使得缓存被污染。因此，LRU 也有一些变型：
小彭在 Redis 和 Vue 中有看到这些 LRU 变型的应用，在 领域的框架中还没有看到具体应用，你知道的话可以提醒我。
1.3 如何实现 LRU 缓存淘汰算法？
这一小节，我们尝试找到 LRU 缓存淘汰算法的实现方案。经过总结，我们可以定义一个缓存系统的基本操作：
我们发现，前 3 个操作都有 “查询” 操作， 所以缓存系统的性能主要取决于查找数据和淘汰数据是否高效。 下面，我们用递推的思路推导 LRU 缓存的实现方案，主要分为 3 种方案：
方案 2 - 基于双向链表： 不再直接维护时间戳，而是利用链表的顺序隐式维护时间戳的先后顺序。当数据被访问（添加、更新或查询）时，将数据插入到链表头部。当空间已满时，直接淘汰链表的尾节点。
方案 3 - 基于双向链表 + 散列表： 使用双向链表可以将淘汰数据的时间复杂度降低为 O(1)，但是查询数据的时间复杂度还是 O(n)，我们可以在双向链表的基础上增加散列表，将查询操作的时间复杂度降低为 O(1)。
方案 3 这种数据结构就叫 “哈希链表或链式哈希表”，我更倾向于称为哈希链表，因为当这两个数据结构相结合时，我们更看重的是它作为链表的排序能力。
我们今天要讨论的 Java 就是基于哈希链表的数据结构。
2. 认识 哈希链表2.1 说一下 的特点
需要注意： 中的 “” 实际上是指双向链表，并不是指解决散列冲突中的分离链表法。
2、 支持 2 种排序模式，这是通过构造器参数 标记位控制的，表示是否按照访问顺序排序，默认为 false 按照插入顺序。
3、在有序性的基础上， 提供了维护了淘汰数据能力，并开放了淘汰判断的接口 ()。在每次添加数据时，会回调 () 接口，开发者可以重写这个接口决定是否移除最早的节点（在 FIFO 策略中是最早添加的节点，在 LRU 策略中是最早未访问的节点）；
4、与 相同， 也不考虑线程同步，也会存在线程安全问题。可以使用 . 包装类，其原理也是在所有方法上增加 关键字。
2.2 说一下 和 的区别？
事实上， 和 并不是平行的关系，而是继承的关系java lru算法 如何使用 LinkedHashMap 实现 LRU 缓存？， 是继承于 实现的哈希链表。
两者主要的区别在于有序性： 会维护数据的插入顺序或访问顺序，而且封装了淘汰数据的能力。在迭代器遍历时， 会按照数组顺序遍历桶节点，从开发者的视角看是无序的。而是按照双向链表的顺序从 head 节点开始遍历，从开发者的视角是可以感知到的插入顺序或访问顺序。
示意图
3. 预留的 Hook 点
继承于 ，在后者的基础上通过双向链表维护节点的插入顺序或访问顺序。因此，我们先回顾下 为 预留的 Hook 点：
.java
// 节点访问回调
void afterNodeAccess(Node p) { }
// 节点插入回调
// evict：是否淘汰最早的节点
void afterNodeInsertion(boolean evict) { }
// 节点移除回调
void afterNodeRemoval(Node p) { }
除此了这 3 个空方法外， 也重写了部分 的方法，在其中插入双链表的维护逻辑，也相当于 Hook 点。在 的添加、获取、移除方法中，与 有关的 Hook 点如下：
3.1 的添加方法中的 Hook 点
直接复用 的添加方法，也支持批量添加：
不管是逐个添加还是批量添加，最终都会先通过 hash 函数计算键（Key）的散列值，再通过 # 添加或更新键值对，这些都是 的行为。关键的地方在于： 在 # 的 Hook 点中加入了双线链表的逻辑。区分 2 种情况：
.java
// 添加或更新键值对
public V put(K key, V value) {
return putVal(hash(key) /*计算散列值*/, key, value, false, true);
}
// hash：Key 的散列值（经过扰动）
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node[] tab;
Node p;
int n;
int i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// (n - 1) & hash：散列值转数组下标
if ((p = tab[i = (n - 1) & hash]) == null)
// 省略遍历桶的代码，具体分析见 HashMap 源码讲解
// 1.1 如果节点不存在，则新增节点
p.next = newNode(hash, key, value, null);
// 2.1 如果节点存在更新节点 Value
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 2.2 Hook：访问节点回调
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 扩容
if (++size > threshold)
resize();
// 1.2 Hook：新增节点回调
afterNodeInsertion(evict);
return null;
}
#put 示意图
3.2 的获取方法中的 Hook 点
重写了 #get 方法，在 版本的基础上，增加了 () 回调。
.java
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
.java
public V get(Object key) {
Node e;
if ((e = getNode(hash(key), key)) == null)
return null;
// Hook：节点访问回调
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
public V getOrDefault(Object key, V defaultValue) {
Node e;
if ((e = getNode(hash(key), key)) == null)
return defaultValue;
// Hook：节点访问回调
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
#get 示意图
3.3 的移除方法中的 Hook 点
直接复用 的移除方法，在移除节点后，增加 () 回调。
.java
// 移除节点
public V remove(Object key) {
Node e;
return (e = removeNode(hash(key)/*计算散列值*/, key, null, false, true)) == null ? null : e.value;
}
final Node removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node[] tab;
Node p;
int n, index;
// (n - 1) & hash：散列值转数组下标
if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
Node node = null, e; K k; V v;
// 省略遍历桶的代码，具体分析见 HashMap 源码讲解
// 删除 node 节点
if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
// 省略删除节点的代码，具体分析见 HashMap 源码讲解
++modCount;
--size;
// Hook：删除节点回调
afterNodeRemoval(node);
return node;
}
}
return null;
}
# 示意图
4. 源码分析
这一节，我们来分析 中主要流程的源码。
4.1 的属性
节点继承关系
.java
public class LinkedHashMap extends HashMap implements Map {
// 头指针
transient LinkedHashMap.Entry head;
// 尾指针
transient LinkedHashMap.Entry tail;
// 是否按照访问顺序排序
final boolean accessOrder;
// 双向链表节点
static class Entry extends HashMap.Node {
// 前驱指针和后继指针（用于双向链表）
Entry before, after;
Entry(int hash, K key, V value, Node next/*单链表指针（用于散列表的冲突解决）*/) {
super(hash, key, value, next);
}
}
}
.java
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable {
// 头指针（// LinkedList 中也有类似的头尾节点）
transient Node first;
// 尾指针
transient Node last;
// 双向链表节点
private static class Node {
// 节点数据
// （类型擦除后：Object item;）
E item;
// 前驱指针
Node next;
// 后继指针
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
的属性很好理解的，不出意外的话又有小朋友出来举手提问了：
我的理解是作者希望简化节点类型，所以采用了非常规的做法（不愧是标准库）。由于 Java 是单继承的，如果按照常规的做法让 . 直接继承 .Nodejava lru算法，那么在 中就需要区分 .Entry 和 .，再使用接口统一两种类型。
常规实现
4.2 的构造方法
有 5 个构造方法，作用与 的构造方法基本一致，区别只在于对 字段的初始化。
<p><pre>// 带初始容量和装载因子的构造方法
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;}
// 带初始容量的构造方法
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;}
// 无参构造方法
public LinkedHashMap() {
super();
accessOrder = false;}
// 带 Map 的构造方法
public LinkedHashMap(Map