操作流程#

get(key)：哈希表找到节点 → 把节点移到链表头部 → 返回值。如果没找到，返回 -1。

put(key, value)：

• key 已存在：更新值 → 移到链表头部
• key 不存在：创建新节点插到链表头部 → 哈希表记录映射 → 如果超容量，删除链表尾部节点（最久未用）→ 同时删除哈希表中对应条目

复杂度#

双向链表之所以比单向链表关键，是因为删除节点需要知道前驱节点。单向链表找前驱要 O(n)，双向链表直接 O(1)。

扫描抗性问题#

LRU 有一个经典弱点：扫描破坏。假设缓存容量 100，已经装满热点数据。一个爬虫依次访问了 200 个冷页面，每个页面只访问一次。LRU 会把所有热点条目逐个挤走，缓存里最后只剩下 100 个再也不会被访问的冷页面。这就是「一次扫描毁掉全部热点」。

解决方案：

• LRU-K：要求被访问 K 次才进入 LRU 链表，过滤掉一次性扫描
• ARC（Adaptive Replacement Cache）：同时维护最近条目和频繁条目两个链表，自动调整比例
• Redis 近似 LRU：随机采样 N 个 key，淘汰其中最久未用的，避免维护全局链表

Redis 的近似 LRU#

Redis 没有给每个 key 维护双向链表指针——那要多花 16 字节（两个 64 位指针）per key。它用的是近似 LRU：

1. 每个 key 头部有一个 24 位的 lru_clock 字段，记录最后一次访问时间（精度约 1.6 秒）
2. 需要淘汰时，随机采样 maxmemory-samples 个 key（默认 5），选 idle 时间最长的淘汰
3. 采样 10 个 key 的效果已经接近精确 LRU，但省掉了全局链表的开销

这种「用随机采样换精确排序」的思路，在分布式系统中很常见——用少量随机性换取可观的内存节省。

Go（使用 container/list）#

Go 标准库的 container/list 就是双向链表，配合 map 即可实现 LRU：

1
package lru
2

3
import "container/list"
4

5
type entry struct {
6
    key   string
7
    value any
8
}
9

10
type Cache struct {
11
    capacity int
12
    items    map[string]*list.Element
13
    order    *list.List
14
}
15

16
func New(capacity int) *Cache {
17
    return &Cache{
18
        capacity: capacity,
19
        items:    make(map[string]*list.Element),
20
        order:    list.New(),
21
    }
22
}
23

24
func (c *Cache) Get(key string) (any, bool) {
25
    if elem, ok := c.items[key]; ok {
26
        c.order.MoveToFront(elem) // 访问后移到头部
27
        return elem.Value.(*entry).value, true
28
    }
29
    return nil, false
30
}
31

32
func (c *Cache) Put(key string, value any) {
33
    if elem, ok := c.items[key]; ok {
34
        c.order.MoveToFront(elem)
35
        elem.Value.(*entry).value = value
36
        return
37
    }
38
    // 新条目插入头部
39
    elem := c.order.PushFront(&entry{key: key, value: value})
40
    c.items[key] = elem
41
    // 超容量则淘汰尾部
42
    if c.order.Len() > c.capacity {
43
        oldest := c.order.Back()
44
        c.order.Remove(oldest)
45
        delete(c.items, oldest.Value.(*entry).key)
46
    }
47
}

container/list 的 MoveToFront、PushFront、Back、Remove 都是 O(1) 操作。链表节点里存了 key，是为了淘汰时能反向删除哈希表条目——这是 LRU 实现中容易遗漏的细节。

TypeScript（利用 Map 的插入顺序）#

JavaScript 的 Map 会按插入顺序迭代。利用这个特性，可以用 delete + 重新 set 来模拟「移到头部」：

1
class LRUCache<K, V> {
2
  private capacity: number;
3
  private cache: Map<K, V>;
4

5
  constructor(capacity: number) {
6
    this.capacity = capacity;
7
    this.cache = new Map();
8
  }
9

10
  get(key: K): V | undefined {
11
    if (!this.cache.has(key)) return undefined;
12
    // 删除再插入，移到迭代顺序末尾（即"最近"端）
13
    const value = this.cache.get(key)!;
14
    this.cache.delete(key);
15
    this.cache.set(key, value);
16
    return value;
17
  }
18

19
  put(key: K, value: V): void {
20
    if (this.cache.has(key)) {
21
      this.cache.delete(key); // 已存在则先删除
22
    } else if (this.cache.size >= this.capacity) {
23
      // 淘汰最久未用：迭代器的第一个元素即最早插入的
24
      const oldest = this.cache.keys().next().value;
25
      this.cache.delete(oldest);
26
    }
27
    this.cache.set(key, value);
28
  }
29
}

Map 的 keys() 迭代器按插入顺序遍历，第一个就是最久没更新的条目。delete + set 把条目移到末尾，末尾就是「最近」端。这个实现不需要手写链表，但 delete + set 涉及两次哈希表操作，比原生双向链表的指针操作稍慢。在大多数业务场景下，这点差异可以忽略。

Go groupcache LRU#

Brad Fitzpatrick（memcached 创始人）在 groupcache 中实现了一个精简的 LRU 缓存，代码不到 100 行。它用 container/list + map 的经典组合，OnEvicted 回调支持淘汰时的资源清理。

• 项目：golang/groupcache
• 用途：groupcache 是一个分布式缓存库，LRU 用于单个节点的本地缓存淘汰

Redis 近似 LRU 淘汰#

Redis 没有使用精确 LRU，而是用随机采样实现近似 LRU。evict.c 中的 evictionPoolPopulate 函数随机采样 N 个 key，按 idle 时间排序后选出最佳淘汰候选。默认采样 5 个 key，调到 10 就能接近精确 LRU 的效果。

• 项目：redis/redis
• 用途：Redis 内存达到 maxmemory 限制时的 key 淘汰策略

Linux 内核页面置换#

Linux 内核的页面置换也用了 LRU 的变体。它维护 active 和 inactive 两个链表（类似 ARC 的思路），页面在 inactive 链表被再次访问时晋升到 active 链表，active 链表末尾的页面降级回 inactive。这种双链表设计天然抗扫描——一次性扫描的页面只会进入 inactive 链表，不会挤走 active 链表的热点。

• 项目：torvalds/linux
• 用途：物理内存页面的换入换出决策

何时使用 LRU 缓存#

• 数据库查询缓存：热点 SQL 结果集缓存，避免重复查询
• DNS 解析缓存：域名到 IP 的映射，近期访问的域名大概率再访问
• 浏览器资源缓存：HTTP 响应、图片、JS/CSS 文件，最近浏览的页面资源优先保留
• API 响应缓存：高频接口的返回值缓存，降低后端压力
• OS 页面/目录项/索引节点缓存：内核的 dentry cache 和 inode cache 都基于 LRU 变体

何时不要使用 LRU 缓存#

• 扫描密集型负载：爬虫、全表扫描等一次性遍历会冲掉所有热点，改用 LRU-K 或 ARC
• 需要按时间过期：LRU 只管访问顺序，不管 TTL。如果需要「超过 10 分钟自动失效」，要在 LRU 之上加 TTL 层
• 访问频率比访问时序更重要：少数条目被高频访问、大量条目偶尔访问时，LFU 保留热点更稳定
• 不需要淘汰策略：数据量可控、内存充裕时，简单哈希表就够了，不必引入 LRU 的复杂度