数组与哈希中等2 种解法

#146LRU 缓存

实现固定容量的最近最少使用缓存，使 get 与 put 平均 O(1)。

#设计#哈希表#双向链表#LinkedHashMap

解题主线

哈希表提供按 key 定位，双向链表提供 O(1) 删除、移到最新端和淘汰最旧端。

LinkedHashMap 的 accessOrder=true 已内置访问顺序，可通过 removeEldestEntry 自动淘汰。

解法 1：LinkedHashMap 访问顺序

启用 access-order，让 get/put 自动把条目移到最新端，并由钩子淘汰最旧项。

时间复杂度

get/put 平均 O(1)

空间复杂度

O(capacity)

146. LRU 缓存 · LinkedHashMap 访问顺序

java

import java.util.LinkedHashMap;
import java.util.Map;

final class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;

    LRUCache(int capacity) {
        super(Math.max(1, capacity), 0.75f, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

启用 access-order，让 get/put 自动把条目移到最新端，并由钩子淘汰最旧项。

修复旧版未插入新键且淘汰判断时机错误的问题。

解法 2：哈希表 + 双向链表

链表头侧表示最近使用、尾侧表示最久未使用；所有节点移动均通过摘除和头插完成。

时间复杂度

get/put 平均 O(1)

空间复杂度

O(capacity)

146. LRU 缓存 · 哈希表 + 双向链表

java

import java.util.HashMap;
import java.util.Map;

final class LRUCache {
    private static final class Node {
        int key;
        int value;
        Node previous;
        Node next;

        Node() {}

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<Integer, Node> nodes = new HashMap<>();
    private final Node head = new Node();
    private final Node tail = new Node();

    LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.previous = head;
    }

    public int get(int key) {
        Node node = nodes.get(key);
        if (node == null) return -1;
        moveToFront(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node existing = nodes.get(key);
        if (existing != null) {
            existing.value = value;
            moveToFront(existing);
            return;
        }
        Node added = new Node(key, value);
        nodes.put(key, added);
        addFirst(added);
        if (nodes.size() > capacity) {
            Node evicted = removeLast();
            nodes.remove(evicted.key);
        }
    }

    private void moveToFront(Node node) {
        remove(node);
        addFirst(node);
    }

    private void addFirst(Node node) {
        node.previous = head;
        node.next = head.next;
        head.next.previous = node;
        head.next = node;
    }

    private void remove(Node node) {
        node.previous.next = node.next;
        node.next.previous = node.previous;
    }

    private Node removeLast() {
        Node last = tail.previous;
        remove(last);
        return last;
    }
}

链表头侧表示最近使用、尾侧表示最久未使用；所有节点移动均通过摘除和头插完成。

修复节点判空条件，并确保容量超限时链表与 Map 同步淘汰。

边界与易错点

旧自定义链表版把 cache != null 误写成节点存在判断，首次 put 就会对 null 节点解引用。
旧 LinkedHashMap 版缺少正常插入，并把淘汰条件写成 size > capacity，导致缓存长期为空。
更新已有 key 也算访问，必须移动到最近使用端；淘汰后要同步删除哈希映射。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

medium/Q146_II_LRUCache.javamedium/Q146_LRUCache.java