algorithm - 为什么对 LRU 缓存使用双向链表和 HashMap 而不是双端队列？

Question

我在LeetCode上用常规的方法(双向链表+Hash Map)实现了一个LRU Cache Problem的设计。对于那些不熟悉这个问题的人，这个实现看起来像这样:

明白为什么要用这个方法了(两端快拔/插，中间快进)。我无法理解的是，为什么有人可以同时使用 HashMap 和 LinkedList 而可以简单地使用基于数组的双端队列(在 Java ArrayDeque 中，C++ 只是双端队列)。这个双端队列允许在两端轻松插入/删除，并在中间快速访问，这正是 LRU 缓存所需要的。您还可以使用更少的空间，因为您不需要存储指向每个节点的指针。

为什么 LRU 缓存几乎普遍设计(至少在大多数教程中)使用后一种方法而不是 Deque/ArrayDeque 方法，这是有原因的吗？ HashMap/LinkedList 方法有什么好处吗？

Answer 1

当 LRU 缓存已满时，我们会丢弃最近最少使用项。

如果我们要丢弃队列前面的项目，那么，我们必须确保最前面的项目是最长时间未使用的项目。

我们通过确保一个项目在被使用时排到队列的后面来确保这一点。最前面的项目就是最长时间没有被移到后面的项目。

为此，我们需要在每次put 或get 操作时维护队列:

• 当我们将一个新项目放入缓存时，它会成为最最近使用的项目，所以我们将它放在队列的后面。

• 当我们获取一个已经在缓存中的项目时，它成为最最近使用的项目，所以我们移动它从当前位置到队列的后面。

将项目从中间移动到末尾不是双端队列操作，ArrayDeque 接口(interface)不支持。 ArrayDeque 使用的底层数据结构也不能有效地支持它。使用双向链表是因为它们确实有效地支持此操作。