一文读懂缓存淘汰算法：LFU 算法
作者：labuladong
上篇文章算法题就像搭乐高：手把手带你拆解 lru 算法写了 lru 缓存淘汰算法的实现方法，本文来写另一个著名的缓存淘汰算法：lfu 算法。
从实现难度上来说，lfu 算法的难度大于 lru 算法，因为 lru 算法相当于把数据按照时间排序，这个需求借助链表很自然就能实现，你一直从链表头部加入元素的话，越靠近头部的元素就是新的数据，越靠近尾部的元素就是旧的数据，我们进行缓存淘汰的时候只要简单地将尾部的元素淘汰掉就行了。
而 lfu 算法相当于是淘汰访问频次最低的数据，如果访问频次最低的数据有多条，需要淘汰最旧的数据。把数据按照访问频次进行排序，而且频次还会不断变化，这可不容易实现。
所以说 lfu 算法要复杂很多，labuladong 进字节跳动的时候就被面试官问到了 lfu 算法。
话说回来，这种著名的算法的套路都是固定的，关键是由于逻辑较复杂，不容易写出漂亮且没有 bug 的代码。
那么本文 labuladong 就带你拆解 lfu 算法，自顶向下，逐步求精。
一、算法描述
要求你写一个类，接受一个capacity参数，实现get和put方法：
classlfucache{ //构造容量为capacity的缓存 publiclfucache(intcapacity){} //在缓存中查询key publicintget(intkey){} //将key和val存入缓存 publicvoidput(intkey,intval){} } get(key)方法会去缓存中查询键key，如果key存在，则返回key对应的val，否则返回 -1。
put(key, value)方法插入或修改缓存。如果key已存在，则将它对应的值改为val；如果key不存在，则插入键值对(key, val)。
当缓存达到容量capacity时，则应该在插入新的键值对之前，删除使用频次（后文用freq表示）最低的键值对。如果freq最低的键值对有多个，则删除其中最旧的那个。
//构造一个容量为2的lfu缓存 lfucachecache=newlfucache(2); //插入两对(key,val)，对应的freq为1 cache.put(1,10); cache.put(2,20); //查询key为1对应的val //返回10，同时键1对应的freq变为2 cache.get(1); //容量已满，淘汰freq最小的键2 //插入键值对(3,30)，对应的freq为1 cache.put(3,30); //键2已经被淘汰删除，返回-1 cache.get(2); 二、思路分析
一定先从最简单的开始，根据 lfu 算法的逻辑，我们先列举出算法执行过程中的几个显而易见的事实：
1、调用get(key)方法时，要返回该key对应的val。
2、只要用get或者put方法访问一次某个key，该key的freq就要加一。
3、如果在容量满了的时候进行插入，则需要将freq最小的key删除，如果最小的freq对应多个key，则删除其中最旧的那一个。
好的，我们希望能够在 o(1) 的时间内解决这些需求，可以使用基本数据结构来逐个击破：
1、使用一个hashmap存储key到val的映射，就可以快速计算get(key)。
hashmapkeytoval; 2、使用一个hashmap存储key到freq的映射，就可以快速操作key对应的freq。
hashmapkeytofreq; 3、这个需求应该是 lfu 算法的核心，所以我们分开说。
3.1、首先，肯定是需要freq到key的映射，用来找到freq最小的key。
3.2、将freq最小的key删除，那你就得快速得到当前所有key最小的freq是多少。想要时间复杂度 o(1) 的话，肯定不能遍历一遍去找，那就用一个变量minfreq来记录当前最小的freq吧。
3.3、可能有多个key拥有相同的freq，所以freq对key是一对多的关系，即一个freq对应一个key的列表。
3.4、希望freq对应的key的列表是存在时序的，便于快速查找并删除最旧的key。
3.5、希望能够快速删除key列表中的任何一个key，因为如果频次为freq的某个key被访问，那么它的频次就会变成freq+1，就应该从freq对应的key列表中删除，加到freq+1对应的key的列表中。
hashmapfreqtokeys; intminfreq=0; 介绍一下这个linkedhashset，它满足我们 3.3，3.4，3.5 这几个要求。你会发现普通的链表linkedlist能够满足 3.3，3.4 这两个要求，但是由于普通链表不能快速访问链表中的某一个节点，所以无法满足 3.5 的要求。
linkedhashset顾名思义，是链表和哈希集合的结合体。链表不能快速访问链表节点，但是插入元素具有时序；哈希集合中的元素无序，但是可以对元素进行快速的访问和删除。
那么，它俩结合起来就兼具了哈希集合和链表的特性，既可以在 o(1) 时间内访问或删除其中的元素，又可以保持插入的时序，高效实现 3.5 这个需求。
综上，我们可以写出 lfu 算法的基本数据结构：
classlfucache{ //key到val的映射，我们后文称为kv表 hashmapkeytoval; //key到freq的映射，我们后文称为kf表 hashmapkeytofreq; //freq到key列表的映射，我们后文称为fk表 hashmapfreqtokeys; //记录最小的频次 intminfreq; //记录lfu缓存的最大容量 intcap; publiclfucache(intcapacity){ keytoval=newhashmap(); keytofreq=newhashmap(); freqtokeys=newhashmap(); this.cap=capacity; this.minfreq=0; } publicintget(intkey){} publicvoidput(intkey,intval){} } 三、代码框架
lfu 的逻辑不难理解，但是写代码实现并不容易，因为你看我们要维护kv表，kf表，fk表三个映射，特别容易出错。对于这种情况，labuladong 教你三个技巧：
1、不要企图上来就实现算法的所有细节，而应该自顶向下，逐步求精，先写清楚主函数的逻辑框架，然后再一步步实现细节。
2、搞清楚映射关系，如果我们更新了某个key对应的freq，那么就要同步修改kf表和fk表，这样才不会出问题。
3、画图，画图，画图，重要的话说三遍，把逻辑比较复杂的部分用流程图画出来，然后根据图来写代码，可以极大减少出错的概率。
下面我们先来实现get(key)方法，逻辑很简单，返回key对应的val，然后增加key对应的freq：
publicintget(intkey){ if(!keytoval.containskey(key)){ return-1; } //增加key对应的freq increasefreq(key); returnkeytoval.get(key); } 增加key对应的freq是 lfu 算法的核心，所以我们干脆直接抽象成一个函数increasefreq，这样get方法看起来就简洁清晰了对吧。
下面来实现put(key, val)方法，逻辑略微复杂，我们直接画个图来看：
这图就是随手画的，不是什么正规的程序流程图，但是算法逻辑一目了然，看图可以直接写出put方法的逻辑：
publicvoidput(intkey,intval){ if(this.cap<=0)return; /*若key已存在，修改对应的val即可*/ if(keytoval.containskey(key)){ keytoval.put(key,val); //key对应的freq加一 increasefreq(key); return; } /*key不存在，需要插入*/ /*容量已满的话需要淘汰一个freq最小的key*/ if(this.cap<=keytoval.size()){ removeminfreqkey(); } /*插入key和val，对应的freq为1*/ //插入kv表 keytoval.put(key,val); //插入kf表 keytofreq.put(key,1); //插入fk表 freqtokeys.putifabsent(1,newlinkedhashset()); freqtokeys.get(1).add(key); //插入新key后最小的freq肯定是1 this.minfreq=1; } increasefreq和removeminfreqkey方法是 lfu 算法的核心，我们下面来看看怎么借助kv表，kf表，fk表这三个映射巧妙完成这两个函数。
四、lfu 核心逻辑
首先来实现removeminfreqkey函数：
privatevoidremoveminfreqkey(){ //freq最小的key列表 linkedhashsetkeylist=freqtokeys.get(this.minfreq); //其中最先被插入的那个key就是该被淘汰的key intdeletedkey=keylist.iterator().next(); /*更新fk表*/ keylist.remove(deletedkey); if(keylist.isempty()){ freqtokeys.remove(this.minfreq); //问：这里需要更新 minfreq 的值吗？ } /*更新kv表*/ keytoval.remove(deletedkey); /*更新kf表*/ keytofreq.remove(deletedkey); } 删除某个键key肯定是要同时修改三个映射表的，借助minfreq参数可以从fk表中找到freq最小的keylist，根据时序，其中第一个元素就是要被淘汰的deletedkey，操作三个映射表删除这个key即可。
但是有个细节问题，如果keylist中只有一个元素，那么删除之后minfreq对应的key列表就为空了，也就是minfreq变量需要被更新。如何计算当前的minfreq是多少呢？
实际上没办法快速计算minfreq，只能线性遍历fk表或者kf表来计算，这样肯定不能保证 o(1) 的时间复杂度。
但是，其实这里没必要更新minfreq变量，因为你想想removeminfreqkey这个函数是在什么时候调用？在put方法中插入新key时可能调用。而你回头看put的代码，插入新key时一定会把minfreq更新成 1，所以说即便这里minfreq变了，我们也不需要管它。
下面来实现increasefreq函数：
privatevoidincreasefreq(intkey){ intfreq=keytofreq.get(key); /*更新kf表*/ keytofreq.put(key,freq+1); /*更新fk表*/ //将key从freq对应的列表中删除 freqtokeys.get(freq).remove(key); //将key加入freq+1对应的列表中 freqtokeys.putifabsent(freq+1,newlinkedhashset()); freqtokeys.get(freq+1).add(key); //如果freq对应的列表空了，移除这个freq if(freqtokeys.get(freq).isempty()){ freqtokeys.remove(freq); //如果这个freq恰好是minfreq，更新minfreq if(freq==this.minfreq){ this.minfreq++; } } } 更新某个key的freq肯定会涉及fk表和kf表，所以我们分别更新这两个表就行了。
和之前类似，当fk表中freq对应的列表被删空后，需要删除fk表中freq这个映射。如果这个freq恰好是minfreq，说明minfreq变量需要更新。
能不能快速找到当前的minfreq呢？这里是可以的，因为我们刚才把key的freq加了 1 嘛，所以minfreq也加 1 就行了。
至此，经过层层拆解，lfu 算法就完成了。
费浦安防二维码识别及产品解决方案
关于单片机C语言编程的常见问题解答
变频器开关电源维修七大步骤
Wind River赋予车载IVI娱乐系统软体Yocto架构优势
数字电视实现银联支付的时代已临近
一文读懂缓存淘汰算法：LFU 算法
温度冲击试验箱试验流程
2020年上百万个5G就业机会来了！vivo助力大学生从象牙塔迈向战场
MEMS开关：四大突破技术实现传统开关的革命
用于边缘计算的机器学习技术介绍
安盟信息法院信息系统勒索病毒防护方案
Tesla 超级充电站将大幅升级，充电时间缩短到5-10分钟
机器视觉的四大应用_机器视觉的基本原理
光伏汇流采集单元应用场景产品介绍
长江存储今年年底量产64层3D NAND,进一步缩短于国外厂商技术差距
ADAMS机械系统动力学自动分析软件
蚂蚁集团A股H股双双暂缓上市 蚂蚁集团重新上市或被推迟半年
如何设计安全的控制系统远程访问
浅谈GTM以及GTM的典型应用
荣耀8评测：华为荣耀8和荣耀8青春版对比评测，前辈与后辈之间的竞争你更青睐谁？
上篇文章算法题就像搭乐高：手把手带你拆解 lru 算法写了 lru 缓存淘汰算法的实现方法，本文来写另一个著名的缓存淘汰算法：lfu 算法。
从实现难度上来说，lfu 算法的难度大于 lru 算法，因为 lru 算法相当于把数据按照时间排序，这个需求借助链表很自然就能实现，你一直从链表头部加入元素的话，越靠近头部的元素就是新的数据，越靠近尾部的元素就是旧的数据，我们进行缓存淘汰的时候只要简单地将尾部的元素淘汰掉就行了。
而 lfu 算法相当于是淘汰访问频次最低的数据，如果访问频次最低的数据有多条，需要淘汰最旧的数据。把数据按照访问频次进行排序，而且频次还会不断变化，这可不容易实现。
所以说 lfu 算法要复杂很多，labuladong 进字节跳动的时候就被面试官问到了 lfu 算法。
话说回来，这种著名的算法的套路都是固定的，关键是由于逻辑较复杂，不容易写出漂亮且没有 bug 的代码。
那么本文 labuladong 就带你拆解 lfu 算法，自顶向下，逐步求精。
一、算法描述
要求你写一个类，接受一个capacity参数，实现get和put方法：
classlfucache{ //构造容量为capacity的缓存 publiclfucache(intcapacity){} //在缓存中查询key publicintget(intkey){} //将key和val存入缓存 publicvoidput(intkey,intval){} } get(key)方法会去缓存中查询键key，如果key存在，则返回key对应的val，否则返回 -1。
put(key, value)方法插入或修改缓存。如果key已存在，则将它对应的值改为val；如果key不存在，则插入键值对(key, val)。
当缓存达到容量capacity时，则应该在插入新的键值对之前，删除使用频次（后文用freq表示）最低的键值对。如果freq最低的键值对有多个，则删除其中最旧的那个。
//构造一个容量为2的lfu缓存 lfucachecache=newlfucache(2); //插入两对(key,val)，对应的freq为1 cache.put(1,10); cache.put(2,20); //查询key为1对应的val //返回10，同时键1对应的freq变为2 cache.get(1); //容量已满，淘汰freq最小的键2 //插入键值对(3,30)，对应的freq为1 cache.put(3,30); //键2已经被淘汰删除，返回-1 cache.get(2); 二、思路分析
一定先从最简单的开始，根据 lfu 算法的逻辑，我们先列举出算法执行过程中的几个显而易见的事实：
1、调用get(key)方法时，要返回该key对应的val。
2、只要用get或者put方法访问一次某个key，该key的freq就要加一。
3、如果在容量满了的时候进行插入，则需要将freq最小的key删除，如果最小的freq对应多个key，则删除其中最旧的那一个。
好的，我们希望能够在 o(1) 的时间内解决这些需求，可以使用基本数据结构来逐个击破：
1、使用一个hashmap存储key到val的映射，就可以快速计算get(key)。
hashmapkeytoval; 2、使用一个hashmap存储key到freq的映射，就可以快速操作key对应的freq。
hashmapkeytofreq; 3、这个需求应该是 lfu 算法的核心，所以我们分开说。
3.1、首先，肯定是需要freq到key的映射，用来找到freq最小的key。
3.2、将freq最小的key删除，那你就得快速得到当前所有key最小的freq是多少。想要时间复杂度 o(1) 的话，肯定不能遍历一遍去找，那就用一个变量minfreq来记录当前最小的freq吧。
3.3、可能有多个key拥有相同的freq，所以freq对key是一对多的关系，即一个freq对应一个key的列表。
3.4、希望freq对应的key的列表是存在时序的，便于快速查找并删除最旧的key。
3.5、希望能够快速删除key列表中的任何一个key，因为如果频次为freq的某个key被访问，那么它的频次就会变成freq+1，就应该从freq对应的key列表中删除，加到freq+1对应的key的列表中。
hashmapfreqtokeys; intminfreq=0; 介绍一下这个linkedhashset，它满足我们 3.3，3.4，3.5 这几个要求。你会发现普通的链表linkedlist能够满足 3.3，3.4 这两个要求，但是由于普通链表不能快速访问链表中的某一个节点，所以无法满足 3.5 的要求。
linkedhashset顾名思义，是链表和哈希集合的结合体。链表不能快速访问链表节点，但是插入元素具有时序；哈希集合中的元素无序，但是可以对元素进行快速的访问和删除。
那么，它俩结合起来就兼具了哈希集合和链表的特性，既可以在 o(1) 时间内访问或删除其中的元素，又可以保持插入的时序，高效实现 3.5 这个需求。
综上，我们可以写出 lfu 算法的基本数据结构：
classlfucache{ //key到val的映射，我们后文称为kv表 hashmapkeytoval; //key到freq的映射，我们后文称为kf表 hashmapkeytofreq; //freq到key列表的映射，我们后文称为fk表 hashmapfreqtokeys; //记录最小的频次 intminfreq; //记录lfu缓存的最大容量 intcap; publiclfucache(intcapacity){ keytoval=newhashmap(); keytofreq=newhashmap(); freqtokeys=newhashmap(); this.cap=capacity; this.minfreq=0; } publicintget(intkey){} publicvoidput(intkey,intval){} } 三、代码框架
lfu 的逻辑不难理解，但是写代码实现并不容易，因为你看我们要维护kv表，kf表，fk表三个映射，特别容易出错。对于这种情况，labuladong 教你三个技巧：
1、不要企图上来就实现算法的所有细节，而应该自顶向下，逐步求精，先写清楚主函数的逻辑框架，然后再一步步实现细节。
2、搞清楚映射关系，如果我们更新了某个key对应的freq，那么就要同步修改kf表和fk表，这样才不会出问题。
3、画图，画图，画图，重要的话说三遍，把逻辑比较复杂的部分用流程图画出来，然后根据图来写代码，可以极大减少出错的概率。
下面我们先来实现get(key)方法，逻辑很简单，返回key对应的val，然后增加key对应的freq：
publicintget(intkey){ if(!keytoval.containskey(key)){ return-1; } //增加key对应的freq increasefreq(key); returnkeytoval.get(key); } 增加key对应的freq是 lfu 算法的核心，所以我们干脆直接抽象成一个函数increasefreq，这样get方法看起来就简洁清晰了对吧。
下面来实现put(key, val)方法，逻辑略微复杂，我们直接画个图来看：
这图就是随手画的，不是什么正规的程序流程图，但是算法逻辑一目了然，看图可以直接写出put方法的逻辑：
publicvoidput(intkey,intval){ if(this.cap<=0)return; /*若key已存在，修改对应的val即可*/ if(keytoval.containskey(key)){ keytoval.put(key,val); //key对应的freq加一 increasefreq(key); return; } /*key不存在，需要插入*/ /*容量已满的话需要淘汰一个freq最小的key*/ if(this.cap<=keytoval.size()){ removeminfreqkey(); } /*插入key和val，对应的freq为1*/ //插入kv表 keytoval.put(key,val); //插入kf表 keytofreq.put(key,1); //插入fk表 freqtokeys.putifabsent(1,newlinkedhashset()); freqtokeys.get(1).add(key); //插入新key后最小的freq肯定是1 this.minfreq=1; } increasefreq和removeminfreqkey方法是 lfu 算法的核心，我们下面来看看怎么借助kv表，kf表，fk表这三个映射巧妙完成这两个函数。
四、lfu 核心逻辑
首先来实现removeminfreqkey函数：
privatevoidremoveminfreqkey(){ //freq最小的key列表 linkedhashsetkeylist=freqtokeys.get(this.minfreq); //其中最先被插入的那个key就是该被淘汰的key intdeletedkey=keylist.iterator().next(); /*更新fk表*/ keylist.remove(deletedkey); if(keylist.isempty()){ freqtokeys.remove(this.minfreq); //问：这里需要更新 minfreq 的值吗？ } /*更新kv表*/ keytoval.remove(deletedkey); /*更新kf表*/ keytofreq.remove(deletedkey); } 删除某个键key肯定是要同时修改三个映射表的，借助minfreq参数可以从fk表中找到freq最小的keylist，根据时序，其中第一个元素就是要被淘汰的deletedkey，操作三个映射表删除这个key即可。
但是有个细节问题，如果keylist中只有一个元素，那么删除之后minfreq对应的key列表就为空了，也就是minfreq变量需要被更新。如何计算当前的minfreq是多少呢？
实际上没办法快速计算minfreq，只能线性遍历fk表或者kf表来计算，这样肯定不能保证 o(1) 的时间复杂度。
但是，其实这里没必要更新minfreq变量，因为你想想removeminfreqkey这个函数是在什么时候调用？在put方法中插入新key时可能调用。而你回头看put的代码，插入新key时一定会把minfreq更新成 1，所以说即便这里minfreq变了，我们也不需要管它。
下面来实现increasefreq函数：
privatevoidincreasefreq(intkey){ intfreq=keytofreq.get(key); /*更新kf表*/ keytofreq.put(key,freq+1); /*更新fk表*/ //将key从freq对应的列表中删除 freqtokeys.get(freq).remove(key); //将key加入freq+1对应的列表中 freqtokeys.putifabsent(freq+1,newlinkedhashset()); freqtokeys.get(freq+1).add(key); //如果freq对应的列表空了，移除这个freq if(freqtokeys.get(freq).isempty()){ freqtokeys.remove(freq); //如果这个freq恰好是minfreq，更新minfreq if(freq==this.minfreq){ this.minfreq++; } } } 更新某个key的freq肯定会涉及fk表和kf表，所以我们分别更新这两个表就行了。
和之前类似，当fk表中freq对应的列表被删空后，需要删除fk表中freq这个映射。如果这个freq恰好是minfreq，说明minfreq变量需要更新。
能不能快速找到当前的minfreq呢？这里是可以的，因为我们刚才把key的freq加了 1 嘛，所以minfreq也加 1 就行了。
至此，经过层层拆解，lfu 算法就完成了。
费浦安防二维码识别及产品解决方案
关于单片机C语言编程的常见问题解答
变频器开关电源维修七大步骤
Wind River赋予车载IVI娱乐系统软体Yocto架构优势
数字电视实现银联支付的时代已临近
一文读懂缓存淘汰算法：LFU 算法
温度冲击试验箱试验流程
2020年上百万个5G就业机会来了！vivo助力大学生从象牙塔迈向战场
MEMS开关：四大突破技术实现传统开关的革命
用于边缘计算的机器学习技术介绍
安盟信息法院信息系统勒索病毒防护方案
Tesla 超级充电站将大幅升级，充电时间缩短到5-10分钟
机器视觉的四大应用_机器视觉的基本原理
光伏汇流采集单元应用场景产品介绍
长江存储今年年底量产64层3D NAND,进一步缩短于国外厂商技术差距
ADAMS机械系统动力学自动分析软件
蚂蚁集团A股H股双双暂缓上市 蚂蚁集团重新上市或被推迟半年
如何设计安全的控制系统远程访问
浅谈GTM以及GTM的典型应用
荣耀8评测：华为荣耀8和荣耀8青春版对比评测，前辈与后辈之间的竞争你更青睐谁？