146. LRU 缓存

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
• 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

要实现一个满足 O(1) 时间复杂度的 get 和 put 操作的 LRU（Least Recently Used）缓存，通常使用 哈希表（HashMap） + 双向链表（Doubly Linked List） 的组合。

Java 标准库中提供了 LinkedHashMap，它内部就是基于这种结构，并支持按访问顺序排序，因此也可以用它来简化实现。但为了更清晰地展示 LRU 的原理，下面提供两种实现方式：

✅ 方法一：使用自定义双向链表 + HashMap（推荐用于面试）

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

class LRUCache {

    // 定义双向链表节点
    class Node {
        int key;
        int value;
        Node prev;
        Node next;

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

    private Map<Integer, Node> cache;
    private int capacity;
    private Node head; // 虚拟头节点
    private Node tail; // 虚拟尾节点

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        // 初始化双向链表的头尾哨兵节点
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 将该节点移到头部（表示最近使用）
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node == null) {
            // 插入新节点
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToHead(newNode);

            if (cache.size() > capacity) {
                // 删除尾部节点（最久未使用）
                Node tailNode = removeTail();
                cache.remove(tailNode.key);
            }
        } else {
            // 更新已有节点的值，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    // 将节点添加到头部（head 之后）
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    // 删除节点
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 将节点移到头部
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    // 删除尾部节点（tail 之前）
    private Node removeTail() {
        Node res = tail.prev;
        removeNode(res);
        return res;
    }
}

✅ 复杂度分析：

• get 和 put 操作均为 O(1)。
• 空间复杂度：O(capacity)，用于存储节点和哈希表。

✅ 方法二：使用 Java 内置 LinkedHashMap（简洁写法）

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

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

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

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

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

    // 当 size() > capacity 时，自动删除最旧的元素
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

⚠️ 注意：虽然这个方法代码简洁，但在某些面试场景中，面试官可能希望你手写双向链表以考察对数据结构的理解。