当前位置：首页 > news >正文

AI 辅助：数据结构工程化：LRU 缓存从题目到生产的差异

news 2026/7/2 1:27:46

AI 辅助：数据结构工程化：LRU 缓存从题目到生产的差异

一、面试里的 LRU，和生产里的缓存不是一回事

LRU 是高频题，标准解法是哈希表加双向链表。面试里实现get和put，保证 O(1)。但生产里的缓存要考虑更多问题：并发安全、容量估算、过期时间、热点 key、指标监控、淘汰回调。只会写题目版本，离工程可用还有距离。

题目版本关注算法结构，生产版本关注运行边界。比如容量按条目数算，还是按内存大小算？多个 goroutine 同时访问，链表如何加锁？淘汰时是否要释放外部资源？缓存命中率下降时如何发现？这些都不是 LeetCode 会问的，但线上会问。

因此，学习数据结构时，不要停在 AC。更好的方式是先写标准结构，再补工程约束。这样算法能力才能真正迁移到后端系统里。

二、LRU 数据流：访问即移动，超限即淘汰

flowchart TD A[get/put 请求] --> B{key 是否存在} B -- 是 --> C[更新值并移动到链表头] B -- 否 --> D[创建新节点] D --> E[插入链表头] E --> F{容量是否超限} F -- 否 --> G[返回] F -- 是 --> H[淘汰链表尾节点] H --> I[删除哈希表索引]

哈希表提供 O(1) 定位，双向链表提供 O(1) 移动和淘汰。链表头表示最近使用，链表尾表示最久未使用。每次访问都把节点移动到头部。容量超限时，从尾部删除。

这个结构本身不复杂，容易错的是指针维护。删除节点时要同时处理前驱和后继，插入头部时要处理空链表。工程里建议使用哨兵节点，减少边界判断。

三、Go 实现：加锁后的最小可用版本

下面是一个并发安全的 LRU 骨架。

type entry struct { key string value any prev *entry next *entry } type LRU struct { mu sync.Mutex capacity int items map[string]*entry head *entry tail *entry } func NewLRU(capacity int) *LRU { head := &entry{} tail := &entry{} head.next = tail tail.prev = head return &LRU{capacity: capacity, items: make(map[string]*entry), head: head, tail: tail} } func (c *LRU) Get(key string) (any, bool) { c.mu.Lock() defer c.mu.Unlock() node, ok := c.items[key] if !ok { return nil, false } c.moveToFront(node) return node.value, true } func (c *LRU) Put(key string, value any) { c.mu.Lock() defer c.mu.Unlock() if node, ok := c.items[key]; ok { node.value = value c.moveToFront(node) return } node := &entry{key: key, value: value} c.items[key] = node c.insertAfterHead(node) if len(c.items) > c.capacity { c.removeOldest() } }

这里使用一把互斥锁保护 map 和链表。读操作也要加锁，因为Get会修改链表顺序。想提高并发，可以做分片 LRU，但复杂度会上升。

工程上还要补指标。至少包括命中次数、未命中次数、淘汰次数、当前条目数。没有指标，就无法判断缓存是否真的有效。