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

Question

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

Answer 1

假设缓存条目是键控的，您可以使用队列 ( LinkedList) 和映射 ( HashMap) 来完成。

（假设队列和地图已满）为队列
选择一个边界b。在每个缓存请求中，将请求页面的键推送到队列中，然后轮询队列。
如果您想要的页面在地图中，则返回该页面。如果页面不在地图中，请在队列中找到出现频率最低的键，该键也在地图中或您想要的页面的键中。如果该键是您想要的页面的键，则什么也不做；否则从地图中删除该键的条目并将您的页面插入地图。
返回您的页面。

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