一句话答案

LRU 用 HashMap + 双向链表实现 O(1) get/put：访问的节点移到头部，超容量时淘汰尾部节点。

核心要点

数据结构： HashMap<Key,Node> + DoubleLinkedList

操作： get → 查找+移到头部；put → 存在则更新+移头部，不存在则新建+加头部，超容删尾部

扩展： LFU（频率最低淘汰）用 HashMap + 频率→链表映射；Redis 近似 LRU 用随机采样

追问与易错

追问方向：

• LRU 和 LFU 的区别？
• Redis 的 LRU 是精确的吗？
• 手写 LRU 的关键点？

易错点：

• ❌ LRU 和 LFU 一样——LRU 按时间 LFU 按频率
• ❌ LRU 需要排序——用链表移动操作 O(1)

💡 记忆锚点

LRU像餐厅等位：最近来过的人排队头（HashMap定位+移到链表头O(1)），队尾是最久没来的人，满了就请队尾走（淘汰）。关键数据结构是"HashMap+双向链表"的组合拳：HashMap保证O(1)查找，双向链表保证O(1)增删移动。LFU则是按来的次数淘汰，更精确但更复杂。