【模拟】LRU 缓存 - 编程导航 | 一线开发者编程经验和技术实战分享

本题也是面试时的高频考点，需要重点掌握。

什么是 LRU 缓存淘汰算法？

LRU（Least Recently Used，最近最少使用） 是一种缓存淘汰算法。当缓存空间已满，需要存入新数据时，就淘汰最近最少使用的数据，也就是最久没有被访问过的数据。

举个生活中的例子：假如你的书桌只能放 5 本书，每次阅读一本书后，就把它放到最顺手的位置。当书桌放满，需要放入一本新书时，就把最久没有翻阅过的那本书收进书架。这就是 LRU 算法的核心思想。

本题要求 get、put 操作必须以 $O(1)$ 的平均时间复杂度运行，所以很容易想到应该使用哈希表来存储数据。

然而，哈希表本身无法维护数据的访问顺序，因此还需要借助另外一个辅助数据结构——双向链表。

之所以选择双向链表而非单链表，是因为本题需要频繁移动已有节点。移动节点时，需要先将其从当前位置删除，再插入链表头部。双向链表的节点同时保存了前驱和后继指针，因此可以在$O(1)$的时间复杂度内找到节点的前驱节点，从而完成删除操作；而单链表无法直接找到前驱节点，通常需要从链表头部遍历查找。因此，双向链表更适合本题的需求。

我们规定：最近使用的数据排在链表最前面，最久未使用的数据排在链表最后面。

为了简化链表操作，我们设置虚拟头节点 head 和虚拟尾节点 tail，所有真实节点都位于两者之间。插入新节点或访问已有节点时，将其放到 head 之后；缓存已满时，删除 tail 之前的真实节点。

接下来，实现 get 和 put 两个操作。

对于 get 操作，先通过哈希表查找对应的节点。如果节点不存在，返回 -1；如果节点存在，将其移动到链表头部，再返回节点中保存的值。

对于 put 操作，先判断 key 是否存在。如果存在，更新节点的值，并将其移动到链表头部；如果不存在，则先判断缓存是否已满。若缓存已满，删除链表尾部的真实节点，并将其对应的 key 从哈希表中移除。然后创建新节点，将其插入链表头部，并在哈希表中记录 key 与节点的对应关系。

这里有一个细节需要注意：链表节点不仅要保存 value，还要保存 key。因为淘汰节点时，需要根据节点的 key 删除哈希表中的对应记录，保证哈希表和链表中的数据始终一致。

最后，我们将双向链表的操作封装成三个辅助方法。removeNode 用于删除指定节点，addNode 用于将节点插入虚拟头节点之后，moveNodeToHead 则通过先删除、再插入的方式，将已有节点移动到链表头部。

实现时，建议先写好双向链表的插入、删除和移动操作，再实现 get 和 put。动手编码前，先理清每个操作对哈希表和链表的影响，可以有效避免逻辑混乱。

参考代码：

▼
java
复制代码
class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> map;
    private final Node head;
    private final Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        Node head = new Node(-1, -1);
        Node tail = new Node(-1, -1);
        head.next = tail;
        tail.pre = head;
        this.head = head;
        this.tail = tail;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        moveNodeToHead(node);
        return node.data;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node == null) {
            // 新的键值对
            if (map.size() == capacity) {
                Node removed = tail.pre;
                removeNode(removed);
                map.remove(removed.key);
            }
            node = new Node(key, value);
            addNode(node);
        } else {
            // 更新旧的键值对
            node.data = value;
            moveNodeToHead(node);
        }
        map.put(key, node);
    }

    private void removeNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void moveNodeToHead(Node node) {
        removeNode(node);
        addNode(node);
    }

    private void addNode(Node node) {
        node.next = head.next;
        head.next.pre = node;
        node.pre = head;
        head.next = node;
    }

    static class Node {
        int key;
        int data;
        Node pre;
        Node next;

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