为什么使用双链接列表和HashMap用于LRU缓存而不是Deque？

Question

我已经使用传统方法（Doubly Linked List + Hash Map）在LeetCode上实现了LRU Cache问题的设计。对于那些不熟悉这个问题的人，这个实现看起来像这样：

我理解为什么使用这种方法（两端快速删除/插入，中间快速访问）。我无法理解的是，当人们可以简单地使用基于数组的deque（在Java ArrayDeque，C ++中简称deque）时，有人会同时使用HashMap和LinkedList。此双端队列允许在两端轻松插入/删除，并在中间快速访问，这正是LRU缓存所需的。您也可以使用更少的空间，因为您不需要存储指向每个节点的指针。

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

Answer 1

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

如果我们从队列前面丢弃物品，那么我们必须确保前面的物品是最长时间没用过的物品。

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

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

• 当我们在缓存中put一个新项目时，它将成为最近使用的项目，因此我们将它放在队列的后面。
• 当我们get已经在缓存中的项目时，它将成为最近使用的项目，因此我们将其从当前位置移动到队列的后面。

从中间到末尾移动项目不是deque操作，并且ArrayDeque界面不支持。 ArrayDeque使用的基础数据结构也不能有效支持它。使用双向链表是因为它们确实有效地支持了这种操作。

Answer 2

LRU缓存的目的是支持O(1)时间内的两个操作：get(key)和put(key, value)，附加约束条件是首先丢弃最近最少使用的密钥。通常，键是函数调用的参数，值是该调用的缓存输出。

无论你如何处理这个问题，我们都同意你必须使用一个hashmap。您需要一个散列映射来将缓存中已存在的密钥映射到O(1)中的值。

为了处理最先丢弃的最近使用的密钥的附加约束，首先可以使用LinkedList或ArrayDeque。但是，因为我们实际上不需要访问中间，所以LinkedList更好，因为您不需要调整大小。

编辑：

Timmermans先生在他的回答中讨论了为什么ArrayDeques不能用于LRU cache，因为必须从中间到末尾移动元素。在这里说的是LRU cache的一个实现，它成功地使用deque中的附加和poplefts在leetcode上提交。请注意，python的collections.deque实现为双向链表，但是我们只在collections.deque中使用圆形数组中的O(1)，因此算法保持不变。

from collections import deque

class LRUCache:

    def __init__(self, capacity: 'int'):
        self.capacity = capacity
        self.hashmap = {}
        self.deque = deque()

    def get(self, key: 'int') -> 'int':
        res = self.hashmap.get(key, [-1, 0])[0]
        if res != -1:
            self.put(key, res)
        return res

    def put(self, key: 'int', value: 'int') -> 'None':

        self.add(key, value)
        while len(self.hashmap) > self.capacity:
            self.remove()

    def add(self, key, value):
        if key in self.hashmap:
            self.hashmap[key][1] += 1
            self.hashmap[key][0] = value
        else:
            self.hashmap[key] = [value, 1]
        self.deque.append(key)

    def remove(self):
        k = self.deque.popleft()
        self.hashmap[k][1] -=1
        if self.hashmap[k][1] == 0:
            del self.hashmap[k]

我同意Timmermans先生的观点，使用LinkedList方法是可取的 - 但我想强调使用ArrayDeque来构建LRU缓存是可能的。

我和Timmermans先生之间的主要混淆是我们如何解释能力。我的容量意味着缓存最后的N获取/放置请求，而Timmermans先生认为这意味着缓存最后一个N独特的项目。

上面的代码确实在put中有一个循环，它会减慢代码的速度 - 但这只是为了使代码符合缓存最后一个N独特的项目。如果我们将代码缓存改为最后的N请求，我们可以用以下代码替换循环：

if len(self.deque) > self.capacity: self.remove()

如果不比链表变体更快，这将使其快速。

无论maxsize被解释为什么，上述方法仍然可以作为LRU缓存 - 最近最少使用的元素首先被丢弃。

我只想强调，以这种方式设计LRU缓存是可能的。来源就在那里 - 尝试在Leetcode上提交它！