实现线程安全的 LRU 缓存
哪些公司问过
答案要点
- 哈希表存 key 到节点映射,双向链表维护访问顺序,get/put 均为 O(1)
- get 命中移到表头;put 满时淘汰表尾并删除哈希表项
- get 也会修改链表,单纯读写锁无法让 get 并发,基础版用一把互斥锁
- 读多写少:按 key 分片,各分片独立加锁,降低竞争
- 延迟或批量调整访问顺序、try_lock 跳过提升,换取并发,代价是近似 LRU
易错点
- 认为 get 是只读操作,直接用共享锁导致并发修改链表
- 淘汰尾节点时忘记同步删除哈希表中的项
- 返回内部数据的引用,解锁后被淘汰导致悬空
面试官常见追问
- 较多线程读、少量线程写怎么优化?
- 为什么用双向链表而不是单向?
- 返回值应该怎么设计?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。