上一篇文章介绍了LRU算法的设计方法，也就是LRU缓存算法的设计方法，今天我们还将讨论其他的缓存策略LFU。 现在，博客的个人博客已经公开，也刊登了后期相关的文章。 如果你感兴趣，在上面学习，点击就可以去文青乐园
1 LFU基本上介绍LFU。 全名是Least Frequently Used，不经常使用策略。 在一段时间内，数据使用频率最低，优先处置。 据维基百科介绍，最低使用量(LFU )是用于管理计算机内存的缓存算法，主要记录并跟踪内存块的使用次数，如果缓存已满需要更多空间，系统将使用最低内存块采用LFU算法最简单的方法是为加载到缓存中的每个块分配计数器，每次引用该块时计数器增加一，当缓存达到容量，新的存储器块等待插入时，计数器最低的块
上图为LFU的简单实现思路：
在链表的开头插入元素，每插入一次计数，就按次数对链表进行排序。 如果次数相同，按照插入时间顺序排序，从链表末尾选择淘汰的数据的思路，接下来设计LFU算法。
2 LFU算法实现2.1节点定义首先节点中必须包含key和value，主要是存储合适的数据所必需的； 基于以上思路，LFU的主要实现思想是比较访问次数，在需要以相同次数比较节点时间的情况下，由于越早输入的节点越早被淘汰，所以在节点中加入time和count属性，分别计算节点的访问时间和访问时间因为比较时间和次数需要比较方法，所以节点必须实现comparable接口并重写compareTo方法。 方法中的具体逻辑是首先比较节点的访问次数，在访问次数相同的情况下通过比较节点的访问时间，在排序方法中通过比较key来选择淘汰的key。 如果有以上分析，以下是预定义Node节点的代码。
/* * @ authorlikangmin * @ version 1.0 * @ create 2021/3/2414336029 * @ desc */publicclassnodeimplementscomparablenode//** *访问时间* /长时间； /** *访问量*/int count； publicnode(objectkey，Object value，long time，int count ) { this.key=key； this.value=value； this.time=time； this.count=count； }公共对象获取键() { return key； }publicvoidsetkey(objectkey ) { this.key=key； } public Object getValue () { return value； } public void setvalue (object value ) { this.value=value； } public long getTime () { return time； }publicvoidsettime(longtime ) { this.time=time； } public int getCount () { return count； }publicvoidsetcount(intcount ) { this.count=count； } @ overridepublicintcompareto (nodeo ) int compare=integer.com pare (this.count，o.count )； //以相同数量比较时间if(compare==0) (returnlong.compare ) this.time，o.time )； } return compare； }} 2.2 LFU类的定义定义了LFU类，这里使用声明为k和v的总称。 它还包含用于维护所有节点的总容量和一个映射(caches )。 我们将size传递给了构建方法，并创建了链接的hashmap。 采用链接hashmap的主要原因是保持key的顺序。 对应的代码如下所示。
/* * @ authorlikangmin * @ version 1.0 * @ create 2021/3/2414336051 * @ desc */publicclasslfuk，V { /** *总容量*
/ private int capacity; /** * 所有的node节点 */ private Map<K, Node> caches; public Map<K, Node> getCaches() { return caches; } public void setCaches(Map<K, Node> caches) { this.caches = caches; } /** * 构造方法 * @param size */ public LFU(int size) { this.capacity = size; caches = new LinkedHashMap<K, Node>(size); }}有了类的定义之后，我们接下来需要设计一些方法，包括添加元素，删除元素，获取元素等。
2.3 添加元素添加元素的逻辑主要如下：
先从缓存中根据key获取节点，如果获取不到，说明是新添加的元素，然后和容量比较，大于预定容量的话，需要找出count计数最小(计数相同的情况下，选择时间最久)的节点，然后移除掉那个；如果在预定的大小之内，就新创建节点，注意这里不能使用 System.currentTimeMillis()方法，因为毫秒级别的粒度无法对插入的时间进行区分，在运行比较快的情况下，只有System.nanoTime()才可以将key的插入时间区分，默认设置count计数为1；如果能获取到，表示是旧的元素，那么就用新值覆盖旧值，计数+1，设置key的time为当前纳秒时间；最后还需要进行排序从以上步骤可以看出插入元素的逻辑主要是添加进入缓存，更新元素的时间和计数，重新排序，流程图如下：
每次put或者get元素都需要进行排序，排序的主要意义在于按照key的cout和time进行一个key顺序的重组，这里的逻辑是首先将缓存map创建成一个list，然后按照Node的value进行重组整个map。然后将原来的缓存清空，遍历这个map， 把key和value的值放进去原来的缓存中的顺序就进行了重组。淘汰最小的元素这里调用了Collections.min方法，然后通过比较key的compareTo方法，找到计数最小和时间最长的元素，直接从缓存中移除。有了上面的分析，我们直接写出对应的方法：
获取元素的逻辑主要如下：
首先是从缓存map中获取，如果不存在则返回null，如果存在，在获取到元素之后需要进行节点的更新，计数+1和刷新节点的时间根据LFU的原则，在当前时间获取到这个节点以后，这个节点就暂时变成了热点节点，但是它的count计数也有可能是小于某个节点的count的，所以此时不能将它直接移动到链表顶，还需要进行一次排序，重组它的位置我们依然可以画出对应的流程图：
有了上面的分析，我们直接写出对应的方法：
代码如下：
/** * @author likangmin * @version 1.0 * @create 2021/3/24 14:57 * @desc */public class MyLFUTest { public static void main(String[] args) { LFU<Integer,String> lruCache = new LFU<>(5); lruCache.put(1, "A"); lruCache.put(2, "B"); lruCache.put(3, "C"); lruCache.put(4, "D"); lruCache.put(5, "E"); lruCache.put(6, "F"); lruCache.get(2); lruCache.get(2); lruCache.get(3); lruCache.get(6); //重新put节点3 lruCache.put(3,"C"); final Map<Integer, Node> caches = (Map<Integer, Node>) lruCache.getCaches(); for (Map.Entry<Integer, Node> nodeEntry : caches.entrySet()) { System.out.println(nodeEntry.getValue().value); } }}我们启动程序看一下输出，可以看到正如我们分析的一样。
LRU和LFU侧重点不同，LRU主要体现在对元素的使用时间上，而LFU主要体现在对元素的使用频次上。LFU的缺陷是：在短期的时间内，对某些缓存的访问频次很高，这些缓存会立刻晋升为热点数据，而保证不会淘汰，这样会驻留在系统内存里面。而实际上，这部分数据只是短暂的高频率访问，之后将会长期不访问，瞬时的高频访问将会造成这部分数据的引用频率加快，而一些新加入的缓存很容易被快速删除，因为它们的引用频率很低。
最后，大家可以跟我之前的文章如何设计LRU Cache算法对照着来看，相信看完你会对这两种缓存策略有更深刻的理解，下次不管是跟朋友谈论还是面试，你都可以在他们面前show一波了。