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

推荐用 LinkedHashMap 实现 LRU 缓存，因其底层基于双向链表+哈希表，设置 accessOrder=true 可自动维护访问顺序，重写 removeEldestEntry 即可淘汰最久未用项；手写方式需 Node、双向链表和 HashMap 配合，注意指针更新与 map 同步。

在 java 中用双向链表实现 lru 缓存，核心是用 linkedhashmap（底层即双向链表 + 哈希表）或手写 node + doublylinkedlist + hashmap 组合。前者简洁高效，后者更利于理解 lru 机制和面试考察。

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

Java 的 LinkedHashMap 天然支持访问顺序（accessOrder = true），每次 get 或 put 都会把对应节点移到链表尾部；当容量超限时，可重写 removeEldestEntry 方法自动淘汰头节点（最久未用）。

示例代码：

class LRUCache<k v> extends LinkedHashMap<k v> {
    private final int capacity;

    public LRUCache(int capacity) {
        // true 表示按访问顺序排序（get/put 都算访问）
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<k v> eldest) {
        return size() > capacity; // 超过容量就移除最老的
    }
}</k></k></k>

✅ 优点：代码少、线程不安全但性能高；
❌ 注意：默认 put 不触发访问顺序更新（除非 key 已存在），若需“写入也算最近使用”，确保 key 存在时用 replace 或先 get 再 put，或改用手写方式。

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

关键组件：

Java Maven Code Review

审查Java Maven项目（ZIP压缩包或GitLab仓库URL），检查代码规范、命名、模块边界、可维护性问题以及重复代码。

下载

Node 类：含 key、value、prev、next 字段
双向链表：维护 head（伪头，指向最新）、tail（伪尾，指向最久）
HashMap：O(1) 定位节点

操作逻辑：

get(key)：查 map → 找到 node → 从链表中移出 → 插入 tail 前（即移到末尾）→ 返回 value
put(key, value)：若 key 存在 → 更新值 + 移至末尾；若不存在 → 新建 node 插入末尾 + 放入 map；若超容 → 删除 head.next（最久节点）并从 map 移除其 key

小技巧：用伪头（dummy head）和伪尾（dummy tail）避免空指针判断，插入删除统一。