LRU 缓存 Least Recently Used

数据结构 · 哈希表 + 双向链表的经典组合

什么是 LRU 缓存

缓存空间有限，满了就得淘汰一项。LRU（最近最少使用）的策略是：淘汰最久没被用过的那一项——刚用过的最该留着，最久没碰的最该走。

这里容量 4，缓存项按「最近使用」从左到右排：最左是刚用的（MRU），最右是最久没用的（LRU，下一个被淘汰）。get、put 只要碰到某一项，就把它挪到最前。试试 get 一个已有的键、put 一个新键、再把缓存 put 到满。

怎么做到 get/put 都 O(1)？答案正是前面两种结构的组合：哈希表负责按 key O(1) 找到节点（见哈希那篇），双向链表负责 O(1) 把节点挪到最前、从最后淘汰（见链表的双向那节）。哈希定位 + 双链表调序，缺一不可——这也是它常被当面试题的原因。

LRU 在哪里用

它是「组合已有结构解决新问题」的典范——也为这趟数据结构之旅收个尾。