为什么要引入LFU算法呢?因为LRU算法淘汰数据的立足点是根据使用时间间隔淘汰数据,将当前内存中最长时间没有使用过的数据清理掉。这样就存在一个问题:如果一个不会经常使用的数据偶然被使用了一次,那这个并不被经常使用的数据就会一直待在内存中,浪费内存空间。如果我们想淘汰内存中不经常使用的数据,保留经常使用的热点数据,就要使用到LFU算法了。
LFU的全称为Least Frequently Used,意思就是最不频繁使用,所以,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算法完整的数据结构:
基于上面的数据结构,我们就可以实现完整的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算法实现简单,只需要一个hash表+一个双向链表即可实现;LFU算法实现就复杂很多,需要两个hash表+多个双向链表才能实现。
具体使用时,选择哪种算法作为内存淘汰策略要看具体场景,如果对于热点数据的查询要求比较高,则最好采用LFU算法作为内存淘汰策略。如果没有那么高的热点数据要求,则可以选择实现更为简单的LRU算法。