4. LRU策略实现与调优：双向链表+哈希表实现，访问频率与淘汰时机的关系

LRU（Least Recently Used）是最经典的缓存淘汰策略之一。其核心思想是：如果数据最近被访问过，那么将来被访问的概率也更高。因此，当缓存空间不足时，优先淘汰最长时间未被访问的数据。

工业级LRU缓存通常采用双向链表 + 哈希表的组合结构，能够在 O(1) 时间复杂度内完成数据的插入、查找和淘汰操作。本章将深入剖析该结构的实现原理、调优方向以及访问频率与淘汰时机之间的微妙关系。

4.1 双向链表 + 哈希表：LRU的经典实现结构

该结构将双向链表与哈希表结合，各司其职：

  • 双向链表：维护所有缓存项的访问顺序。链表头部为最近访问的节点，尾部为最久未访问的节点。淘汰时直接移除尾部节点。
  • 哈希表：以 Key 为索引，存储指向链表节点的指针。实现 O(1) 的查找与定位。

每次访问（get/put）时，将对应节点移动到链表头部；当缓存满时，移除链表尾部节点，并同步删除哈希表中的对应项。

关键优势：所有核心操作（查找、插入、删除、移动）的时间复杂度均为 O(1)，这是 LRU 能够应对高并发场景的基础。
LRU 双向链表 + 哈希表结构 哈希表 (HashMap) Key1 → 节点1 Key2 → 节点2 Key3 → 节点3 Key4 → 节点4 Key5 → 节点5 ... 双向链表 (Doubly Linked List) Head (最近访问) Node1 Node2 Node3 Node4 Node5 Tail (最久未访问)

4.2 核心操作实现与代码示例

以下是一个简化的 LRU 缓存实现，展示了双向链表节点定义、哈希表操作以及 get/put 的核心逻辑。

class DLinkedNode {
    int key;
    int value;
    DLinkedNode prev;
    DLinkedNode next;
}

public class LRUCache {
    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用虚拟头尾节点，简化边界处理
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) return -1;
        // 访问后移动到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 创建新节点
            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;
            cache.put(key, newNode);
            addToHead(newNode);
            size++;
            if (size > capacity) {
                // 淘汰尾部节点
                DLinkedNode tailNode = removeTail();
                cache.remove(tailNode.key);
                size--;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}
实现要点：使用虚拟头尾节点（dummy head/tail）可以避免空指针判断，简化链表操作。哈希表的值存储的是链表节点引用，而非 Key-Value 对本身，这是实现 O(1) 移动的关键。

4.3 访问频率与淘汰时机的关系

标准 LRU 仅以最近一次访问时间作为淘汰依据，而不考虑访问频率。这在实际场景中可能引发问题：

场景 问题描述 影响
批量扫描 一次性扫描大量冷数据，将热点数据挤出缓存 缓存命中率骤降，系统响应变慢
周期性低频访问 某些数据每隔一段时间被访问一次，但频率很低 频繁进出缓存，浪费淘汰和加载开销
突发高频访问 某个 Key 在短时间内被高频访问，之后不再使用 长期占用缓存空间，影响其他数据

这些问题的根源在于：LRU 只记忆“最近”，不记忆“经常”。为了弥补这一缺陷，业界提出了多种改进方案：

  • LRU-K：记录每个 Key 最近 K 次访问的时间戳，淘汰时选择第 K 次访问时间最久远的 Key。K 值越大，对访问频率的敏感度越高。
  • Two Queues (2Q)：将缓存分为“一次访问队列”和“多次访问队列”。数据首次访问进入 FIFO 队列，再次访问时晋升到 LRU 队列，避免扫描污染。
  • ARC (Adaptive Replacement Cache)：动态平衡最近访问和频繁访问两个列表的大小，自适应调整淘汰策略。
LRU vs LRU-K 淘汰决策对比 标准 LRU 淘汰依据：最近一次访问时间 访问序列：A, B, C, D, E, A 缓存容量：4 淘汰结果：淘汰 B（最久未访问） 即使 B 被访问过 100 次， 只要最近没访问，就会被淘汰 LRU-K (K=2) 淘汰依据：第 K 次访问时间 访问序列：A, B, C, D, E, A 缓存容量：4 淘汰结果：淘汰 C（第2次访问最久远） B 因为被访问过 100 次， 第 2 次访问时间较近，得以保留

4.4 LRU 调优参数与最佳实践

在实际系统中，LRU 的调优并非仅靠算法本身，还需要结合业务场景调整以下参数：

调优维度 参数/策略 推荐场景 注意事项
缓存容量 根据内存预算设置最大条目数或最大内存占用 所有场景 过小导致频繁淘汰，过大增加 GC 压力
淘汰粒度 单条淘汰 vs 批量淘汰（如一次淘汰 10%） 高并发写入场景 批量淘汰可减少锁竞争，但会短暂降低命中率
访问记录精度 使用 LRU-K (K=2/3) 或 2Q 替代标准 LRU 存在批量扫描或周期性访问 K 值越大，内存开销越高
过期时间 结合 TTL 主动过期，避免冷数据长期驻留 有时效性要求的数据 TTL 与 LRU 淘汰是互补关系，需协同配置
分段锁 将哈希表拆分为多个 segment，降低锁粒度 高并发读写场景 实现复杂度增加，需注意一致性
调优陷阱：不要盲目增大缓存容量。当缓存容量超过工作集大小后，命中率提升趋于平缓，但内存成本和 GC 开销会线性增长。建议通过监控工具（如 Redis 的 INFO stats、Caffeine 的命中率统计）找到容量拐点。

4.5 测试验证：如何验证 LRU 淘汰行为正确性

在测试 LRU 实现时，需要覆盖以下关键场景：

  1. 基础淘汰验证：插入超过容量的数据，确认最早插入且未被再次访问的数据被淘汰。
  2. 访问提升验证：访问某个已存在的 Key，确认其被移动到头部，不会被优先淘汰。
  3. 更新不改变位置验证：更新已存在 Key 的 Value，确认其位置不变（或移动到头部，取决于设计）。
  4. 相同 Key 重复插入验证：重复 put 相同 Key，确认不会导致容量计数错误或链表断裂。
  5. 并发安全验证：多线程同时读写，验证最终一致性且无死锁。
测试用例示例（伪代码）：
// 场景：容量为 3，插入 A, B, C，再插入 D
cache.put("A", 1);
cache.put("B", 2);
cache.put("C", 3);
cache.get("A");  // 访问 A，提升其优先级
cache.put("D", 4);
// 预期：B 被淘汰（最久未访问），A、C、D 保留
assert cache.get("B") == -1;
assert cache.get("A") == 1;
assert cache.get("C") == 3;
assert cache.get("D") == 4;

通过系统化的测试验证，可以确保 LRU 实现不仅在功能上正确，还能在压力下保持稳定的淘汰行为，为后续的失效策略调优奠定坚实基础。

← 上一章 📖 返回目录 下一章 →