设计带统一过期时间的 LRU 缓存
哪些公司问过
答案要点
- 哈希表加双向链表,访问时移到头部,容量满时淘汰尾部,get 和 put 都是 O(1)
- 节点存 expireAt 等于写入时刻加 TTL,get 命中先判断过期,过期即删除,即惰性删除
- 统一 TTL 下写入顺序就是过期顺序,用一条 FIFO 队列从头部清理过期项,均摊 O(1)
- 如果访问也续期,LRU 链表尾部本身就是最早过期的节点,一条链表即可兼顾
- 使用单调时钟计算过期;并发场景加锁,可配合定时任务主动清理
易错点
- get 命中后忘记检查过期,返回了已过期的数据
- 删除时只删链表不删哈希表,或者反过来,导致两边不一致
- 用系统墙钟计算过期,时钟回拨会出错,应使用单调时钟
- 容量满时直接淘汰尾部,没有先清掉已过期的节点
面试官常见追问
- 为什么用双向链表而不是单向链表?
- 只做惰性删除有什么问题?
- 如果每个 key 的 TTL 不同怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。