LFU算法介绍
为什么要引入LFU算法呢？因为LRU算法淘汰数据的立足点是根据使用时间间隔淘汰数据，将当前内存中最长时间没有使用过的数据清理掉。这样就存在一个问题：如果一个不会经常使用的数据偶然被使用了一次，那这个并不被经常使用的数据就会一直待在内存中，浪费内存空间。如果我们想淘汰内存中不经常使用的数据，保留经常使用的热点数据，就要使用到LFU算法了。
LFU的全称为Least Frequently Used，意思就是最不频繁使用，所以，LFU算法会淘汰掉使用频率最低的数据。如果存在相同使用频率的数据，则再根据使用时间间隔，将最久未使用的数据淘汰。
LFU算法原理
上篇文章 LRU算法详解 中，LRU算法的实现使用了一个hash表+一个双向链表，hash表中存储了key值对应的具体node节点，node节点之间组成了一个双向链表，这样既提高了查询效率，又提高了操作效率。同样作为内存淘汰算法，LFU也需要使用类似的数据结构实现，不过LFU算法淘汰数据是基于使用频率的，所以，我们需要快速找到同一频率的所有节点，然后按照需要淘汰掉最久没被使用过的数据。所以，首先我们要有一个hash表来存储每个频次对应的所有节点信息，同时为了保证操作效率，节点与节点之间同样要组成一个双向链表，得到如下结构：
hash表中的key表示访问次数，value就是一个双向链表，链表中所有节点都是被访问过相同次数的数据节点。可以看到，相比较于LRU算法中的节点信息，LFU算法中节点的要素中除了包含具体的key和value之外，还包含了一个freq要素，这个要素就是访问次数，同hash表中的key值一致。这样做的好处是当根据key查找得到一个节点时，我们可以同时得到该节点被访问的次数，从而得到当前访问次数的所有节点。
有了LFU算法的主体结构之后，我们发现还缺少一个重要功能，就是如何根据key值获取value值。所以，参考LRU算法的数据结构，我们还需要有一个hash表来存储key值与节点之间的对应关系。最终，我们就可以得到LFU算法完整的数据结构：
LFU算法实现
基于上面的数据结构，我们就可以实现完整的LRU算法功能。首先看下查询数据的get操作的具体逻辑：
如果key不存在返回null；
如果key存在，则返回对应节点的value值。同时，需要将节点的访问次数+1，然后将该节点从原双向链表中移除，添加到新的访问次数对应的双向链表中。注意：如果原来访问次数对应的双向链表在移除该节点之后，只剩下了head节点和tail节点，说明没有真实的业务数据节点存在，则需要从访问次数hash表中移除这个链表。
为了方便理解，我从网上找了两个动态流程图可以参考：
（1）https://pic.leetcode-cn.com/00ec8b79c1ada23bb3910f81d688468cd0cc5179f85f9c266a5c76e827c3cdd6-4.gif
（2）https://pic.leetcode-cn.com/d652bc2345cf6b0ad980c8d7dae2c905b926a23e85fcd1c7270751786a353019-5.gif
然后再看下操作数据的put操作的具体逻辑：
如果key已经存在，则更新对应节点的value值，然后将该节点的访问次数+1，然后将该节点从原双向链表中移除，添加到新的访问次数对应的双向链表中。注意：如果原来访问次数对应的双向链表在移除该节点之后，只剩下了head节点和tail节点，说明没有真实的业务数据节点存在，则需要从访问次数hash表中移除这个链表。
如果key不存在，则执行新增数据的动作：
如果还未达到最大容量，则插入新的数据节点。节点的访问次数为1，如果hash表中不存在对应的双向链表则需要先创建链表；
如果超过了最大容量，则需要先删除访问次数最低的节点，再插入新节点。节点的访问次数为1，如果hash表中不存在对应的双向链表则需要先创建链表。
为了方便理解，我也找了一个put操作的动态流程图作为参考：
https://pic.leetcode-cn.com/f9cbf292271ab715f5dab1f08bb0bab834fae7d24d26cc675ee0cc4fdb2f18c7-6.gif
清楚了具体实现逻辑，接下来就可以通过代码实现LFU算法了：
执行程序，输出结果如下：
LRU和LFU对比
LRU算法淘汰数据的注重点是时间间隔，只淘汰最久未使用的数据；LFU算法淘汰数据的注重点是使用频率，只淘汰最不经常使用的数据。
LRU算法实现简单，只需要一个hash表+一个双向链表即可实现；LFU算法实现就复杂很多，需要两个hash表+多个双向链表才能实现。
具体使用时，选择哪种算法作为内存淘汰策略要看具体场景，如果对于热点数据的查询要求比较高，则最好采用LFU算法作为内存淘汰策略。如果没有那么高的热点数据要求，则可以选择实现更为简单的LRU算法。
