21-算法与数据结构
第 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 在锁内完成。
记忆要点
- 结构:哈希表 + 双向链表;头 MRU、尾 LRU。
- get 查表并移到头;put 更新/插入到头,满则删尾。
- 并发用锁保护;可选分段或 per-bucket 降低竞争。