java - 如何使用最简单、最少的数据结构来实现 LFU 缓存？

Question

这个问题已经有答案了:

What is the difference between LRU and LFU (4 个回答)

已关闭 7 年前。

我在一次采访中被问到这个问题，他首先问了 LRU 和 LFU 之间的区别，然后要求实现两者。我知道 LRU 可以通过 LinkedHashMap 实现，但我对 LFU 感到困惑。谁能告诉我如何用最简单的数据结构来实现它并有很好的解释？也可以用LinkedHashMap来实现吗？

Answer 1

假设缓存条目已键入，您可以使用队列 (LinkedList) 和映射 (HashMap) 来实现。

(假设队列和 map 已满)
为队列选择一个绑定(bind)的b。在每个缓存请求中，将所请求页面的键推送到队列中，然后轮询队列。
如果您想要的页面在 map 中，请返回该页面。如果页面不在 map 中，请在队列中查找最不常出现的键，该键也在 map 中或您想要的页面的键中。如果该键是您想要的页面的键，则无需执行任何操作；否则从 map 中删除该键的条目并将您的页面插入到 map 中。
返回您的页面。

缓存命中的复杂度为 O(1)，未命中的复杂度为 O(b)。
这假设您想要限制频率。 IE。 “最近 b 请求中最不常用”而不是“有史以来最不常用”。