1. 缓存替换策略的复杂度与实现代价中 LRU（哈希+双向链表 O(1)）、LFU（频次桶 O(1)）、ARC（四链表 O(1)）、W-TinyLFU（sketch+SLRU）各自的数据结构？
问题
请说明 LRU、LFU、ARC、W-TinyLFU 四种主流缓存替换策略各自采用的数据结构，分析它们如何实现 O(1) 的 get/put，以及各自的实现代价与适用场景？
考察点
- 各策略的底层数据结构与复杂度上界
- 哈希表与链表/桶组合解决"按访问顺序/频次"的定位问题
- 实现代价与内存开销的权衡
答案
LRU 用"哈希表 + 双向链表"：哈希表在 O(1) 定位节点，双向链表维护访问顺序，访问时把节点移到链表头、淘汰时删链表尾，两个操作均为 O(1)。LFU 用"哈希表 + 频次桶链表"：每个频次值对应一个双向链表（含同频节点），再从哈希表定位节点，同时维护一个最小频次指针，get/put 与频次更新都是 O(1)。ARC 用四个双向链表 T1/T2/B1/B2 分别对应 recent 与 frequent 的缓存页与幽灵页（ghost），借助自适应目标 p 动态调整 T1 与 T2 的容量，四链表操作均为 O(1)。W-TinyLFU 用"Count-Min sketch 频率近似 + window LRU + segmented LRU（SLRU）"：sketch 用哈希叠加近似统计访问频率（O(1)），window 记录近期流量，main 段用 probation/protected 两级 SLRU 保存高频安全条目，整体复杂度 O(1)。
解析
四条主线共同点：都用哈希表完成 O(1) 定位，再用一种"有序结构"（链表/桶/sketch）表达"访问序"或"频次"这一维度。LRU 只记录"最近性"，LFU 只记录"频次"，ARC 在两者间自适应，W-TinyLFU 则用近似 sketch 用极小的内存代价逼近 LFU 的频率信息并保持 O(1) 与高并发。复杂度和内存代价从 LRU 到 ARC/W-TinyLFU 递增，但命中率与扫描抵抗性也更好。
示例代码
// 以 LRU 为例：哈希表 + 双向链表，O(1) get/put
class LRUCache {
private final int capacity;
private final Map<Integer, Node> map = new HashMap<>();
private final Node head = new Node(0, 0); // 哨兵头
private final Node tail = new Node(0, 0); // 哨兵尾
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node n = map.get(key);
if (n == null) return -1;
moveToHead(n);
return n.value;
}
public void put(int key, int value) {
Node n = map.get(key);
if (n != null) {
n.value = value;
moveToHead(n);
return;
}
if (map.size() == capacity) {
Node last = tail.prev; // 最久未使用
removeNode(last);
map.remove(last.key);
}
Node nn = new Node(key, value);
map.put(key, nn);
addToHead(nn);
}
private void addToHead(Node n) {
n.next = head.next;
n.prev = head;
head.next.prev = n;
head.next = n;
}
private void removeNode(Node n) {
n.prev.next = n.next;
n.next.prev = n.prev;
}
private void moveToHead(Node n) {
removeNode(n);
addToHead(n);
}
static class Node {
int key, value;
Node prev, next;
Node(int k, int v) { key = k; value = v; }
}
}