LRU缓存实现#

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

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

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

LRU即最近最少使用缓存淘汰策略，核心数据结构是HashMap加双向链表的组合，保证get和put都是O(1)。HashMap存储key到链表节点的映射实现O(1)查找，双向链表维护访问顺序，最近访问的放头部最久没访问的在尾部。get操作先在HashMap查找，找到后把节点从链表原位置摘出移动到头部。put操作如果key已存在就更新value并移到头部，不存在就新建节点加到头部同时放入HashMap，如果超过容量上限就删除链表尾部节点并从HashMap中移除。用双向链表而不是单链表是因为删除操作需要知道前驱节点，双向链表可以O(1)完成。Java中可以直接继承LinkedHashMap，构造时传accessOrder=true并重写removeEldestEntry方法来实现LRU，它底层就是这个思路；默认accessOrder=false是插入顺序，get不会调整顺序，就成了FIFO。Redis的LRU不是精确实现，而是近似LRU，每次随机采样maxmemory-samples个key（默认5）淘汰其中最久未使用的，3.0起还维护一个候选淘汰池让结果更接近真实LRU，这样避免了维护全局链表的开销。LFU按访问频率淘汰更精确但实现更复杂，需要额外维护频率到链表的映射。

追问方向：

• “LRU 和 LFU 的区别？”→ LRU 淘汰最久未使用的（按时间），LFU 淘汰使用频率最低的（按次数）；LFU 对热点数据更友好但实现复杂，需要维护频率桶
• “Redis 的 LRU 是精确的吗？”→ 不是精确 LRU，Redis 用近似 LRU：随机采样 maxmemory-samples 个 key（默认5个）淘汰其中最久未用的，3.0 起配合候选淘汰池提高近似度，避免维护全局链表的开销；Redis 4.0+ 还支持 LFU 策略
• “手写 LRU 的关键点？”→ HashMap + 双向链表：HashMap 存 key→Node 实现 O(1) 查找，双向链表维护访问顺序；get/put 时将节点移到链表头部，容量满时删除尾节点

易错点：

• ❌ LRU 和 LFU 一样——LRU 按时间 LFU 按频率
• ❌ LRU 需要排序——用链表移动操作 O(1)
• ❌ put 已存在的 key 只改 value——还要把节点移到头部，且不触发淘汰（容量没变）；只有新增 key 超容才删尾
• ❌ 继承 LinkedHashMap 重写 removeEldestEntry 就是 LRU——必须构造时传 accessOrder=true，否则按插入顺序淘汰，get 不刷新顺序