LRU 缓存淘汰算法

概述

LRU(Least Recently Used,最近最少使用)是最经典的缓存淘汰算法:当缓存空间不足时,优先淘汰最长时间未被访问的条目。其依据是访问的时间局部性——最近用过的数据更可能再次被用到。

实现

标准实现是哈希表加双向链表:哈希表提供 O(1) 查找,链表按访问时间排序,每次访问将节点移到表头,淘汰时摘除表尾,使 get 和 put 均为 O(1)(LeetCode 146)。工程实现常用近似算法:Redis 采用随机采样若干键淘汰其中空闲时间最长者的近似 LRU;MySQL InnoDB 的缓冲池将 LRU 链表分为冷热两段(midpoint 插入),防止全表扫描冲刷热点数据。

变体

LRU 对突发扫描不友好,由此衍生 LRU-K、2Q、SLRU、LFU;W-TinyLFU(Caffeine 缓存库采用)结合频率草图与窗口,命中率在多数负载下优于 LRU;ARC 则自适应地在时间与频率之间平衡。