Go container/list.MoveToFront 怎么实现最近使用顺序

要用 container/list.MoveToFront 实现最近使用顺序，最实用的结构不是单独一条链表，而是把 map[K]*list.Element 和双向链表组合起来：map 负责按键找到节点，list 负责记录使用先后。约定链表头 Front 是最近使用项（MRU），链表尾 Back 是最久未使用项（LRU）。命中缓存时，对已有节点调用 MoveToFront 即可。

核心思路：map 找节点，list 管顺序

只用链表时，虽然能从头到尾表达先后顺序，但按 key 查找节点需要遍历；只用 map 时，又没有稳定的最近使用顺序。把两者组合后，map 直接保存链表节点指针，命中时无需重新创建节点，也无需扫描链表。

• 缓存命中：从 map 取得 *list.Element，再调用 MoveToFront。
• 缓存新增：调用 PushFront，并把返回的节点保存到 map。
• 超过容量：读取 Back，同时从 map 和 list 删除该项。
• 更新已有 key：改写节点中的值，然后移动到链表头，不能再次 PushFront。

这里最重要的不变式是：map 中每个 key 恰好对应 list 中一个节点。若命中时再次插入新节点，同一个 key 就会在链表里出现多份，后续淘汰会删除错误的映射。

完整实现：一个可直接使用的 LRU 缓存

下面使用泛型实现一个固定容量缓存。container/list.Element.Value 的类型是 any，因此节点中保存私有的 entry[K, V]，取值时再做类型断言。map 与链表由同一把互斥锁保护，保证每次操作看到的是一致状态。

package lru

import (
	"container/list"
	"sync"
)

// entry 同时保存淘汰时需要删除的 key 和业务值。
type entry[K comparable, V any] struct {
	key   K
	value V
}

// Cache 使用 map 定位节点，使用双向链表维护最近使用顺序。
type Cache[K comparable, V any] struct {
	mu    sync.Mutex
	cap   int
	order *list.List
	items map[K]*list.Element
}

// NewCache 创建固定容量缓存；容量必须为正数。
func NewCache[K comparable, V any](capacity int) *Cache[K, V] {
	if capacity  c.cap {
		oldest := c.order.Back()
		oldItem := oldest.Value.(*entry[K, V])
		delete(c.items, oldItem.key)
		c.order.Remove(oldest)
	}
}

// Len 返回当前缓存项数。
func (c *Cache[K, V]) Len() int {
	c.mu.Lock()
	defer c.mu.Unlock()
	return c.order.Len()
}

查找由 map 完成；顺序调整不遍历链表，而是重连已有 Element。淘汰时必须先从尾节点取出 key，再同时执行 delete 和 Remove。两边少删任何一处，都会破坏一一对应关系。

MoveToFront 的调用边界

Go 标准库文档说明，MoveToFront(e) 会把元素 e 移到链表头；如果 e 不是当前链表的元素，链表保持不变；e 不能为 nil。标准库源码还对“e 已经位于头部”的情况直接返回。因此实践中应遵守以下边界：

1. 只把当前缓存 map 中取出的节点传给当前缓存的 list。
2. 不要向 MoveToFront 传 nil；map 未命中时应直接返回。
3. 不要把 *list.Element 暴露给调用方，否则外部容易混用不同链表的节点。
4. 命中与更新都移动已有节点，而不是删除后再插入新节点。

Go 标准库文档：https://pkg.go.dev/container/list

调用示例：谁会被淘汰

package main

import "fmt"

func main() {
	cache := NewCache[string, int](2)
	cache.Put("a", 1) // 最近顺序：a
	cache.Put("b", 2) // 最近顺序：b, a

	cache.Get("a")    // 命中 a，顺序变为：a, b
	cache.Put("c", 3) // 超容量，淘汰尾部的 b

	_, exists := cache.Get("b")
	fmt.Println(exists) // false
}

关键点在于 Get("a") 不只是读取值，还会改变顺序。随后插入 c 时，链表尾部已经是 b，所以 b 被淘汰。若读取操作忘记调用 MoveToFront，实现出来的就不是 LRU。

并发场景为什么要锁住整个组合操作

container/list 本身不负责业务层并发协调，而一次 LRU 操作通常会同时读写 map 与 list。例如 Put 新增时需要先插入链表、再写 map，超容量还要继续删除两边。锁若只保护其中一个容器，其他 goroutine 可能看到“map 已有节点但链表尚未就绪”之类的中间状态。

因此示例用一把 sync.Mutex 覆盖整个 Get、Put 和 Len 操作。即使 Get 看起来是读取，它也会调用 MoveToFront 修改链表，所以不能简单使用读锁。若后续要做分片缓存或降低竞争，也应先保证每个分片内部仍维护同样的不变式。

常见错误清单

• 命中后 PushFront：会产生重复 key；应复用 map 中的 Element。
• 只 Remove 不 delete：map 留下已经脱离链表的节点指针。
• 只 delete 不 Remove：链表里留下无法通过 map 找到的孤儿节点。
• 把 Back 当最近使用：顺序语义反了，淘汰结果也会相反。
• Get 不加锁：Get 会调整链表，不是纯只读操作。

归纳起来，MoveToFront 只负责“把已知节点挪到头部”，真正完整的最近使用顺序需要 map、list、容量淘汰和并发边界共同配合。始终维护“map 与 list 一一对应、Front 为 MRU、Back 为 LRU”，实现就会清晰且不易出错。