为什么将双链接列表和HashMap用于LRU缓存而不是双端队列？

Question

我已经使用常规方法（双链表+哈希映射）在LeetCode上实现了LRU缓存问题的设计。对于那些不熟悉该问题的人，此实现看起来像这样：

我知道为什么要使用这种方法（两端都快速移除/插入，中间快速访问）。我无法理解的是为什么当人们只使用基于数组的双端队列（在Java ArrayDeque中，C ++只是双端队列）时，为什么有人同时使用HashMap和LinkedList的原因。此双端队列使两端的插入/删除操作变得容易，并且在中间可以快速访问，这正是LRU缓存所需要的。您还可以使用更少的空间，因为您不需要存储指向每个节点的指针。

是否有理由为什么使用后一种方法而不是Deque / ArrayDeque方法对LRU缓存进行几乎通用的设计（至少在大多数教程中如此）？HashMap / LinkedList方法有什么好处吗？

Answer 1

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

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

我们通过确保每当一个项目进入到队列的后面确保这一点被使用。那么前面的项目就是没有被最长移到后面的项目。

为此，我们需要在每个putOR get操作上维护队列：

• 当我们put的新项目在缓存中，就变成了最最近使用的项目，所以我们把它在队列的后面。

• 当我们get已在高速缓存中的项目，就成了最最近使用的项目，所以我们移动它从当前位置到队列的后面。

将项目从中间移到末尾不是划定的操作，并且ArrayDeque界面不支持。ArrayDeque使用的基础数据结构也没有有效地支持它。使用双链表是因为它们确实有效地支持此操作。