Java 数据结构中 LRU 缓存淘汰算法基于双向链表的底层怎么手写-java教程-PHP中文网

lru缓存淘汰算法需哈希表+双向链表实现o(1)操作：一、定义含key/value及prev/next指针的node类，key用于淘汰时同步删除map项；二、用dummyhead和dummytail简化边界处理；三、核心是movetohead和removenode方法；四、put/get中更新链表位置并维护map与size。

java 数据结构中 lru 缓存淘汰算法基于双向链表的底层怎么手写

LRU 缓存淘汰算法的核心是“最近最少使用”，要高效支持 O(1) 插入、删除、查找和更新，必须结合哈希表 + 双向链表。手写关键在于：用 HashMap 快速定位节点，用自定义双向链表维护访问时序——最新访问的放头部，淘汰时删尾部。

一、定义双向链表节点

每个节点需存 key、value，并有 prev 和 next 指针。不依赖 LinkedList，自己写 Node 类更清晰可控：

static class Node {
    int key, value;
    Node prev, next;
    Node(int k, int v) {
        this.key = k;
        this.value = v;
    }
}

注意：key 字段不能省略。因为淘汰尾节点时，需通过节点反查 key，才能从 HashMap 中同步删除。

二、维护头尾哨兵节点（简化边界处理）

初始化时创建 dummyHead 和 dummyTail，让所有真实节点夹在中间。这样插入、删除无需判空，逻辑统一：

Java Maven Code Review

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

下载

put/get 时，把目标节点移到 head 后（即成为最新）
size 超限时，删 tail.prev（即最老节点），并从 map 删除其 key
head.next 是最近访问的，tail.prev 是最久未用的

三、核心操作：moveToHead 和 removeNode

这两个辅助方法是 LRU 的骨架，务必写对：

private void removeNode(Node node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
}
private void addToHead(Node node) {
    node.prev = head;
    node.next = head.next;
    head.next.prev = node;
    head.next = node;
}
private void moveToHead(Node node) {
    removeNode(node);
    addToHead(node);
}

addToHead 不是简单插在 head 后，还要修正原节点前后指针；removeNode 前必须确保 node 不是哨兵（实际调用时已保证）。