ai-infra-interview-305

第 281 题：实现一个LRU cache，支持并发访问

题目

实现一个LRU cache，支持并发访问

---

完整讲解

一、LRU 与并发需求

LRU cache：容量上限，满时淘汰最久未使用的项；get/put 都算「使用」。并发：多线程同时 get/put，需保证正确性与尽量少阻塞。典型接口：get(key)、put(key, value)、可选 get 时刷新「最近使用」顺序。

二、数据结构与策略

经典实现：哈希表 + 双向链表。哈希表 key → 链表节点（含 key、value）；链表按「最近使用」顺序，头为 MRU、尾为 LRU。get：查哈希表、有则把节点移到头并返回值。put：有则更新并移到头；无则新建节点插头，若超容量则删尾节点并从哈希表删除。并发：用一把读写锁（或 mutex）保护整个结构；或分段锁 + 每段一个 LRU；高并发可考虑 per-bucket 锁或 lock-free 结构（实现复杂）。

三、实现要点

双向链表便于 O(1) 删除任意节点并移到头；哈希表 O(1) 查找。注意「先删后加」避免重复 key 时链表成环。并发下 put 可能触发 evict，需在锁内完成「删尾 + 删表项」。

---

面试要点

• LRU：容量满时淘汰最久未用；哈希表 + 双向链表实现 O(1) get/put。
• 链表维护访问顺序（头=MRU、尾=LRU）；get 时移到头，put 满时删尾。
• 并发：整体 mutex 或读写锁；高并发可分段锁或 per-bucket 锁。
• 注意重复 key 时先删后加、evict 在锁内完成。

---

记忆要点

1. 结构：哈希表 + 双向链表；头 MRU、尾 LRU。
2. get 查表并移到头；put 更新/插入到头，满则删尾。
3. 并发用锁保护；可选分段或 per-bucket 降低竞争。

返回模块

返回总览