如何使用 LinkedHashMap 实现 LRU 缓存？

学习路线图：

---

1. 认识 LRU 缓存淘汰算法

1.1 什么是缓存淘汰算法？

缓存是提高数据读取性能的通用技术，在硬件和软件设计中被广泛使用，例如 CPU 缓存、Glide 内存缓存，数据库缓存等。由于缓存空间不可能无限大，当缓存容量占满时，就需要利用某种策略将部分数据换出缓存，这就是缓存的替换策略 / 淘汰问题。常见缓存淘汰策略有：

• 1、随机策略： 使用一个随机数生成器随机地选择要被淘汰的数据块；

• 2、FIFO 先进先出策略： 记录各个数据块的访问时间，最早访问的数据最先被淘汰；

• 3、LRU （Least Recently Used）最近最少策略： 记录各个数据块的访问 “时间戳” ，最近最久未使用的数据最先被淘汰。与前 2 种策略相比，LRU 策略平均缓存命中率更高，这是因为 LRU 策略利用了 “局部性原理”：最近被访问过的数据，将来被访问的几率较大，最近很久未访问的数据，将来访问的几率也较小；

• 4、LFU （Least Frequently Used）最不经常使用策略： 与 LRU 相比，LFU 更加注重使用的 “频率” 。LFU 会记录每个数据块的访问次数，最少访问次数的数据最先被淘汰。但是有些数据在开始时使用次数很高，以后不再使用，这些数据就会长时间污染缓存。可以定期将计数器右移一位，形成指数衰减。

FIFO 与 LRU 策略

1.2 向外看：LRU 的变型

其实，在标准的 LRU 算法上还有一些变型实现，这是因为 LRU 算法本身也存在一些不足。例如，当数据中热点数据较多时，LRU 能够保证较高的命中率。但是当有偶发的批量的非热点数据产生时，就会将热点数据寄出缓存，使得缓存被污染。因此，LRU 也有一些变型：

• LRU-K： 提供两个 LRU 队列，一个是访问计数队列，一个是标准的 LRU 队列，两个队列都按照 LRU 规则淘汰数据。当访问一个数据时，数据先进入访问计数队列，当数据访问次数超过 K 次后，才会进入标准 LRU 队列。标准的 LRU 算法相当于 LRU-1；
• Two Queue： 相当于 LRU-2 的变型，将访问计数队列替换为 FIFO 队列淘汰数据数据。当访问一个数据时，数据先进入 FIFO 队列，当第 2 次访问数据时，才会进入标准 LRU 队列；
• Multi Queue： 在 LRU-K 的基础上增加更多队列，提供多个级别的缓冲。

小彭在 Redis 和 Vue 中有看到这些 LRU 变型的应用，在 Android 领域的框架中还没有看到具体应用，你知道的话可以提醒我。

1.3 如何实现 LRU 缓存淘汰算法？

这一小节，我们尝试找到 LRU 缓存淘汰算法的实现方案。经过总结，我们可以定义一个缓存系统的基本操作：

• 操作 1 - 添加数据： 先查询数据是否存在，不存在则添加数据，存在则更新数据，并尝试淘汰数据；
• 操作 2 - 删除数据： 先查询数据是否存在，存在则删除数据；
• 操作 3 - 查询数据： 如果数据不存在则返回 null；
• 操作 4 - 淘汰数据： 添加数据时如果容量已满，则根据缓存淘汰策略一个数据。

我们发现，前 3 个操作都有 “查询” 操作， 所以缓存系统的性能主要取决于查找数据和淘汰数据是否高效。 下面，我们用递推的思路推导 LRU 缓存的实现方案，主要分为 3 种方案：

• 方案 1 - 基于时间戳的数组： 在每个数据块中记录最近访问的时间戳，当数据被访问（添加、更新或查询）时，将数据的时间戳更新到当前时间。当数组空间已满时，则扫描数组淘汰时间戳最小的数据。

  • 查找数据： 需要遍历整个数组找到目标数据，时间复杂度为 O(n)；
  • 淘汰数据： 需要遍历整个数组找到时间戳最小的数据，且在移除数组元素时需要搬运数据，整体时间复杂度为 O(n)。

• 方案 2 - 基于双向链表： 不再直接维护时间戳，而是利用链表的顺序隐式维护时间戳的先后顺序。当数据被访问（添加、更新或查询）时，将数据插入到链表头部。当空间已满时，直接淘汰链表的尾节点。

  • 查询数据：需要遍历整个链表找到目标数据，时间复杂度为 O(n)；
  • 淘汰数据：直接淘汰链表尾节点，时间复杂度为 O(1)。

• 方案 3 - 基于双向链表 + 散列表： 使用双向链表可以将淘汰数据的时间复杂度降低为 O(1)，但是查询数据的时间复杂度还是 O(n)，我们可以在双向链表的基础上增加散列表，将查询操作的时间复杂度降低为 O(1)。

  • 查询数据：通过散列表定位数据，时间复杂度为 O(1)；
  • 淘汰数据：直接淘汰链表尾节点，时间复杂度为 O(1)。

方案 3 这种数据结构就叫 “哈希链表或链式哈希表”，我更倾向于称为哈希链表，因为当这两个数据结构相结合时，我们更看重的是它作为链表的排序能力。

我们今天要讨论的 Java LinkedHashMap 就是基于哈希链表的数据结构。

2. 认识 LinkedHashMap

2.1 LinkedHashMap 的特点

需要注意：LinkedHashMap 中的 “Linked” 实际上是指双向链表，并不是指解决散列冲突中的分离链表法。

• 1、LinkedHashMap 是继承于 HashMap 实现的哈希链表，它同时具备双向链表和散列表的特点。事实上，LinkedHashMap 继承了 HashMap 的主要功能，并通过 HashMap 预留的 Hook 点维护双向链表的逻辑。

  • 1.1 当 LinkedHashMap 作为散列表时，主要体现出 O(1) 时间复杂度的查询效率；
  • 1.2 当 LinkedHashMap 作为双向链表时，主要体现出有序的特性。

• 2、LinkedHashMap 支持 2 种排序模式，这是通过构造器参数 accessOrder 标记位控制的，表示是否按照访问顺序排序，默认为 false 按照插入顺序。