caching - 如何存储几百万个缓存，然后跟踪 20 个最旧的缓存

Question

我收到一个面试问题，说我需要存储几百万个缓存，然后我需要跟踪 20 个最旧的缓存，一旦缓存收集的阈值增加，就用下一组最旧的缓存替换 20 个最旧的缓存。

我回答要为它保留一个 hashmap，这个问题再次增加了如果我们想快速访问 hashmap 上的任何元素怎么办，怎么办，所以我告诉它的 map 所以访问不会花时间，但面试官并不满意。那么对于这种情况应该是什么空闲方式。

Answer 1

队列非常适合查找和删除最旧的成员。

实现为双向链表的队列在两端都有 O(1) 的插入和删除。

优先级队列有助于为队列中的不同项目赋予不同的权重（例如，重新创建某些队列元素可能比其他元素更昂贵）。

您可以使用哈希映射来保存实际元素并根据哈希键快速找到它们，并使用哈希键队列来跟踪缓存元素的年龄。

Answer 2

通过对队列使用双链表并维护元素的哈希映射，您应该能够创建支持最大大小的缓存（甚至是 LRU 缓存）。这应该导致对对象的引用被存储 3 次，而不是对象被存储两次，如果你实现了这个，一定要检查这个（避免这种情况的简单方法是只对哈希键进行排队）

检查溢出时，您只需将最后一项从队列中弹出，然后将其从哈希图中删除

访问项目时，您可以使用哈希映射来查找缓存的项目。然后，如果您正在实现 LRU 缓存，您只需将其从队列中删除并将其添加回开头，this.

通过使用这种结构，插入、更新、读取、删除都将是O(1).

接下来的问题是，面试官会询问项目是否具有每个缓存项目不同的生存时间 (TTL)。为此，您需要有另一个队列来维护按生存时间排序的项目，这里唯一的问题是插入现在变成O(n)了，因为您必须扫描 TTL 队列并找到过期点，因此您必须决定是否将 TTL 队列存储为 n 树的内存使用是值得的（从而产生O(log n)插入时间）。或者您可以将您的 TTL 队列实现为每 ~ 1 分钟间隔或类似的存储桶，您O(1)仍然会得到 ~ 插入，并且只会稍微降低到期后台进程的性能，但不会大大降低（这是一个后台进程）。