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

This question already has answers here:

What is the difference between LRU and LFU
                                
                                    （3个答案）
                                
                        
                                3年前关闭。
            
                    
在一次采访中有人问我这个问题，他首先询问LRU和LFU之间的区别，然后要求同时实施两者。我知道可以通过LinkedHashMap实现LRU，但是我对LFU感到困惑。谁能告诉我如何使用最简单的数据结构并进行很好的解释来实现它？
也可以用LinkedHashMap实现吗？

最佳答案

假设缓存条目被键入密钥，则可以使用队列（LinkedList）和映射（HashMap）来完成。

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

缓存命中的复杂度为O（1），未命中的复杂度为O（b）。
假设您要限制频率。即。 “最近b次请求中最不常用”，而不是“有史以来最不频繁使用”。