LRU 缓存实现：先把链表原语和边界条件写清楚

LRU 缓存实现：先把链表原语和边界条件写清楚

LRU 的常见写法是哈希表加双向链表：哈希表按 key 找节点，链表记录最近使用顺序。只要两种操作都保持常数次指针变更，Get和Put的平均时间复杂度就是 O(1)。难点不在概念，而在淘汰和移动节点时保持两个结构同步。

让指针变更集中

用虚拟头尾节点可减少空链表和首尾节点的分支。链表只负责插入、删除和取尾节点；缓存对象负责 map、容量和调用顺序。这样单元测试可以分别覆盖链表和缓存。

type node struct { key, value int prev, next *node } func (c *Cache) detach(n *node) { n.prev.next = n.next n.next.prev = n.prev } func (c *Cache) attachFront(n *node) { n.next = c.head.next n.prev = c.head c.head.next.prev = n c.head.next = n } func (c *Cache) Get(key int) (int, bool) { n, ok := c.items[key] if !ok { return 0, false } c.detach(n) c.attachFront(n) return n.value, true }

完整的Put需要覆盖已有 key、容量为零、满容量淘汰和新节点插入。淘汰尾节点时，先从链表删除，再从 map 删除；节点保留 key 正是为了完成这一步。

工程中的几个限制

这段代码本身不是并发安全的。并发缓存可在外层加互斥锁，或按 key 分片；RWMutex未必有收益，因为Get也会移动节点，是写操作。容量、TTL、缓存穿透和缓存预热属于上层策略，不能由一个 LRU 结构自动解决。

测试至少包含：连续覆盖同一 key、容量为一、淘汰后重新写入、随机操作与参考 map 的结果对照。不要把纳秒级基准数字当作通用结论；分配、锁和 value 大小都会改变结果。

把链表原语拆开不是为了让代码“更高级”，而是让每一次指针修改都有唯一的位置可检查。