LRU

LRU 缓存到底要做什么？ 在动手写代码之前，最重要的一步是明确我们的目标。LRU 缓存机制的核心是：当缓存满了以后，优先淘汰最久没有被使用过的数据。 我们来分解一下 LRUCache 需要实现的功能： Constructor(capacity int): 初始化一个固定容量的缓存。 Get(key int): 如果 key 存在，返回对应的 value。 关键点：这次访问使得该 key 成为了“最近使用的”，所以需要更新它的位置。 如果 key 不存在，返回 -1。 Put(key int, value int): 如果 key 存在，更新 value。 关键点：这次更新也使得该 key 成为了“最近使用的”，需要更新它的位置。 如果 key 不存在，插入这个新的键值对。 关键点：插入后，如果缓存的尺寸超过了 capacity，则必须淘汰“最久未使用的”那个元素。 总结一下，我们需要一个数据结构，它必须同时满足以下几个要求： 快速查找：Get 和 Put 都需要快速地判断一个 key 是否存在。 有序存储：需要一种机制来记录所有 key 的“新旧”顺序，方便我们找到“最久未使用的”那个。 快速增删：当一个 key 被访问（Get 或 Put）时，我们要能快速地将它移动到“最新”的位置。当缓存满了，也要能快速地删除“最旧”的那个。 哈希表 + 双向链表 这是本题的核心套路。没有任何单一的基础数据结构能同时满足上述所有要求，所以需要组合。 为什么需要哈希表 (map)？ 为了实现 O(1) 复杂度的快速查找。我们可以用 map[int]*Node 来存储 key 到链表节点的映射。 为什么需要链表？ 为了维护元素的“新旧”顺序。链表天然有序。我们可以规定，越靠近链表头部的元素，就是“最近使用”的；越靠近链表尾部的，就是“最久未使用”的。 为什么必须是双向链表，而不是单向？ 因为我们需要 O(1) 复杂度的删除操作。想象一下，当我们要删除一个节点（比如缓存满了要淘汰尾部节点，或者 Get 了一个中间节点要把它移动到头部），我们需要修改这个节点前面那个节点的 Next 指针。在单向链表中，找到前驱节点需要从头遍历，时间复杂度是 O(n)。而双向链表每个节点都存了 Pre 和 Next 指针，使得我们可以在 O(1) 的时间内完成任意节点的删除。 结论：哈希表 (map) + 双向链表 (Doubly Linked List) 是解决此问题的完美组合。...