LRU 缓存与淘汰策略（含 LruCache）

一句话定义

LRU（Least Recently Used） 在容量满时淘汰最久未使用的条目；Android LruCache 用 LinkedHashMap 访问顺序 + 容量上限 实现内存缓存，并配合 sizeOf 按「权重」而不仅是条目个数限流。

可运行 Demo：cache-eviction-demo（LruLinkedHashMapDemo · SimpleLruCache · SimpleLfuCache）
并发字典（去重、索引）不是 LRU：那是 Java CHM 场景，见 map-concurrency-compare。

为什么要学

问题	LRU 回答
内存只能放 100 张图，第 101 张怎么办？	踢掉最久没看过的
Glide / 图片库底层思路？	内存层常是 LRU 或变种
`LinkedHashMap` 和 LRU 什么关系？	`accessOrder=true` 即可实现 LRU 核心逻辑

LRU 核心逻辑

text

访问 key → 把该条目移到「最近使用」端
容量满   → 从「最久未使用」端删除

可用 哈希表 + 双向链表 实现均摊 O(1)：

结构	作用
`HashMap<K, Node>`	key → 链表节点，O(1) 定位
双向链表	维护最近访问时间序；头 = 最久未用，尾 = 最近使用

算法题常考「手写 LRU」；工程里多用库实现。

Android `LruCache` 如何实现

类：android.util.LruCache<K, V>（Support 库时代同源，现 AndroidX 仍在 android.util）。

核心机制：

内部基于 LinkedHashMap，构造时 accessOrder = true（按访问排序，不是插入顺序）。
重写 entryRemoved：条目被移除时回调（可置空 Bitmap、打日志）。
重写 sizeOf(key, value)：默认每条算 1；图片缓存常返回 字节数，使 maxSize 表示 KB/MB 总量 而非个数。
trimToSize / evictAll：主动缩容或清空。

java

int maxBytes = 4 * 1024 * 1024; // 4MB
LruCache<String, Bitmap> cache = new LruCache<String, Bitmap>(maxBytes) {
    @Override
    protected int sizeOf(String key, Bitmap value) {
        return value.getByteCount();
    }

    @Override
    protected void entryRemoved(boolean evicted, String key,
            Bitmap oldValue, Bitmap newValue) {
        if (evicted && oldValue != null && !oldValue.isRecycled()) {
            oldValue.recycle(); // 按项目规范决定是否 recycle
        }
    }
};

cache.put("avatar", bitmap);
Bitmap hit = cache.get("avatar"); // get 会把条目标为「最近使用」

get 流程（简化）：

LinkedHashMap.get → 命中则链表调整顺序（最近使用）。
若 size() > maxSize，循环删除 最久未使用（LinkedHashMap 迭代顺序的头部）直到达标。

注意：LruCache 不是线程安全的；多线程访问需外部同步，或每线程/主线程专用实例。并发索引用 CHM，不要混为一谈。

Java `LinkedHashMap` 如何实现 LRU？

LinkedHashMap 在 HashMap 之外，额外维护一条 双向链表，把条目串成「使用顺序」。构造时第三个参数：

java

new LinkedHashMap<>(initialCapacity, loadFactor, accessOrder)

`accessOrder`	链表按什么排	能否当 LRU
`false`（默认）	插入顺序	❌ `get` 不会把条目挪到尾部
`true`	访问顺序（最久未用 → 最近使用）	✅ `get` / `put` 都会把该条移到「最近」端

removeEldestEntry 钩子：每次 put 插入新条目之后，JDK 会问子类：「要不要删掉当前最老的那条？」
在 accessOrder=true 时，「最老」= 最久没被 get/put 访问过的 key（链表头）。

java

LinkedHashMap<K, V> map = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > MAX_ENTRIES; // true → 删掉 eldest（最久未用）
    }
};

形象理解（容量 MAX = 3）

把链表想成一队人，左边最久没动，右边刚用过：

text

put A, B, C     →  A — B — C
put D（满）       →  踢 A → B — C — D
get B           →  B 到队尾 → C — D — B
put E（满）       →  踢 C（最左）→ D — B — E

put 新 key 时若 size > MAX，removeEldestEntry 返回 true，JDK 自动删除链表头 eldest，你不用手写 remove。

和 `LruCache` 的关系

LruCache 内部就是 accessOrder=true 的 LinkedHashMap + 在 put 后按 sizeOf 累加权重并循环淘汰，逻辑与上面相同，只是上限按字节而不是条数。

逐步打印验证：跑 cache-eviction-demo（含 get D×5 再 put F 场景）。

LRU 记的是「最近一次访问」，不是「访问次数」

策略	排序依据	`get` 读 1 次 vs 100 次
LRU	时间序：谁最久没被碰过	已在队尾时，效果相同（只更新「最近」位置一次）
LFU	次数：谁访问最少	每次 `get` 通常频率 +1，100 次更难被淘汰

所以 LRU 全称 Least Recently Used = 最久未使用（按最近一次访问时间排队），不是 Least Frequently Used。

续：剩 `D — B — E` 后狂读 `D`，再 `put F`？

text

起点           D — B — E
get D（第1次）   B — E — D        ← D 挪到队尾
get D（第2~N次） B — E — D        ← 已在队尾，不变
put F          踢 B → E — D — F   ← 踢链表头 B，不是 D

`LinkedHashMap` 内部：HashMap + 双向链表

LinkedHashMap 继承 HashMap，每个条目仍是 HashMap 的桶节点，但 LinkedHashMap.Entry 额外带两个指针：

text

HashMap 桶数组（按 hash 定位）
        │
        ▼
   Entry(key,value)  ←→  before / after  ←→  串成全局双向链表
        │
   （链表顺序 = accessOrder 时的「使用先后」）

字段 / 指针	作用
`HashMap` 的 `table[]`	按 hash 找桶，O(1) 定位 key
`before` / `after`	把所有 Entry 串成一条双向链表（与桶内链表是两套结构）
`head` / `tail`（链表哨兵）	`accessOrder=true` 时，迭代顺序：head 侧 = 最久未用，tail 侧 = 最近使用

get(key) 时 JDK 做什么（简化，对应 afterNodeAccess）：

text

1. HashMap 正常查找 → 找到 Entry 节点 e
2. 若 accessOrder == true：
   a. 把 e 从双向链表中摘下（改 e.prev.next、e.next.prev）
   b. 把 e 接到 tail 前面（变成「最近使用」）
3. 返回 value

put 新 key 且超容：插入新节点 → 调 removeEldestEntry(head侧最老节点) → 返回 true 则删掉该节点。

这与手写 LRU 的 unlink + linkBefore(tail) 完全同构，见 lab SimpleLruCache.java。

手写 LRU 核心方法（教学用）

java

void moveToTail(Node node) {
    unlink(node);           // 从当前位置摘下
    linkBefore(tail, node); // 接到队尾（最近使用）
}

完整可运行实现：SimpleLruCache.java。

注意：containsKey 不会触发 afterNodeAccess；只 get/put 等才算「使用」。用 containsKey 判断存在性不会给条目续命。

LFU 简单实现（对照 LRU）

LFU（Least Frequently Used） 在容量满时淘汰访问次数最少的条目；频率相同时，踢同频里最久未用的（LFU + 桶内 LRU tie-break，LeetCode 460 标准写法）。

核心逻辑

text

访问 key（get / 更新 put）→ 该 key 频率 +1，挪到更高频率的桶
容量满且插入新 key     → 从 minFreq 桶的链表尾删掉一个（次数最少 + 同频最久）

LRU 用一条双向链表排时间；LFU 用多条双向链表，按频率分桶：

结构	作用
`HashMap<K, Node>`（`keyTable`）	key → 节点，节点上带 `freq` 和 `prev`/`next`，O(1) 定位
`HashMap<Integer, FreqList>`（`freqTable`）	频率 f → 一条双向链表，链上全是 freq = f 的 key
`minFreq`	当前缓存里最小的频率；满员淘汰时只扫这一桶，不用遍历全表

text

keyTable:  A → Node(freq=4)   B → Node(freq=2)   C → Node(freq=1)

freqTable:
  freq=1  →  C — …              ← minFreq=1，满员新 key 从这桶尾踢
  freq=2  →  B — …
  freq=4  →  A — …

形象理解：一份节点，两张表（不是存了两份 A/B/C）

把每个缓存条目想成一张学员卡（Node），上面写着：key、value、freq（访问次数）、以及 prev/next（在「本班队列」里前后是谁）。

结构	比喻	实际存什么
`keyTable`	学号索引册：报学号立刻翻到那张卡	`HashMap<String, Node>`，key → 节点引用
`freqTable`	按「年级」分班：1 年级一班、2 年级一班…	`HashMap<Integer, FreqList>`，频率 → 该班的双向链表
`FreqList`	每个班门口一条队，有哨兵 `head`/`tail`	链表里挂的是 Node 引用，不是另拷一份 key 字符串

关键：keyTable 里的 Node@A 和 freq=4 队列里的那个 是同一个 Java 对象。链表只负责「这个频率档位内的先后顺序」；keyTable 负责 get("A") 时 O(1) 找到它。

接上例（get A×3、get B 之后），内存里大致是这样（←→ 表示双向链表）：

text

keyTable（按 key 查，O(1)）
  "A" ──→  Node{ key=A, value=1, freq=4, prev, next }  ←──┐
  "B" ──→  Node{ key=B, value=2, freq=2, prev, next }  ←──┼── 各出现一次，不重复 new
  "C" ──→  Node{ key=C, value=3, freq=1, prev, next }  ←──┘

freqTable（按频率分桶，每桶一条链）
  1 →  head ←→ [C 的 Node] ←→ tail        minFreq=1，满员踢 tail 前那个（此处是 C）
  2 →  head ←→ [B 的 Node] ←→ tail
  4 →  head ←→ [A 的 Node] ←→ tail
  （没有 freq=3 的桶 → freqTable 里根本没有 key=3 这一项）

对应代码里的类型（见 SimpleLfuCache）：

java

static class Node {
    final String key;
    String value;
    int freq;      // 当前访问次数，升频时改这个字段
    Node prev, next;  // 只表示「在当前频率桶的链」里的前后邻居
}

static class FreqList {
    final Node head = new Node("", "");  // 哨兵，不存真实数据
    final Node tail = new Node("", "");
    // head.next … tail.prev 之间串的都是真实 Node
}

get("A") 时发生了什么（对照 increaseFreq）：

text

1. node = keyTable.get("A")           // 索引册翻到 A 那张卡
2. 从 freq=4 的链上 unlink(node)      // A 先离开「4 年级」队列（改 prev/next）
3. node.freq = 5
4. freqTable[5].addToHead(node)       // A 挂到「5 年级」队列头部（本档里算最新用过）
5. 若 freq=4 的桶空了 → 删掉 freqTable[4]，且若 minFreq 曾是 4 则 minFreq++

满员 put("D") 时：

text

1. list = freqTable.get(minFreq)      // minFreq=1 → 进「1 年级」队列
2. evicted = list.removeEldest()      // 取 tail.prev，即 C 那张 Node（同频里最久未用）
3. keyTable.remove("C")               // 索引册删掉 C；C 的 Node 对象不再被任何地方引用
4. new Node("D") → keyTable + freq=1 桶头，minFreq=1

和 LRU 的类比：LRU 是全班只有一条时间队列；LFU 是多条队列，按 freq 分班，再加一个 minFreq 记住「当前人数最少、且非空的是哪一班」，满员只去那一班队尾踢人。

桶内链表约定与 LRU 相同：头侧 = 该频率下最久未用，尾侧 = 该频率下最近用过（升频时 addToHead，淘汰时 removeEldest 取 tail.prev）。

举例（容量 MAX = 3）

与 lab SimpleLfuCache.java 主流程一致：

text

put A, B, C           →  三人 freq 均为 1，minFreq=1
                        freq=1: C — B — A（尾为最近 put）

get A ×3              →  A 升到 freq=4
                        freq=1: C — B    freq=4: A

get B                 →  B 升到 freq=2
                        freq=1: C        freq=2: B    freq=4: A

put D（满，插新 key）  →  从 minFreq=1 的桶踢 → 只剩 C 是 freq=1 → 踢 C，不是 A
                        再 put D，D.freq=1，minFreq 重置为 1

要点：A 虽然被 get 了很多次，但 B、C 没动时 C 仍停在 freq=1；新 key 进来先比频率（minFreq），不比「谁最近被读过」。若 B、C 都是 freq=1，则踢同频链表头侧最久未用的那个。

`increaseFreq` 与满员淘汰（简化）

text

increaseFreq(node):
  1. 从 freq=oldFreq 的链表中 unlink
  2. 若该桶空了：删掉 freqTable[oldFreq]；若 oldFreq == minFreq，则 minFreq++
  3. node.freq = oldFreq + 1，挂到 freq=(oldFreq+1) 桶的头部

put 新 key 且 size >= capacity:
  1. evicted = freqTable.get(minFreq).removeEldest()  // 同频 LRU
  2. keyTable.remove(evicted.key)
  3. 新节点 freq=1 入桶，minFreq = 1

均摊 O(1) 的关键是维护 minFreq：升频时若最小频率桶变空，minFreq 只能 +1（不会出现比当前更小、且仍非空的频率）。

完整可运行实现：SimpleLfuCache.java。

LFU 与 LRU+LFU 混合：有没有现成的？推荐吗？

策略	淘汰谁	现成实现	推荐场景
LRU	最久未访问	`LinkedHashMap`、`LruCache`、Guava Cache（旧）	Android 图片内存、近期热点
LFU	访问次数最少	Redis `allkeys-lfu`、手写 / cache-eviction-demo	长期热门 key、抗扫描
LFU + 同频 LRU	先比频率，同频踢最久未用	LeetCode 460 标准写法、本仓库 `SimpleLfuCache`	理解 LFU；中等复杂度
W-TinyLFU	窗口 LRU + 频率素描准入	Caffeine（Java 服务端首选）	高 QPS 本地缓存，比纯 LRU 命中率高
Redis 组合	可配 `volatile-lru` 等	运维层	分布式缓存

二者结合有没有？ 有，而且工程上很常见，只是不叫「LRU+LFU 简单相加」：

LFU 桶内 LRU（本 lab SimpleLfuCache）：频率相同则踢最久未用——同时用到次数和时间。
W-TinyLFU（Caffeine）：新条目先进小窗口 LRU；进主缓存前用 TinyLFU 频率素描 和被淘汰候选比一比，低频的一次性访问进不来（防扫描污染）。
不推荐在 Android 业务里自研 W-TinyLFU；图片缓存继续 LruCache / Glide 即可。服务端 JVM 缓存优先考虑 Caffeine。

LFU Demo：同 lab cache-eviction-demo · SimpleLfuCache.java

类似概念与选型

策略 / 产品	淘汰依据	特点	常见场景
LRU	最久未访问	实现简单、命中近期热点	图片内存、`LruCache`
LFU	访问次数最少	抗偶发扫描更好，实现稍复杂	长期热点、CDN 变种
FIFO	最早进入	不看是否再次访问	简单队列缓存
TTL / 过期时间	写入后固定时长	与 LRU 正交，常组合	接口缓存、配置
`DiskLruCache`（Jake Wharton）	磁盘版 LRU，journal 日志	图片库二级缓存	OkHttp 早期生态、自研磁盘缓存
Glide	内存 `LruResourceCache` + 磁盘 LRU	框架封装	Android 图片加载
Caffeine（Java）	W-TinyLFU 等	比纯 LRU 命中率高	服务端本地缓存
Redis	`maxmemory-policy`	`allkeys-lru` / `lfu` 等可配	分布式缓存

LRU 的弱点：一次大范围扫描会把冷数据全挤进缓存，把热数据踢掉（缓存污染）。LFU、W-TinyLFU 等是为缓解这个问题。

LRU vs CHM vs HashMap（别混）

	目的	线程安全	容量
`HashMap`	通用字典	❌	无自动淘汰
`ConcurrentHashMap`	并发字典、索引	✅ 单次 API	无自动淘汰
`LruCache`	有上限的缓存	❌（需自行同步）	自动 LRU 淘汰
`LinkedHashMap` + `removeEldestEntry`	JVM 层 LRU 字典	❌	可设上限

Android 实战注意

sizeOf 必须反映真实内存（Bitmap 字节、对象估算），否则 maxSize 名存实亡。
不要在 LruCache 里放 Activity Context 引用的超大对象 而不设上限——仍可能 OOM。
磁盘 + 内存二级缓存：内存 LruCache，磁盘 DiskLruCache 或 SQLite/文件 + 自己的索引。
协程/多线程：对同一 LruCache 加锁，或限制在单线程访问。

复习检查题

LRU 淘汰的是哪一类条目？
答：最久未被访问（get/put 算访问）的条目，不是最早 put 进来的（那是 FIFO，除非从未再访问）。
LruCache 为什么用 LinkedHashMap 且 accessOrder=true？
答：哈希表保证 O(1) 查找；双向链表维护访问顺序，accessOrder=true 使 get 后把节点移到「最近」端，超容时从「最久」端删除，正好对应 LRU。
LruCache 的 maxSize 和 sizeOf 有什么关系？
答：内部累加每次 put 的 sizeOf(key,value)，超过 maxSize 就淘汰最久未用条目直到 ≤ maxSize。只设 maxSize 不重写 sizeOf 时，按条目个数计。
图片缓存用 CHM 还是 LruCache？为什么？
答：应用层图片内存缓存优先 LruCache（或 Glide 等封装），因为有容量上限与自动淘汰。CHM 适合多线程 key→value 索引 且无内置 LRU；要自己写淘汰逻辑。
LRU 和 LFU 对「同一 key 连续 get 100 次」反应有何不同？
答：LRU 在 key 已到队尾后，再多 get 不改变相对顺序，只表达「最近用过」。LFU 每次 get 通常 频率 +1，该 key 更难被淘汰。LRU 比时间，LFU 比次数。
想要「又看最近又看热度」，工程上怎么办？
答：Android 图片层继续 LRU/LruCache 即可。Java 服务端本地缓存优先 Caffeine（W-TinyLFU）；Redis 按 workload 选 allkeys-lru 或 allkeys-lfu。手写可用 LFU + 同频 LRU（见 SimpleLfuCache），不必在 App 里自研 TinyLFU。

速记

LRU = 按最近一次访问时间；踢链表头（最久未用），不是按次数。
LinkedHashMap = HashMap + before/after 双向链表；get → afterNodeAccess 挪到 tail。
手写 LRU：unlink + linkBefore(tail)；见 SimpleLruCache。
LFU = keyTable + freq 分桶链表 + minFreq；满员踢 minFreq 桶尾（同频 LRU）。
LFU 工程选型见 Caffeine（W-TinyLFU）；手写见 SimpleLfuCache。
LruCache = LinkedHashMap(accessOrder) + sizeOf；并发索引用 CHM。

LRU 缓存与淘汰策略（含 LruCache） ​

一句话定义 ​

为什么要学 ​

LRU 核心逻辑 ​

Android LruCache 如何实现 ​

Java LinkedHashMap 如何实现 LRU？ ​

形象理解（容量 MAX = 3） ​

和 LruCache 的关系 ​

LRU 记的是「最近一次访问」，不是「访问次数」 ​

续：剩 D — B — E 后狂读 D，再 put F？ ​

LinkedHashMap 内部：HashMap + 双向链表 ​

手写 LRU 核心方法（教学用） ​

LFU 简单实现（对照 LRU） ​

核心逻辑 ​

形象理解：一份节点，两张表（不是存了两份 A/B/C） ​

举例（容量 MAX = 3） ​

increaseFreq 与满员淘汰（简化） ​

LFU 与 LRU+LFU 混合：有没有现成的？推荐吗？ ​

类似概念与选型 ​

LRU vs CHM vs HashMap（别混） ​

Android 实战注意 ​

复习检查题 ​

速记 ​

LRU 缓存与淘汰策略（含 LruCache）

一句话定义

为什么要学

LRU 核心逻辑

Android `LruCache` 如何实现

Java `LinkedHashMap` 如何实现 LRU？

形象理解（容量 MAX = 3）

和 `LruCache` 的关系

LRU 记的是「最近一次访问」，不是「访问次数」

续：剩 `D — B — E` 后狂读 `D`，再 `put F`？

`LinkedHashMap` 内部：HashMap + 双向链表

手写 LRU 核心方法（教学用）

LFU 简单实现（对照 LRU）

核心逻辑

形象理解：一份节点，两张表（不是存了两份 A/B/C）

举例（容量 MAX = 3）

`increaseFreq` 与满员淘汰（简化）

LFU 与 LRU+LFU 混合：有没有现成的？推荐吗？

类似概念与选型

LRU vs CHM vs HashMap（别混）

Android 实战注意

复习检查题

速记