LeetCode 面试题 16.25. LRU 缓存

2026-08-25 HGNULB 约 7 分钟

文章信息 12 个分类 4 个标签

分类

LeetCode CodeTop 中等未解决 10-20 程序员面试金典（第 6 版）腾讯字节阿里美团拼多多京东

题目描述

✅ 面试题 16.25. LRU 缓存

题意分析

缓存容量固定，get(key) 返回对应值，未命中返回 -1；put(key, value) 更新或插入键值，容量不足时淘汰最久未使用的一项。命中读取、更新已有键和新增都算一次使用，未命中的读取不改变顺序。

要让两种操作平均为 O(1)，既要按键快速找到数据，也要随时把指定项移到最新位置，并找到最旧项。单独的哈希表不能维护这个顺序，单独的链表又不能快速按键定位。

解法：哈希表 + 双向链表

核心思路

[!blue]

哈希表保存 key → 节点，双向链表保存这些节点的使用顺序：head 之后是最近使用的节点，tail 之前是最久未使用的节点。每次操作结束时，哈希表与链表包含完全相同的一批真实节点，且每个键只有一个节点。

找到节点后，通过它的 prev、next 让前后邻居直接相连，就能在 O(1) 时间将它摘下；再把它插到头部，表示刚刚使用。其他节点的相对顺序没有变化，因此链表仍按最近使用时间从新到旧排列。新键也放在头部；更新旧键只修改原节点，不增加节点数量。

超出容量时，tail.prev 必然是最久未使用项。删除它后，还要用节点中保存的 key 删除哈希表记录，两个结构才能保持一致。每次只新增一个节点，因此至多淘汰一个就能恢复容量限制。

head、tail 是不存缓存数据的哨兵，空表时也彼此相连。真实节点始终有前后邻居，所以移除首节点、尾节点或唯一节点都使用同一套指针操作；哨兵不进入哈希表，也不计入容量。

解题步骤

初始化哈希表和首尾哨兵，并令 head.next = tail、tail.prev = head。

get 未命中返回 -1；命中则把节点移到头部再返回值。

put 命中已有 key 时更新值、移到头部并结束，缓存数量不变。

新 key 创建节点，同时写入哈希表并插到链表头部。

若数量超过容量，删除 tail.prev，再用该节点的 key 清理哈希表。

移动已有节点必须先摘下再头插。头插时先让新节点连接旧首节点，并修改旧首节点的 prev，最后更新 head.next，这样不会丢失原来的链表。

代码实现

class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> cache = new HashMap<>();
    private final Node head = new Node(0, 0);
    private final Node tail = new Node(0, 0);

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = cache.get(key);

        if (node == null) {
            return -1;
        }

        moveToHead(node);

        return node.value;
    }

    public void put(int key, int value) {
        Node node = cache.get(key);

        if (node != null) {
            node.value = value;
            moveToHead(node);

            return;
        }

        node = new Node(key, value);
        cache.put(key, node);
        addToHead(node);

        if (cache.size() > capacity) {
            Node removed = tail.prev;

            remove(removed);
            // 淘汰时同步删除哈希索引，链表与哈希表必须引用同一批有效节点。
            cache.remove(removed.key);
        }
    }

    private void moveToHead(Node node) {
        remove(node);
        addToHead(node);
    }

    private void addToHead(Node node) {
        node.prev = head;
        // 先保存旧首节点的连接，最后再更新头哨兵的后继。
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private static class Node {
        final int key;
        int value;
        Node prev;
        Node next;

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

type LRUCache struct {
    capacity int
    cache    map[int]*lruNode
    head     *lruNode
    tail     *lruNode
}

type lruNode struct {
    key, value int
    prev, next *lruNode
}

func Constructor(capacity int) LRUCache {
    head, tail := &lruNode{}, &lruNode{}
    head.next = tail
    tail.prev = head
    return LRUCache{
        capacity: capacity,
        cache:    make(map[int]*lruNode),
        head:     head,
        tail:     tail,
    }
}

func (cache *LRUCache) Get(key int) int {
    node := cache.cache[key]
    if node == nil {
        return -1
    }
    cache.moveToHead(node)
    return node.value
}

func (cache *LRUCache) Put(key int, value int) {
    if node := cache.cache[key]; node != nil {
        node.value = value
        cache.moveToHead(node)
        return
    }

    node := &lruNode{key: key, value: value}
    cache.cache[key] = node
    cache.addToHead(node)

    if len(cache.cache) > cache.capacity {
        removed := cache.tail.prev
        cache.remove(removed)
        // 淘汰时同步删除哈希索引，链表与哈希表必须引用同一批有效节点。
        delete(cache.cache, removed.key)
    }
}

func (cache *LRUCache) moveToHead(node *lruNode) {
    cache.remove(node)
    cache.addToHead(node)
}

func (cache *LRUCache) addToHead(node *lruNode) {
    node.prev = cache.head
    // 先保存旧首节点的连接，最后再更新头哨兵的后继。
    node.next = cache.head.next
    cache.head.next.prev = node
    cache.head.next = node
}

func (cache *LRUCache) remove(node *lruNode) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

复杂度分析

时间复杂度：get、put 平均都是 $O(1)$。哈希表操作平均为常数时间，摘链、头插和删尾都只修改固定数量的指针。

空间复杂度：$O(capacity)$。操作结束后最多保留 capacity 个真实节点，哈希表为这些节点保存索引；新增时临时多出一个节点不影响量级。

关键点总结

[!green]

哈希表负责找到节点，双向链表负责移动节点，两者共同保证平均常数时间。

移到头部只改变当前节点的使用时间，其余节点的先后顺序应保持不变。

淘汰总是从尾部进行，并同步删除哈希索引。

易错点总结

[!yellow]

get 命中和 put 更新都要刷新使用顺序，未命中的 get 则不改链表。

更新旧键后立即结束，不能继续创建同键节点或错误淘汰其他项。

摘链必须同时修改两个方向的连接；只改 next 会让后续操作沿着错误的 prev 访问节点。

哨兵没有真实缓存含义，不能把它们计入容量或选作淘汰对象。

相似题目

题目	难度	关联与区别
460. LFU 缓存	困难	同样需要常数时间定位与更新淘汰顺序，LFU按频率分组，LRU只按最近使用顺序。
432. 全 O(1) 的数据结构	困难	同样结合哈希定位与双向链表维护动态顺序，原题维护频次桶，本题维护访问顺序。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/20444064

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！