【LeetCode 热题 100】146. LRU 缓存——哈希表+双向链表

Problem: 146. 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) 缓存。LRU 缓存是一种遵循特定淘汰策略的固定容量缓存：当缓存已满且需要添加新元素时，它会移除最近最少被使用的那个元素。

为了高效地实现这一功能，该算法巧妙地结合了两种数据结构：

1. 哈希表 (HashMap):

   • 代码中是 private final Map<Integer, Node> keyToNode。
   • 作用: 提供 O(1) 平均时间复杂度的快速查找。通过 key，我们可以立即找到对应的链表节点 Node。这是实现高效 get 和 put 的关键。

2. 双向链表 (Doubly Linked List):

   • 代码中是通过 Node 类和一系列指针操作（remove, pushFront）实现的。
   • 作用: 维护数据的“最近使用”顺序。所有节点按照其被访问的先后顺序排列。
     • 队首 (MRU - Most Recently Used): 链表的头部（紧跟在 dummy 节点之后）存放的是最近被访问（get 或 put）的元素。
     • 队尾 (LRU - Least Recently Used): 链表的尾部（dummy 节点的前一个节点）存放的是最久未被访问的元素。
   • 双向链表的优势在于，只要我们有了一个节点的引用（可以从哈希表中O(1)获得），我们就可以在 O(1) 的时间内将该节点从链表的任意位置移除，或移动到头部。

核心操作逻辑:

• get(key): 当一个元素被访问时，它就成为了“最近使用”的。

  1. 通过哈希表快速找到该 key 对应的节点。
  2. 如果找到，就将该节点从其当前位置移动到双向链表的头部。
  3. 返回节点的值。如果未找到，返回 -1。

• put(key, value): 当插入或更新一个元素时，它也成为了“最近使用”的。

  1. 检查是否存在: 通过哈希表检查 key 是否已存在。
  2. 如果存在 (更新): 更新该节点的值，并将其移动到链表头部。
  3. 如果不存在 (插入):
     a. 创建一个新节点。
     b. 将新节点插入到链表的头部。
     c. 在哈希表中添加 key到新节点的映射。
     d. 检查容量: 如果此时缓存的大小超过了 capacity，就需要淘汰最久未使用的元素。
     e. 淘汰 (Eviction): 移除链表的尾部节点，并同时从哈希表中移除该节点的 key。

通过这两种数据结构的协同工作，LRU 缓存得以在平均 O(1) 的时间内完成所有核心操作。

完整代码

class LRUCache {
    // 内部类，定义双向链表的节点结构
    private static class Node {
        int key; // 存储键，便于在淘汰时从哈希表中删除
        int val; // 存储值
        Node prev; // 指向前一个节点
        Node next; // 指向后一个节点

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

    private final int capacity; // 缓存的最大容量
    // dummy 是一个哨兵节点，用于简化链表头尾的操作，避免空指针判断。
    // dummy.next 指向真正的头节点 (MRU)，dummy.prev 指向真正的尾节点 (LRU)。
    private final Node dummy = new Node(0, 0);
    // 哈希表，实现 O(1) 的 key -> Node 查找
    private final Map<Integer, Node> keyToNode = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        // 初始化双向链表为一个空的循环链表，dummy 自己指向自己。
        dummy.prev = dummy;
        dummy.next = dummy;
    }
    
    public int get(int key) {
        // 调用辅助函数 getNode 获取节点。
        // getNode 会自动处理“将节点移动到头部”的逻辑。
        Node node = getNode(key);
        // 如果节点不存在，返回 -1；否则返回节点的值。
        return node == null ? -1 : node.val;
    }
    
    public void put(int key, int value) {
        // 尝试获取节点，如果存在，getNode 会将其移动到头部。
        Node node = getNode(key);
        if (node != null) {
            // Case 1: Key 已存在，更新值即可。
            node.val = value;
            return;
        }
        
        // Case 2: Key 不存在，需要插入新节点。
        node = new Node(key, value);
        // a. 将新节点添加到链表头部 (MRU)
        pushFront(node);
        // b. 在哈希表中建立 key 到新节点的映射
        keyToNode.put(key, node);
        
        // c. 检查是否超出容量
        if (keyToNode.size() > capacity) {
            // d. 淘汰最久未使用的元素 (链表尾部)
            Node lruNode = dummy.prev;
            // 从哈希表中移除
            keyToNode.remove(lruNode.key);
            // 从链表中移除
            remove(lruNode);
        }
    }

    /**
     * 辅助函数：根据 key 获取节点，并将其标记为最近使用（移动到链表头部）。
     */
    private Node getNode(int key) {
        if (!keyToNode.containsKey(key)) {
            return null; // Key 不存在
        }
        // 从哈希表中获取节点引用
        Node node = keyToNode.get(key);
        // 将节点从当前位置移除
        remove(node);
        // 将节点添加到链表头部
        pushFront(node);
        return node;
    }

    /**
     * 辅助函数：从双向链表中移除一个节点。
     */
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /**
     * 辅助函数：将一个节点添加到双向链表的头部。
     */
    private void pushFront(Node node) {
        node.next = dummy.next;
        node.next.prev = node;
        dummy.next = node;
        node.prev = dummy;
    }
}

时空复杂度

时间复杂度：O(1)

1. get(int key):

   • 该操作主要调用 getNode。
   • 在 getNode 中，keyToNode.containsKey 和 keyToNode.get 都是哈希表操作，平均时间复杂度为 O(1)。
   • remove(node) 和 pushFront(node) 是双向链表的指针操作，时间复杂度为 O(1)。
   • 因此，get 方法的平均时间复杂度是 O(1)。

2. put(int key, int value):

   • 该操作首先调用 getNode，耗时 O(1)。
   • 更新情况: 赋值操作是 O(1)。
   • 插入情况: new Node, pushFront, keyToNode.put 都是 O(1) 的平均操作。
   • 淘汰情况: keyToNode.remove 和 remove(lruNode) 也都是 O(1) 的平均操作。
   • 因此，put 方法的平均时间复杂度是 O(1)。

注意：以上分析基于哈希表的平均情况。在极罕见的哈希冲突最坏情况下，哈希表操作可能退化到 O(N)，但通常不作为主要考量。

空间复杂度：O(capacity)

1. 主要存储开销：算法需要存储数据，其存储量与缓存的容量 capacity 直接相关。
2. 哈希表 keyToNode: 在最坏情况下，哈希表会存储 capacity 个键值对。每个键是 Integer，每个值是 Node 的引用。空间复杂度为 O(capacity)。
3. 双向链表: 双向链表最多会存储 capacity 个 Node 对象。每个 Node 对象包含 key, val, prev, next。空间复杂度也为 O(capacity)。

综合分析：
算法所需的额外空间由哈希表和双向链表共同决定，两者都与 capacity 成线性关系。因此，总的空间复杂度为 O(capacity)。

参考灵神