我在一次采访中被问到这个问题，他首先问了 LRU 和 LFU 之间的区别，然后要求实现两者。我知道 LRU 可以通过 LinkedHashMap 实现，但我对 LFU 感到困惑。谁能告诉我如何用最简单的数据结构来实现它并有很好的解释？ 也可以用LinkedHashMap来实现吗？
最佳答案
假设缓存条目已键入，您可以使用队列 (LinkedList) 和映射 (HashMap) 来实现。
(假设队列和 map 已满)
为队列选择一个绑定(bind)的b。在每个缓存请求中，将所请求页面的键推送到队列中，然后轮询队列。
如果您想要的页面在 map 中，请返回该页面。如果页面不在 map 中，请在队列中查找最不常出现的键，该键也在 map 中或您想要的页面的键中。如果该键是您想要的页面的键，则无需执行任何操作；否则从 map 中删除该键的条目并将您的页面插入到 map 中。
返回您的页面。
缓存命中的复杂度为 O(1)，未命中的复杂度为 O(b)。
这假设您想要限制频率。 IE。 “最近 b 请求中最不常用”而不是“有史以来最不常用”。
关于java - 如何使用最简单、最少的数据结构来实现 LFU 缓存？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37759551/