笔试题：LRU缓存 | 程序之心

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) 的平均时间复杂度运行。

分析

为了满足 LRU（Least Recently Used）缓存的要求，并确保 get 和 put 操作具有 O(1) 平均时间复杂度，我们需要结合以下两种数据结构：

哈希表：用于实现 O(1) 的 key 查找。
双向链表：用于维护元素的访问顺序，使得最近使用的在尾部，最久未使用的在头部，支持 O(1) 插入和删除。

设计要点：

使用虚拟头节点 head 和虚拟尾节点 tail 简化边界操作。
每次 get 或 put 一个已存在的 key，都要将其移到链表尾部（表示“最近使用”）。
当容量满时，从链表头部移除最久未使用的节点，并同步从哈希表中删除。

代码

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

public class LRUCache {

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

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

    /**
     * 容量
     */
    private final int capacity;
    /**
     * 缓存
     */
    private final Map<Integer, Node> cache;
    /**
     * 头节点
     */
    private final Node head;
    /**
     * 尾节点
     */
    private final Node tail;

    /**
     * 构造函数
     * @param capacity 容量
     */
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    /**
     * get
     * @param key 键
     * @return 值
     */
    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 移动到尾部（标记为最近使用）
        moveToTail(node);
        return node.value;
    }

    /**
     * put
     * @param key 键
     * @param value 值
     */
    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node != null) {
            // 更新值并移到尾部
            node.value = value;
            moveToTail(node);
        } else {
            // 新增节点
            if (cache.size() >= capacity) {
                // 删除最久未使用的节点（head.next）
                Node oldest = head.next;
                removeNode(oldest);
                cache.remove(oldest.key);
            }
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToTail(newNode);
        }
    }

    /**
     * 将节点从链表中移除
     * @param node 节点
     */
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /**
     * 将节点添加到链表尾部（tail 前面）
     * @param node 节点
     */
    private void addToTail(Node node) {
        node.prev = tail.prev;
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
    }

    /**
     * 将已有节点移动到尾部
     * @param node 节点
     */
    private void moveToTail(Node node) {
        removeNode(node);
        addToTail(node);
    }
}