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

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释:    

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

思路

LRU的核心是要维护一个“最近使用顺序”。

每次访问(get 或 put)一个key，这个key就变成“最新的”。

当容量满了要淘汰时，扔掉那个“最老的”那个。

所以我们需要一个数据结构，能高效的做三件事:

快速查找某个key的值(get要O(1))
快速把某个节点移到“最新”的位置(每次访问后都要更新顺序)
快速找到并删除“最老”的节点(淘汰时用)

哈希表 + 双向链表

单独用一种结构不够:

哈希表(HashMap): 查找是O(1)了，但哈希表没有顺序概念，没法知道谁是最老的，淘汰时得遍历O(n)
链表: 能维护顺序(越靠头越新，越靠尾越老)，但查找某个key得从头遍历O(n)

把两者结合，各取所长:

哈希表负责按key秒找到对应的链表节点 -- 解决查找O(1)
双向链表负责维护使用顺序 -- 头部是最新的，尾部是最老的。

为什么要使用双向链表

因为我们经常要删除链表中间的某个节点(比如get一个中间节点后，要把它移到头部，得先从原位置删掉它)

在单链表里删除一个节点，必须要知道它的前驱，而单链表拿到一个节点没法O(1)找到前驱(得从头遍历)

而双向链表里，每个节点都存了prev和next两个指针，删除时直接node.prev.next = node.next和node.next.prev = node.prev，这样O(1)就搞定，这就是必须使用双向链表的原因。

用两个哨兵简化边界(dummy head + dummy tail)

好处是: 无论链表空不空，插入头部、删除尾部时，永远有前驱和后继可用，不用判断是不是“第一个/最后一个节点”这种烦人的边界。
插入和删除的代码变得及其干净统一。

头部最新、尾部最老

新插入的或刚被访问的节点 --> 移到紧挨head的位置(最新)。
要淘汰时 --> 删除紧挨tail的那个节点(最老)。

两个操作的完整流程

get(key)
- 哈希表里查key，查不到就返回-1。
- 查到了拿到节点，把它移到头部(因为刚被访问，变最新)，返回它的值。
put(key, value)
- 如果key已经存在 --> 更新它的值，并把节点移到头部
- 如果key不存在
  - 新建节点，放进哈希表，插到头部
  - 如果此时超过容量 --> 删除尾部那个最老节点(同时从哈希表里也删掉它)

class LRUCache(private val capacity: Int) {

    /**
     * 双向链表节点：同时存 key 和 value。
     * 存 key 是为了淘汰尾节点时，能反查到它在哈希表里的键并一起删除。
     */
    private class Node(var key: Int, var value: Int) {
        var prev: Node? = null
        var next: Node? = null
    }

    // 哈希表：key → 对应的链表节点，实现 O(1) 查找
    private val map = HashMap<Int, Node>()

    // 两个哨兵节点：head 侧为最新，tail 侧为最老（它们不存真实数据）
    private val head = Node(0, 0)
    private val tail = Node(0, 0)

    init {
        // 初始时链表为空，head 和 tail 直接相连
        head.next = tail
        tail.prev = head
    }

    fun get(key: Int): Int {
        val node = map[key] ?: return -1   // 不存在返回 -1
        moveToHead(node)                   // 刚访问过，移到头部（变最新）
        return node.value
    }

    fun put(key: Int, value: Int) {
        val existing = map[key]
        if (existing != null) {
            // key 已存在：更新值，并移到头部
            existing.value = value
            moveToHead(existing)
            return
        }
        // key 不存在：新建节点，加入哈希表并插到头部
        val node = Node(key, value)
        map[key] = node
        addToHead(node)

        // 超过容量：淘汰尾部最老节点，并从哈希表删除
        if (map.size > capacity) {
            val lru = removeTail()
            map.remove(lru.key)
        }
    }

    // --- 以下是三个私有的链表操作辅助方法 ---

    /** 把一个节点插入到 head 哨兵之后（即最新位置） */
    private fun addToHead(node: Node) {
        node.prev = head
        node.next = head.next
        head.next!!.prev = node
        head.next = node
    }

    /** 把一个节点从链表中摘除（利用双向指针，O(1)） */
    private fun removeNode(node: Node) {
        node.prev!!.next = node.next
        node.next!!.prev = node.prev
    }

    /** 把一个已在链表中的节点移动到头部 = 先摘除，再插到头部 */
    private fun moveToHead(node: Node) {
        removeNode(node)
        addToHead(node)
    }

    /** 删除并返回尾部（tail 哨兵之前）的最老节点 */
    private fun removeTail(): Node {
        val lru = tail.prev!!
        removeNode(lru)
        return lru
    }
}

复杂度

时间复杂度: O(1)
空间复杂度: O(capacity)哈希表和链表最多同时存 capacity 个节点。

下一题

邮箱：charon.chui@gmail.com
Good Luck!