LRU缓存：哈希+指针

题目

请你设计并实现一个满足  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) 的平均时间复杂度运行。

思考

一点思路没有呢

代码

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

public class LRUCache {

    // ==================== 1. 定义链表节点 ====================
    private class Node {
        int key;
        int value;
        Node prev;
        Node next;

        Node() {}  // 空构造，给假头假尾用

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

    // ==================== 2. 成员变量 ====================
    private final int capacity;   // 最大容量
    private int size;              // 当前元素个数
    private final Map<Integer, Node> cache;  // 哈希表：快速查找
    private final Node head;       // 假头节点（最近使用的方向）
    private final Node tail;       // 假尾节点（最久未使用的方向）

    // ==================== 3. 构造方法 ====================
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.cache = new HashMap<>();

        // 初始化假头假尾，互相连接
        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    // ==================== 4. 对外接口：get ====================
    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;  // 缓存中没有
        }
        // 找到了，移到头部（续命）
        moveToHead(node);
        return node.value;
    }

    // ==================== 5. 对外接口：put ====================
    public void put(int key, int value) {
        Node node = cache.get(key);

        if (node == null) {
            // 情况1：新 key，需要插入
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            size++;

            // 检查是否超出容量
            if (size > capacity) {
                Node removed = removeTail();  // 淘汰最久未使用
                cache.remove(removed.key);    // 哈希表同步删除
                size--;
            }
        } else {
            // 情况2：已有 key，更新 value
            node.value = value;
            moveToHead(node);  // 更新后也是最近使用
        }
    }

    // ==================== 6. 链表内部方法 ====================

    /** 将节点添加到链表头部（最近使用） */
    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);
    }

    /** 移除尾部节点（最久未使用）并返回 */
    private Node removeTail() {
        Node node = tail.prev;  // 尾节点的前一个就是真实的最久未使用节点
        removeNode(node);
        return node;
    }
}

‍