如何实现一个LRU缓存机制

题目描述
LRU（Least Recently Used，最近最少使用）是一种常用的缓存淘汰策略。其核心思想是：当缓存容量达到上限时，优先淘汰那些最久未被访问的数据。题目要求设计并实现一个LRU缓存类，它需要支持以下两种操作：

1. get(key)：如果键key存在于缓存中，则返回对应的值，并将该键值对标记为最近使用；否则返回-1。
2. put(key, value)：如果键key已存在，则更新其对应的值，并标记为最近使用。如果键不存在，则插入该键值对。如果插入后缓存容量超过上限，则需要淘汰最久未使用的键值对。

要求get和put操作的时间复杂度均为O(1)。

解题思路
要使get和put都达到O(1)时间复杂度，我们需要一种数据结构能快速完成以下操作：

1. 快速查找键对应的值 -> 哈希表（HashMap）可以在O(1)时间内完成。
2. 快速调整“最近使用”顺序 -> 当访问一个已存在的键时，需要将它从当前位置移动到“最近使用”的位置（例如，移动到链表头部或尾部）。
3. 快速删除最久未使用的元素 -> 我们需要知道数据被访问的时间顺序，并且能在O(1)时间内删除最早的元素。有序的线性数据结构（如链表）支持在O(1)时间内删除节点，但链表查找是O(n)。然而，哈希表+双向链表的组合可以解决这个问题：

• 双向链表：按访问时间顺序排列节点。靠近头部的节点是最近使用的，靠近尾部的节点是最久未使用的。这样，删除尾部节点（淘汰）和移动节点到头部（标记最近使用）都可以在O(1)时间内完成。
• 哈希表：以键key为键，以链表节点（包含key和value）为值。这样我们可以通过键在O(1)时间内定位到链表中的具体节点。

数据结构设计：

• 定义一个双向链表节点类Node，包含key、value、prev、next。
• LRU缓存类包含：
  • 一个哈希表cache（例如HashMap<Integer, Node>），用于O(1)查找。
  • 一个双向链表，维护访问顺序。我们使用虚拟头节点（dummyHead）和虚拟尾节点（dummyTail） 来简化链表操作，避免处理头尾节点的边界条件。
  • 缓存容量capacity和当前大小size。

核心操作逻辑：

1. get(key)：

   • 在cache中查找key。
   • 如果不存在，返回-1。
   • 如果存在，获取对应的节点node，然后调用moveToHead(node)（将该节点移动到链表头部，表示最近使用），最后返回node.value。

2. put(key, value)：

   • 在cache中查找key。
   • 如果存在，获取节点node，更新node.value，然后调用moveToHead(node)。
   • 如果不存在：
     • 创建新节点newNode。
     • 将newNode添加到链表头部（addToHead(newNode)）。
     • 将key和newNode放入cache。
     • size++。
     • 如果size > capacity，则需要淘汰最久未使用的节点：
       • 链表尾部节点（dummyTail.prev）就是最久未使用的节点tailNode。
       • 从链表中移除tailNode（removeNode(tailNode)）。
       • 从cache中删除对应的键tailNode.key。
       • size--。

辅助方法：

• addToHead(node)：将节点插入到虚拟头节点之后。
• removeNode(node)：从链表中移除指定节点。
• moveToHead(node)：先removeNode(node)，再addToHead(node)。

逐步实现讲解

步骤1：定义双向链表节点类

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

步骤2：LRU缓存类框架与初始化

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

class LRUCache {
    // 哈希表，用于快速查找
    private Map<Integer, Node> cache = new HashMap<>();
    // 当前缓存中的键值对数量
    private int size;
    // 缓存容量上限
    private int capacity;
    // 虚拟头节点和虚拟尾节点，简化链表操作
    private Node dummyHead, dummyTail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 初始化双向链表，建立头尾虚拟节点的连接关系
        dummyHead = new Node();
        dummyTail = new Node();
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }
}

步骤3：实现辅助的链表操作方法

    // 将一个新节点添加到链表头部（虚拟头节点之后）
    private void addToHead(Node node) {
        node.prev = dummyHead;
        node.next = dummyHead.next;
        dummyHead.next.prev = node;
        dummyHead.next = node;
    }

    // 从链表中移除一个节点
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 将一个已存在的节点移动到链表头部
    private void moveToHead(Node node) {
        removeNode(node);   // 1. 先从原位置移除
        addToHead(node);    // 2. 再插入到头部
    }

步骤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) {
            // 键已存在，更新值，并移动到头部
            node.value = value;
            moveToHead(node);
        } else {
            // 键不存在，创建新节点
            Node newNode = new Node(key, value);
            // 添加到链表头部
            addToHead(newNode);
            // 存入哈希表
            cache.put(key, newNode);
            size++;
            // 如果超出容量，删除链表尾部的节点（最久未使用）
            if (size > capacity) {
                Node tailNode = dummyTail.prev; // 尾部虚拟节点的前一个就是实际尾节点
                removeNode(tailNode); // 从链表中移除
                cache.remove(tailNode.key); // 从哈希表中移除
                size--;
            }
        }
    }

复杂度分析

• 时间复杂度：get和put操作都只涉及哈希表的O(1)查找和链表的O(1)增删，因此时间复杂度为O(1)。
• 空间复杂度：哈希表和双向链表存储了最多capacity个元素，因此空间复杂度为O(capacity)。

关键点总结

1. 数据结构选择：哈希表保证O(1)查找，双向链表保证O(1)的顺序调整和删除。
2. 虚拟头尾节点：极大简化了链表边界条件的处理。
3. 访问即更新：无论是get成功访问还是put更新已有键，都需要将该节点移动到链表头部，表示“最近使用”。
4. 淘汰时机：只在插入新键导致size > capacity时，才需要淘汰链表尾部的节点（最久未使用），并同步从哈希表中删除。