不能直接用 container/list 实现 LRU,因为 *list.Element 缺少 key 字段,导致 map 与链表节点脱节,Get 时需 O(n) 遍历查找,破坏 LRU 的 O(1) 时间复杂度;正确做法是自定义节点结构,内含 key、value 和指针,并确保 map 存储节点指针,淘汰时同步清理 map 和链表引用。

为什么不能直接用 container/list 拼 LRU?
因为 container/list 的 *list.Element 不带 key 字段,map[key]value 和链表节点完全脱节。每次 Get 都得遍历链表找对应节点——时间复杂度变成 O(n),直接废掉 LRU 的核心价值。
常见错误写法:
cache := make(map[string]interface{})
list := list.New()
// Put 时只往 map 写值、往 list.PushFront 写副本
// Get 时从 map 取值,但根本没法把 list 里对应节点移到头 —— 因为不知道它在哪
真正要的是:哈希表值直接存指向自定义节点的指针,节点里自带 key、value、prev、next 字段。
Put 时怎么避免内存泄漏和重复 alloc?
缓存满后淘汰尾节点,必须同步清理两处引用:map 中的 key 和链表中的节点。Go GC 不会自动回收仍被 *list.Element 持有的节点,哪怕它已从 map 删除。
立即学习“go语言免费学习笔记(深入)”;
- 淘汰前先取尾节点的
key,再delete(cacheMap, key) - 接着调用
list.Remove()或手动解链(如果不用container/list) - 不要复用旧
node实例(比如清空字段重塞),容易引发并发错乱或 stale pointer;new(node)更安全 - 如果节点结构里嵌了
*list.Element(如某些 wrapper 实现),记得在淘汰时也置空其Value字段,防止悬挂引用
如何让 Get 和 Put 并发安全又不锁死?
读多写少场景下,全量 sync.Mutex 会成为瓶颈;但 sync.RWMutex 也不能无脑读锁——因为 Get 后要 MoveToFront,本质是写操作。
实操建议:
-
Get:先Rlock()查 map,拿到节点指针后立即RUnlock();再单独Lock()做moveToHead(只改指针,不碰 value) -
Put:全程Lock(),但临界区只做 map 更新 + 链表指针重连;value 赋值放在锁外 - 千万别在锁里调用用户传入的
OnEvict回调,否则可能卡住整个缓存
带过期时间的 LRU 为什么别自己扫定时器?
为每个 key 启一个 time.AfterFunc 或开 goroutine 扫全量 map,在高并发下会迅速耗尽 goroutine 和 timer 资源。更糟的是,系统时钟被 NTP 调整时,大量 time.Time 过期判断会集体失准。
推荐惰性检查:
- value 类型内嵌
expireAt time.Time字段(如struct{ Data interface{}; ExpireAt time.Time }) -
Get时用time.Now().After(item.ExpireAt)判断,过期就当 key 不存在,返回 false -
Put只更新ExpireAt,不主动删;让 LRU 容量机制自然淘汰过期项(它们反正也不会被访问)
真正难处理的不是逻辑,而是时钟漂移和并发下的过期判定时机——Get 时判一次最轻量,也最可控。


















