LRU 缓存

难度: Medium

请你设计并实现一个满足 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 <= 10⁵
最多调用 2 * 10⁵ 次 get 和 put

Submission

运行时间: 196 ms

内存: 23.4 MB

class Node:
    
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None
        self.prev = None


class DoubleList:

    def __init__(self):
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1
    
    def remove_first(self):
        if self.head.next == self.tail:
            return
        first = self.head.next
        self.remove(first)
        return first

    def add_last(self, node):
        node.prev = self.tail.prev
        node.next = self.tail
        node.prev.next = node
        self.tail.prev = node
        self.size += 1


class LRUCache:

    def __init__(self, capacity: int):
        self.map = dict()
        self.cache = DoubleList()
        self.capacity = capacity        

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        self.make_recent(key)
        return self.map[key].val

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self.delete_key(key)
            self.add_recent(key, value)
            return
        
        if self.capacity == len(self.map):
            self.remove_least_recent()

        self.add_recent(key, value)

    def make_recent(self, key):
        node = self.map[key]
        self.cache.remove(node)
        self.cache.add_last(node)
    
    def add_recent(self, key, val):
        node = Node(key, val)
        self.cache.add_last(node)
        self.map[key] = node

    def delete_key(self, key):
        node = self.map[key]
        self.cache.remove(node)
        del self.map[key]
    
    def remove_least_recent(self):
        node = self.cache.remove_first()
        del self.map[node.key]

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

Explain

该题解采用哈希表和双向链表实现了一个 LRU 缓存机制。哈希表用于存储每个节点的引用，以便快速定位节点并在 O(1) 时间内完成删除或更新。双向链表用于按照访问的顺序存储节点，使得最近访问的节点总是移动到链表末尾，而最久未访问的节点位于链表头部。当缓存容量满时，链表头部的节点（即最久未访问的节点）被删除。

时间复杂度: O(1)

空间复杂度: O(capacity)

class Node:
    
    def __init__(self, key, val):
        self.key = key  # 节点存储键
        self.val = val  # 节点存储值
        self.next = None  # 指向下一个节点
        self.prev = None  # 指向上一个节点


class DoubleList:

    def __init__(self):
        self.head = Node(0, 0)  # 初始化头结点
        self.tail = Node(0, 0)  # 初始化尾节点
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0  # 链表大小

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1  # 删除节点时减少链表大小
    
    def remove_first(self):
        if self.head.next == self.tail:
            return
        first = self.head.next
        self.remove(first)
        return first  # 返回被删除的第一个节点

    def add_last(self, node):
        node.prev = self.tail.prev
        node.next = self.tail
        node.prev.next = node
        self.tail.prev = node
        self.size += 1  # 添加节点时增加链表大小


class LRUCache:

    def __init__(self, capacity: int):
        self.map = dict()  # 哈希表存储键到节点的映射
        self.cache = DoubleList()  # 双向链表存储节点
        self.capacity = capacity        

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1  # 如果键不存在，返回-1
        self.make_recent(key)
        return self.map[key].val  # 返回键对应的值

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self.delete_key(key)
            self.add_recent(key, value)
            return
        
        if self.capacity == len(self.map):
            self.remove_least_recent()  # 移除最久未使用的节点

        self.add_recent(key, value)  # 添加最新的节点

    def make_recent(self, key):
        node = self.map[key]
        self.cache.remove(node)
        self.cache.add_last(node)  # 将节点移动至链表末尾
    
    def add_recent(self, key, val):
        node = Node(key, val)
        self.cache.add_last(node)
        self.map[key] = node  # 在哈希表中更新或添加键与节点的映射

    def delete_key(self, key):
        node = self.map[key]
        self.cache.remove(node)
        del self.map[key]  # 从哈希表中删除键
    
    def remove_least_recent(self):
        node = self.cache.remove_first()
        del self.map[node.key]  # 删除最少使用的节点

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

Explore

双向链表能够提供前驱和后继节点的直接访问，这使得节点的添加和删除操作可以在O(1)时间内完成。在LRU缓存中，需要频繁地移除最老的节点（位于链表头部）以及移动最近访问的节点到链表尾部。使用双向链表，可以直接通过节点的前驱和后继链接进行快速的删除和添加，而无需像单向链表那样需要从头遍历到特定位置，这显著提高了效率。

在LRU缓存的实现中，双向链表的头部始终指向最久未使用的节点。因此，当缓存达到最大容量需要移除最老元素时，可以直接访问链表的头部节点（头结点的下一个节点），并利用双向链表的结构特性，在O(1)时间内删除该节点。同时，使用哈希表记录节点的键与链表中对应节点的映射，也可以快速从哈希表中移除该节点的键。

虽然直接更新节点值在某些情况下是可行的，但在LRU缓存机制中，除了更新值，还需要将对应节点移动到链表的末尾表示最近使用过。如果仅仅更新值而不移动节点，那么节点的位置将不正确地反映其最近一次的访问顺序。因此，通常的做法是将旧节点从链表中移除并重新添加到链表末尾，这样可以保证节点顺序的正确性和访问的最新性。

在多线程环境下，当多个线程同时操作LRU缓存时，可能会引发数据竞争和一致性问题。例如，一个线程在读取某个节点的同时，另一个线程可能正在修改或删除该节点，这可能导致不一致的状态或程序崩溃。为了解决这些问题，需要引入锁机制或者其他同步工具来确保每次只有一个线程可以修改链表和哈希表，从而保证操作的原子性和数据的一致性。