共计 2101 个字符，预计需要花费 6 分钟才能阅读完成。
上一次，置信大家曾经晓得对于 LRU 页面置换算法的思维和实现了，这里能够一键中转：
- 【LRU】一文让你弄清 Redis LRU 页面置换算法
Redis 的淘汰策略中，对于 LFU 页面置换算法 ，明天咱们来捋一捋到底 思维是啥，能够如何去实现它
这就让咱们进入状态吧
✔LFU 的思维和实现
LFU 全称为：Least frequently used
含意为：应用频次起码的，即为 最不常常应用的
思维是：如果 数据在一段时间被拜访的次数较少，那么在将来的一段时间，这段数据被拜访的几率就会更小
能够看到 LRU 和 LFU 思维上的区别是非常明显的
- LRU 强调最近起码应用，关注的是最近有没有应用过
<!—->
- LFU 强调的是一段时间的应用次数，关注的是频次
实际上，LRU 和 LFU 在实现上也是挺类似的，都要应用到双向链表和 hashmap，只不过，咱们须要思考如何很好的解决好频次这个数据
LRU 查问数据的时候，为了将工夫复杂度从 O(n) 升高到 O(1)，抉择了应用 hashmap 来寄存具体的 key 和对应的 数据节点
那么 LFU 中，也能够如法炮制，能够应用 hashmap 寄存 频次 和 对应的该频次的节点组成的链表
👀👀简略来看
- LRU 的实现时用一个双向链表，插入数据应用头插法，从尾部淘汰数据
<!—->
- 那么 LFU 的实现实际上是 应用了 2 个 hashmap 和 多个 双向链表，插入数据应用尾插法，淘汰数据从链表头淘汰
✔举例时刻
还是同样的办法，咱们举个例子，就能很好的明确这个思维了
例如，咱们还是要插入这些数据
set(0,0),set(1,1),set(2,2),set(3,3),set(4,4),get(3) ，set(5,5)，链表的 容量为 3
来模仿一下 LFU 的处理过程😁
同理，
先插入后面 3 个节点 数据
0, 1, 2，此处 LFU 是应用的 尾插法，此处对于首次插入的数据，频次都是 1，因而会默认放到频次为 1 的对应的链表上
插入 3，
因为 LFU 容量为 3，曾经满了，以后产生了缺页，须要置换数据
淘汰 频次（最低的）为 1 的链表的头结点，且删除 hashmap 中的数据，同时将 3 这个节点的数据退出到 hashmap 中
插入 4，
因为 LFU 容量为 3，曾经满了，以后产生了缺页，须要置换数据
淘汰 频次（最低的）为 1 的链表的头结点，且删除 hashmap 中的数据，同时将 4 这个节点的数据退出到 hashmap 中
获取 3，
key 为 3 的节点在 LFU 中，更新 3 节点的频次，从频次 1 更新到 频次 2
相当于在频次为 1 对应得的链表中，删除 3 这个节点，让 2 节点和 4 节点进行相连，再将 3 这个节点退出到频次为 2 的链表中，同时更新 hashmap 中 key 为 3 的值
插入 5，
因为 LFU 容量为 3，曾经满了，以后产生了缺页，须要置换数据
淘汰 频次（最低的）以后频次为 1 的链表的头结点，且删除 hashmap 中的数据，同时将 5 这个节点的数据退出到 hashmap 中
从上述演示中，咱们能够看到 对于 LRU 的要害逻辑
- 实现根本的链表，应用一个 hashmap 来寄存 key 和对应的节点 ， 应用另外一个 hashmap 来寄存频次和其对应的链表
<!—->
- 插入的数据时，如果 LFU 容量已满，那么找到频次最低的那条链表，删除链表头，并插入数据到链表尾部
<!—->
- 查问数据的时候，若数据曾经存在于链表中，则将该节点的频次 +1，且放到对应频次的链表尾部
那么在实现的时候，只须要实现根本的链表以及对于两个 hashmap 的联动即可实现咱们的 LFU
LFU 绝对 LRU 的实现来说，会多保护一个 hashmap，只不过这个 hashmap 是 key 为 频次，value 为链表，即上图中的 hashmap_freq
晓得 LFU 的思维，以及 LFU 中数据变动的过程明确了，写代码都是很简略的事件，感兴趣的 xdm 能够查看我的 code 地址：https://github.com/qingconglaixueit/my_lru_lfu/blob/main/my_lfu/lfu.go
代码案例后果
仓库地址中 main.go 代码实现和 LRU 的统一，只不过， 咱们的句柄和具体实现换成了 LFU 的
代码运行成果如下：
总结
至此，咱们将 Redis 淘汰策略中的 LRU 和 LFU 页面置换算法的思维，演示，以及具体实现都聊了一下，如果有偏差，还请提出，兄弟们不吝赐教哦
感兴趣的，随时能够下载源码，在你的机器上运行哦，仓库地址如下：
https://github.com/qingconglaixueit/my_lru_lfu
感激浏览，欢送交换，点个赞，关注一波 再走吧
欢送点赞，关注，珍藏
敌人们，你的反对和激励，是我保持分享，提高质量的能源
好了，本次就到这里
技术是凋谢的，咱们的心态，更应是凋谢的。拥抱变动，背阴而生，致力向前行。
我是 阿兵云原生，欢送点赞关注珍藏，下次见~
文中提到的技术点，感兴趣的能够查看这些文章：
- 【LRU】一文让你弄清 Redis LRU 页面置换算法
<!—->
- 什么是单点登录？什么又是 OAuth2.0？
<!—->
- 什么是分布式锁？他解决了什么样的问题？
<!—->
- 【Redis 系列】redis 存储构造原理 1
<!—->
- 【Redis 系列】redis 存储构造原理 2
<!—->
- 我是如何用 redis 分布式锁来解决线上历史业务问题的
