Golang怎么实现LRU缓存淘汰算法_Golang如何用双向链表加map构建本地缓存【进阶】-Golang-PHP中文网

因为标准库无内置lru，第三方包依赖重、泛型支持弱、淘汰逻辑难定制；手写可精准控制键值类型、过期行为、并发粒度，并支持结构体键、sync.map配合、remove回调等场景。

golang怎么实现lru缓存淘汰算法_golang如何用双向链表加map构建本地缓存【进阶】

为什么不用现成的 `lru` 包，而要自己写？

因为标准库没有内置 LRU，第三方包（比如 github.com/hashicorp/golang-lru）虽好，但依赖引入、泛型支持弱、定制淘汰逻辑困难。自己实现能精准控制键值类型、过期行为、并发安全粒度，也方便嵌入监控或打点。

真正需要手写的情况：缓存键不是字符串而是结构体；要和 sync.Map 配合做无锁读；或者想在 Remove 时触发回调（比如落盘或通知）。

常见错误是直接用 map + 切片模拟顺序——delete 和 append 会导致 O(n) 时间复杂度，一压就慢。

怎么用 `list.List` + `map` 实现 O(1) 操作？

list.List 是 Go 标准库的双向链表，但它的 Element.Value 是 interface{}，必须自己封装键值对结构；map 存的是 *list.Element，不是值本身——这是最容易漏掉的关键点。

实操建议：

定义缓存项结构体，包含 key、value 字段，避免反复类型断言
map 的 value 类型必须是 *list.Element，否则每次 Get 后无法快速移到链表头
插入新元素时，先 list.PushFront，再把返回的 *list.Element 写进 map，顺序不能反
淘汰最久未用项时，从 list.Back() 取，再从 map 中用对应 key 删除，两步缺一不可

示例关键片段：

type entry struct {
    key   string
    value interface{}
}
type LRUCache struct {
    list *list.List
    m    map[string]*list.Element // 注意 value 是 *list.Element
    cap  int
}

并发安全怎么加？锁粒度选 `sync.RWMutex` 还是 `sync.Mutex`？

读多写少场景下，用 sync.RWMutex 能提升吞吐，但注意：只要涉及 list.MoveToFront 或 list.Remove，就必须用写锁——因为这些操作会修改链表结构，哪怕只是“移动”，sync.RWMutex 的读锁也不够。

Golang Stay Updated

提供最新的 Golang 新闻、社群和值得关注的人。适用于寻找 Go 学习资源、发现新库等。

下载

所以实际没法只用读锁保护 Get。更现实的做法是：所有公开方法（Get/Put/Remove）都用 sync.Mutex，简单可靠。若真有高并发读需求，可考虑分片（shard），比如按 key 哈希到 8 个独立 LRU 实例 + 8 把锁。

容易踩的坑：

在 Get 中只加读锁，然后调 list.MoveToFront → panic: “concurrent map read and map write” 或链表损坏
把 sync.Mutex 放在结构体字段里却忘了导出（首字母小写），导致外部无法 lock
在 Put 里先删旧 entry 再插新 entry，中间没锁住，被其他 goroutine 插入打断