LRU缓存设计

Question

最近最少使用（LRU）缓存是先丢弃最近最少使用的项目，你是如何设计和实现这样一个缓存类的呢？设计要求如下：

1. 尽可能快地找到物品

2）一旦缓存未命中并且缓存已满，我们需要尽快替换最近最少使用的项目。

如何从设计模式和算法设计的角度来分析和实现这个问题？

原文由 user297850 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

链表 + 指向链表节点的指针哈希表是实现 LRU 缓存的常用方法。这给出了 O(1) 操作（假设一个体面的散列）。这样做的好处（O(1)）：你可以通过锁定整个结构来做一个多线程版本。您不必担心粒度锁定等。

简而言之，它的工作方式：

在访问一个值时，您将链表中的相应节点移动到头部。

当您需要从缓存中删除一个值时，您从尾部删除。

向缓存中添加值时，只需将其放在链表的开头即可。

感谢 doublep，这里有一个 C++ 实现的站点： Miscellaneous Container Templates 。

原文由 Aryabhatta 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

我们必须创建一个允许我们同时优化所有三个主要操作的数据结构。

根据上图，我们可以推断：

• 对于一般情况，使用树将是最佳选择。

• 如果我们知道缓存的大小足够大（并且新元素的插入频率足够低）以至于很少需要删除最旧的条目，那么哈希表将是最佳选择。

• 如果删除旧条目比存储条目或查找缓存元素更重要，则链表可能是一个有效的选择：但在这种情况下，缓存基本上是无用的，添加它不会带来任何好处。

• 在所有情况下，存储 n 个条目所需的内存都是 O(n)。

现在我最喜欢的问题是，我们能做得更好吗？

单个数据结构可能不足以构建最有效的问题解决方案。一方面，我们拥有特别适合快速存储和检索条目的数据结构。如果这是游戏，哈希表几乎是不可能被击败的。另一方面，哈希表在维护事物的顺序时很糟糕，在检索它们包含的最小（或最大）元素时它们也不是很好，但是我们有其他结构可以很好地处理这个问题。根据我们想要保留的顺序，我们可能需要树，或者我们可以使用列表。

我们只需要对缓存条目进行排序，就可以从最少使用到最近使用。由于顺序仅基于插入时间，因此新元素不会改变旧元素的顺序；因此，我们不需要任何花哨的东西：我们只需要一个支持 FIFO 的结构。我们可以只使用列表或队列。当我们事先不知道我们必须存储的元素数量或数量可以动态变化时，链表通常是最佳选择，而队列通常使用数组实现（因此在维度上更静态），但针对头部插入和尾部移除进行了优化。

链表还可以支持在其末端快速插入/删除。然而，我们需要一个双向链表，我们在前面插入元素并从尾部删除它们。通过始终保持指向尾部的指针以及从每个节点到其前身的链接，我们可以在 O(1) 时间内实现尾部删除。

您可以看到为缓存存储并需要在每次操作后更新的树数据元素： (1) 哈希表。 (2) 双向链表的头部。 (3) 指向列表中最后一个元素的指针。请注意哈希表中的每个元素如何指向列表中存储所有数据的节点。为了从一个列表条目到相应的哈希条目，我们必须对存储在节点中的公司名称进行哈希处理，这是表的键。

我们分别考虑了哈希表和链表，但我们需要让它们同步工作。我们可能会在缓存中存储非常大的对象，并且我们绝对不想在两种数据结构中复制它们。避免重复的一种方法是将条目仅存储在其中一个结构中并从另一个结构中引用它们。我们可以将条目添加到哈希表中，并将哈希表的密钥存储在另一个 DS 中，反之亦然。

现在，我们需要决定哪个数据结构应该保存这些值，哪个应该留给引用。最好的选择是让哈希表条目存储指向链表节点的指针，并让后者存储实际值。 （如果我们做相反的事情，那么我们从链表节点链接到哈希表条目的方式将与哈希表的实现相关联。如果我们使用链接，它可能是开放寻址的索引或指针。这与实现的耦合既不是好的设计，也不是通常可能的，因为您通常无法访问标准库内部）。

此缓存称为 least recently used 。它不是最近添加的。这意味着排序不仅基于我们第一次将元素添加到缓存的时间，还基于最后一次访问它。

• 当我们向缓存中添加一个新条目时，当我们有一个 缓存未命中，试图访问一个不在缓存中的元素时，我们只需在链表的前面添加一个新条目。

• 但是当我们遇到 缓存命中，访问一个确实存储在缓存中的元素时，我们需要将现有的列表元素移动到列表的前面，只有当我们都能以常量检索时，我们才能有效地做到这一点 (我们仍然需要包括计算我们查找的条目的每个哈希值的时间。） time 指向现有条目的链表节点的指针（据我们所知，它可能在列表中的任何位置），并删除一个以恒定时间从列表中取出元素（同样，我们需要一个双向链表；对于基于数组的队列实现，在队列中间移除需要线性时间）。

• 如果缓存已满，我们需要删除最近最少使用的条目，然后才能添加新条目。在这种情况下，删除最旧条目的方法可以在恒定时间内访问链表的尾部，从中恢复要删除的条目。为了在哈希表上找到它并从中删除它，我们需要以额外的成本对条目（或其 ID）进行哈希处理（可能是非常量：对于字符串，它将取决于字符串的长度）。

原文由 Yilmaz 发布，翻译遵循 CC BY-SA 4.0 许可协议