Go 怎么用双向链表实现固定容量 LRU 缓存

如果缓存只用一个 map，可以很快找到 key，却不知道谁最久没被访问；如果只用链表，又要在线性时间里查找 key。Go 实现固定容量 LRU（Least Recently Used）的常见组合是 map[string]*list.Element 加 container/list：map 负责定位，双向链表负责顺序。本文约定链表头是“最近使用”，尾部是“最久未使用”，每次命中或写入都把节点移到头部。

核心做法是让 map 指向链表节点：Get 命中时 MoveToFront，Put 新增时 PushFront，超出容量时删除 Back，并同步删除 map 中的 key。这样查找、更新顺序和淘汰都能保持 O(1)。

先把 map 定位和链表顺序分开

container/list 是标准库提供的双向链表。Front、Back 返回两端节点，MoveToFront 可以在已知节点指针时调整顺序，Remove 删除节点。LRU 不应该把业务对象直接放进 map，而是让 map 指向 list.Element，这样命中后不用再次扫描链表。

用固定容量封装 Get 和 Put

下面的实现故意保持单线程语义，适合先理解数据结构。容量为 0 时，Put 不保存；已有 key 再写入时只更新值并移动到头部。淘汰时先读出尾节点里的 key，再调用链表删除，最后删掉 map 项。

package lru

import "container/list"

type entry struct {
	key   string // 删除尾节点时需要用 key 清理 map
	value string // 示例使用字符串值，业务中可替换为具体类型
}

type Cache struct {
	capacity int
	items    map[string]*list.Element // key 到链表节点的 O(1) 索引
	order    *list.List                // 头部最近使用，尾部最久未使用
}

func New(capacity int) *Cache {
	return &Cache{
		capacity: capacity,
		items:    make(map[string]*list.Element), // 预留索引容器
		order:    list.New(),                     // 创建已初始化的双向链表
	}
}

func (c *Cache) Get(key string) (string, bool) {
	e, ok := c.items[key]
	if !ok {
		return "", false // map 未命中，不改变顺序
	}
	c.order.MoveToFront(e) // 命中即变成最近使用
	return e.Value.(entry).value, true // Element.Value 取回业务值
}

func (c *Cache) Put(key, value string) {
	if c.capacity 

这里的 Element.Value 是 any，所以断言类型必须和写入时一致。生产代码若需要泛型，可以把 key、value 放到自定义节点里，或使用泛型封装，但仍要保持 map 与链表节点的一一对应。

容量边界和更新路径要各自验证

容量为 2 时依次写入 A、B，顺序是 B → A；再读取 A，顺序变成 A → B；写入 C 后删除 B，最终是 C → A。这个小例子能覆盖新增、命中移动和尾部淘汰三条路径。覆盖已有 key 时不要调用 PushFront，否则 map 仍指向旧节点，长度也会虚增。

还要注意 Back() 可能返回 nil。只要先处理容量小于等于 0，并且每次新增后才在超限分支取尾节点，就不会对空指针做 Value 访问。

并发使用时补上锁，而不是误以为 list 自带安全

map 和 container/list 的这组操作需要作为一个整体保持一致。多个 goroutine 同时调用 Get 与 Put 时，应在 Cache 中增加 sync.RWMutex 或 sync.Mutex，并让读命中时移动链表的操作使用写锁；因为 LRU 的 Get 并不是纯读操作。若缓存值还要设置过期时间，应额外记录时间并明确“过期优先还是容量淘汰优先”的策略。

常见问题

为什么不用 slice 保存访问顺序？

slice 查找和中间删除通常要移动元素，命中后维护顺序不是 O(1)。map 加双向链表更适合固定容量 LRU。

删除节点后还能从 map 找到它吗？

不能保留旧索引。淘汰必须同时执行 Remove 和 delete，否则 map 会留下指向已脱离链表节点的条目。

Get 为什么也需要写锁？

因为命中后要调用 MoveToFront 改变链表结构；并发版本不能把它当成只读查询。