LRU 在容量不足时淘汰最久未被访问的条目。要让读取和写入都接近 O(1)，单用哈希表无法知道新旧顺序，单用链表又不能快速按键定位，因此常组合哈希表与双向链表。

哈希表保存 key -> 节点，链表头表示最近使用，尾表示最久未用。读取命中后把节点从原位置摘下并移到头部；写入已有键时更新值并移头；写入新键时创建头节点，若超过容量，删除尾节点并同步从哈希表移除。双向链表使已知节点的摘除为 O(1)，哑头尾节点可减少边界分支。

1
2
3
4
get(k):
  node = map[k]; if absent return miss
  unlink(node); linkAfterHead(node)
  return node.value

每个操作平均 O(1)，空间 O(capacity)。Java 可利用按访问顺序维护的 LinkedHashMap，并通过淘汰钩子实现，但面试手写仍要展示两个结构的一致性。

工程缓存还要考虑线程安全、过期时间、权重容量、缓存击穿和统计。锁住每次访问会简单但可能竞争；分段或成熟缓存库通常更可靠。LRU 也并非命中率总最佳：一次性顺序扫描可能污染缓存，LFU 或分代策略有时更合适。

常见误区是命中后不更新顺序、删链表却忘删映射、容量为零处理错误、使用单链表导致尾删除昂贵，以及把过期淘汰与 LRU 混为一谈。小结：LRU 的核心是不变量——映射与链表节点一一对应，链表次序始终代表最近访问时间。