如何在 Java 中通过双向链表结构实现一个简单的 LRU（最近最少使用）页面置换算法缓存

如何在Ja va中实现LRU缓存：从高效工具到深度理解

说到在Ja va里实现LRU缓存，核心思路其实很清晰：你得有一个能快速查找的数据结构，还得有一个能记录访问顺序的机制。这活儿，通常有两种主流做法：一是直接搬出Ja va标准库里的LinkedHashMap，它本身就是一个“双向链表+哈希表”的复合体，拿来即用，非常高效；二是自己动手，组合Node节点、双向链表和HashMap，从头搭建。前者胜在简洁，适合日常开发；后者则能让你把LRU的每个齿轮都看得清清楚楚，尤其适合深入学习和应对技术面试。

用LinkedHashMap快速实现（推荐日常使用）

如果你追求效率，想用最少的代码搞定一个生产可用的LRU缓存，那LinkedHashMap绝对是首选。它的妙处在于，构造时只要把accessOrder参数设为true，它就会自动进入“访问顺序”模式。之后，每次调用get或put（当key已存在时），对应的条目都会被自动移到链表的末尾，成为“最近使用”的项。容量管理就更简单了，只需重写一个removeEldestEntry方法，当缓存大小超过设定容量时，链表头部的“最久未用”项就会被自动淘汰。

来看一个典型的实现示例：

class LRUCache extends LinkedHashMap {
    private final int capacity;

    public LRUCache(int capacity) {
        // 第三个参数 true 是关键，表示按访问顺序排序
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        // 当大小超过容量时，移除最老的条目
        return size() > capacity;
    }
}

这么做的优点显而易见：代码量极少，并且得益于LinkedHashMap的优化，性能非常出色。不过，有个细节需要留意：默认情况下，put一个新key的操作并不会触发访问顺序的更新（只有key已存在时才会）。如果你希望“写入即视为最近使用”，就需要额外处理，比如先调用get检查，或者直接使用replace方法。当然，更彻底的控制，就需要我们接下来要讲的手写方式了。

手写双向链表 + HashMap（适合学习与面试）

要真正吃透LRU，亲手搭建一遍是必不可少的。这套方案由三个核心部件组成：

• Node类：作为缓存项的基本单元，需要包含key、value，以及指向前后节点的prev和next指针。
• 双向链表：这个链表负责维护访问顺序。通常，我们会设置一个“伪头”节点指向最近使用的项，一个“伪尾”节点指向最久未用的项，这样能极大简化边界条件的判断。
• HashMap：它的作用是以O(1)的时间复杂度，通过key快速定位到链表中的对应Node节点。

整个缓存的运作逻辑，就围绕这几个核心操作展开：

• get(key)：先用HashMap找到Node。如果存在，关键的一步来了——必须把这个Node从链表当前位置移除，然后重新插入到链表尾部（即伪尾节点之前），以此标记它为“最近使用”，最后返回value。
• put(key, value)：如果key已存在，流程和get类似：更新value，并将该节点移至链表末尾。如果key不存在，则创建新Node，插入链表末尾，并存入HashMap。此时，如果缓存已超过容量，就要执行淘汰：删除链表头部的下一个节点（即最久未用的节点），并同步从HashMap中移除对应的key。

这里有个让代码更优雅的小技巧：使用“伪头”和“伪尾”这两个哨兵节点，可以让链表的插入和删除操作无需进行繁琐的空指针判断，逻辑更加统一。

关键细节与易错点

自己实现时，下面这几个坑一定要避开：

• 链表指针更新必须完整：在双向链表中插入或删除一个节点时，前后共四个指针的更新必须一步不落。漏掉任何一个，都可能导致链表断裂或产生循环引用，进而引发难以调试的问题。
• HashMap存储的是引用：HashMap里存的是Node对象的引用，而不是值的拷贝。这意味着，Node里key和value的类型，必须与HashMap定义的泛型完全一致。
• put操作需维护顺序：当put一个已存在的key时，绝不能只更新value就了事。必须先将该节点从链表中移除，再插入尾部，否则LRU的访问顺序机制就失效了。
• 淘汰需同步：删除最久未用的节点时，务必记得同时从HashMap中也移除对应的key。如果只删链表节点而忘了清理HashMap，就会导致内存泄漏，而且后续对这个key的get操作会产生错误结果。

是否需要线程安全？

上面讨论的基础版本，在多线程环境下并发读写是不安全的。如果应用场景需要线程安全，可以考虑以下几种方案：

• 使用Collections.synchronizedMap(new LRUCache(...))进行包装。这是最简单的方法，但属于粗粒度锁，在高并发场景下可能影响性能。
• 在get和put等关键方法上直接添加synchronized关键字。实现直接，但同样存在锁竞争问题。
• 对于读多写少的场景，可以考虑使用ReentrantReadWriteLock分离读写锁，实现更精细的并发控制，当然复杂度也会增加。
• 最后，对于生产环境，一个更务实的选择是直接使用业界成熟的高性能缓存库，比如Caffeine或Gua va Cache。它们不仅提供了线程安全的LRU及其变种实现，还在内存管理、过期策略等方面做了大量深度优化，是更可靠的选择。