01
目的：用有限空间保留更可能再用的数据
LRU 不是数据库，也不是一致性协议。它只解决一个问题：缓存满了以后，优先淘汰最久没有被访问的条目。
降低慢路径成本
数据库、磁盘、网络和重复计算都可能很慢。缓存命中时直接返回，避免再次走慢路径。
利用时间局部性
刚被访问的数据，短期内更可能再次被访问。LRU 把这个经验规则工程化。
稳定淘汰规则
容量满时不随机删除，而是删除 tail 前的冷数据，行为可解释、可测试。
hash table / doubly linked list / eviction policy
LRU Cache
get(k): O(1)
哈希表直接找到节点，再把它移动到队头。
put(k,v): O(1)
更新或插入后放到队头，超容量时淘汰队尾。
head ⇄ ... ⇄ tail
队头最热，队尾最冷，哨兵节点消除边界分支。
LIVE CACHE STATE
ready
1. HASH LOOKUP
用 key 在 map 中查找节点引用，不扫描链表。
2. LIST SPLICE
命中或更新后，把节点从原位置摘下并接到 head 后。
3. TAIL EVICT
超过 capacity 时，删除 tail 前的最久未使用节点。
Doubly Linked List MRU -> LRU
head 之后
最近访问或刚写入的数据，下一次淘汰时最安全。
tail 之前
最久没有被访问的数据，容量溢出时优先删除。
HashMap key -> node*
capacity
4
最多保留多少个 key。
cache size
4 / 4
超过容量就淘汰 tail 前节点。
hit ratio
0%
本页操作序列中的命中率。
LRU Cache 解决的是一个朴素但高频的问题：空间有限时，应该保留谁、淘汰谁。 它用 HashMap 负责 O(1) 定位，用 双向链表 负责 O(1) 调整新旧顺序， 把“最近使用”变成一条可维护的时间轴。
02
核心结构：HashMap + 双向链表
LRU 的职责拆分很清楚：HashMap 负责 O(1) 找节点，双向链表负责 O(1) 调整新旧顺序。
HashMap：key -> Node
避免从链表头扫到尾。命中后直接拿到节点引用。
双向链表：MRU -> LRU
head 后是最近使用，tail 前是最久未使用。命中和写入都移动到 head 后。
哨兵 head / tail
空表、单节点、删除头尾都变成同一套指针改写，减少边界分支。
get(key)
查 map。未命中返回 -1；命中则移动到 head 后，再返回 value。
put(existing)
更新 value，并移动到 head 后。写入也算一次使用。
put(new)
创建节点，加入 map，插到 head 后。若超容量，删除 tail 前节点。
Invariant
map 与链表必须同步；链表顺序必须从热到冷。
03
Java 实现：把指针操作集中到 helper
公开方法只表达业务动作；摘节点、插头部、移动到头部、删除冷节点都放进 helper，代码更容易检查。
04
高并发版本：先决定要多精确
标准 LRU 的 get 不是纯读，它要移动链表节点。并发设计的关键，是在“严格顺序”和“高吞吐”之间做选择。
05
复杂度与取舍
基础 LRU 的复杂度很漂亮，但工程版本还要考虑并发、容量、过期、一致性和观测。
平均 O(1)，空间 O(capacity)
get：查 map，移动节点，返回值。
put：更新或插入，必要时删 tail 前节点。
并发：严格 LRU 必须同步链表；吞吐优先时通常分片或近似。
为什么不用数组
数组移动中间元素到头部要 O(n)。LRU 每次命中都要刷新顺序，所以数组不合适。
为什么节点要存 key
淘汰时拿到的是 tail 前节点。节点必须带 key，才能同步删除 map 中的条目。
设计原则
策略是“最近使用者留下”，机制是“map 定位 + 链表排序”。先保证不变量，再谈性能。