Go list 怎样维护 LRU 访问顺序

如果缓存只需要按插入顺序排队，切片就够了；但 LRU 要记录“最近一次访问”。Go 里最稳妥的做法是把 map[string]*list.Element 和 container/list 组合起来：map 负责按 key 找节点，双向链表负责维护新旧顺序。每次命中调用 MoveToFront，容量超限时移除 Back，这样定位和移动都不需要遍历整个缓存。

先把 map 和 list 的职责分开

container/list 是标准库双向链表。它的 MoveToFront、MoveToBack 和 Remove 都围绕已经存在的 *list.Element 操作，所以不能只维护一个 key 到 value 的 map：还需要把每个 key 对应的链表节点保存下来。

下面这个小项目用字符串做 key 和 value。链表中存的是 entry，map 中存的是该 entry 所在的节点。这样不会为了找到一个命中项从 Front 循环到 Back。

用一个小项目实现 Get 和 Put

缓存结构只需要容量、链表和索引三项状态。Get 查到节点后先移动，再返回值；Put 遇到旧 key 时更新节点里的 value，并同样移动到队首。

package main

import (
    "container/list"
    "fmt"
)

type entry struct {
    key, value string
}

type LRU struct {
    capacity int
    items    map[string]*list.Element
    order    *list.List
}

func NewLRU(capacity int) *LRU {
    // 负数容量没有实际意义，统一按零容量处理。
    if capacity  c.capacity {
        // 队尾是最久未访问项，Remove 返回被删除的 entry。
        oldest := c.order.Back()
        removed := c.order.Remove(oldest).(entry)
        delete(c.items, removed.key)
    }
}

func (c *LRU) Keys() []string {
    // 从 Front 到 Back 输出，便于观察访问顺序。
    keys := make([]string, 0, c.order.Len())
    for element := c.order.Front(); element != nil; element = element.Next() {
        keys = append(keys, element.Value.(entry).key)
    }
    return keys
}

func main() {
    cache := NewLRU(2)
    cache.Put("a", "A")
    cache.Put("b", "B")
    _, _ = cache.Get("a")
    cache.Put("c", "C")
    fmt.Println(cache.Keys()) // [c a]；b 因最久未访问被淘汰
}

这个实现的关键不是 PushFront 本身，而是“每个 key 只绑定一个 Element”。更新旧 key 时复用节点，避免同一个 key 在链表中出现两次；淘汰后同时删除链表节点和 map 索引，避免留下失效指针。

把命中移动和淘汰写成两个动作

以容量 2 的缓存为例，先放入 a、b，顺序是 b → a。再次读取 a 后，a 变成最近使用项，顺序变为 a → b。此时放入 c，新节点进入队首，队尾的 b 被移除，结果是 c → a。

运行与验收时看什么

把代码放进一个 Go module 后运行即可。验收不要只看最后一行，要按动作记录顺序：命中后被访问的 key 必须到 Front；新增 key 后，Back 才是候选淘汰项；更新旧 key 不能让 Len() 增长。

# 创建一个独立目录并初始化 Go module
mkdir go-lru-demo
cd go-lru-demo
go mod init example.com/go-lru-demo
# 将上面的 main.go 保存后运行
go run .

预期输出是 [c a]。它只说明这个示例的顺序维护符合 LRU 规则，不代表缓存已经具备持久化、并发安全或淘汰回调。

容量、并发和类型断言的边界

容量为零时直接丢弃写入，能减少一次无意义的插入和删除。并发场景下，标准库 list.List 和上面的 map 都没有替你加锁；如果多个 goroutine 同时读写，应在 LRU 外层使用 sync.Mutex 或把锁放进结构体，并让 Get、Put、Keys 的临界区保持一致。

Element.Value 的类型是 any。本文所有节点都写入 entry，所以类型断言成立；如果项目里允许混放不同类型，应该改成统一的节点类型或检查断言结果，不要把 panic 当成缓存未命中的处理方式。另一个常见边界是外部代码不能把别的 list 创建的 Element 传给 MoveToFront，标准库会忽略不属于当前链表的节点，但调用方仍应维护好节点所有权。

相关问题

为什么不能只用 map 实现 LRU？

map 擅长按 key 定位，但不记录访问先后。没有链表或其他有序结构，淘汰最久未用项就需要额外扫描或维护复杂的排序状态。

Get 未命中时要不要修改访问顺序？

通常不修改。未命中没有对应 Element，保持顺序可以让 LRU 状态只反映真实存在的缓存项。

更新已有 key 后为什么也要 MoveToFront？

Put 本身代表一次使用或刷新。如果更新不移动，刚写入的项目仍可能停留在队尾，下一次淘汰会违背“最近使用”的定义。