LRU 缓存的实现
哪些公司问过
答案要点
- 哈希表提供 O(1) 查找,双向链表维护访问顺序(头部最近、尾部最久未使用)
- get 命中:把节点移到链表头部
- put:key 已存在则更新并移到头部;不存在则插入头部,容量满时淘汰尾节点并删除哈希表中的 key
- 哈希表存 key 到链表节点(C++ 里是 list 迭代器)的映射,get/put 均为 O(1)
- C++ 用 std::list::splice 在 O(1) 内移动节点,不拷贝元素
易错点
- 用单向链表或数组:删除、移动退化为 O(n)
- 淘汰尾节点时忘了同时删除哈希表里的 key
- 更新已有 key 时忘了把它移到头部
- 只处理 get 命中的移动,漏掉 put 已存在 key 的情况
面试官常见追问
- 为什么用双向链表而不是单向链表?
- LRU 和 LFU 有什么区别?
- LRU 有什么缺点,怎么改进?
- 多线程下怎么用?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。