上一次，相信大家已经知道关于 LRU 页面置换算法的思想和实现了，这里可以一键直达：
Redis 的淘汰策略中，关于 LFU 页面置换算法，今天咱们来捋一捋到底思想是啥，可以如何去实现它
[图片上传失败...(image-51c77d-1695644896801)]
这就让我们进入状态吧
✔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 的对应的链表上
[图片上传失败...(image-439be5-1695644896801)]
插入3，
由于 LFU 容量为 3 ，已经满了，当前发生了缺页，需要置换数据
淘汰 频次（最低的）为 1 的链表的头结点，且删除 hashmap 中的数据，同时将 3 这个节点的数据加入到 hashmap 中
[图片上传失败...(image-9e432d-1695644896801)]
插入4，
由于 LFU 容量为 3 ，已经满了，当前发生了缺页，需要置换数据
淘汰 频次（最低的）为 1 的链表的头结点，且删除 hashmap 中的数据，同时将 4 这个节点的数据加入到 hashmap 中
[图片上传失败...(image-703517-1695644896801)]
获取 3，
key 为 3 的节点在 LFU 中，更新 3 节点的频次，从频次 1 更新到 频次 2
相当于在频次为 1 对应得的链表中，删除 3 这个节点，让 2 节点和 4 节点进行相连，再将 3 这个节点加入到频次为 2 的链表中，同时更新 hashmap 中 key 为 3 的值
[图片上传失败...(image-5addc-1695644896801)]
插入5，
由于 LFU 容量为 3 ，已经满了，当前发生了缺页，需要置换数据
淘汰 频次（最低的）当前频次为 1 的链表的头结点，且删除 hashmap 中的数据，同时将 5 这个节点的数据加入到 hashmap 中
[图片上传失败...(image-ec7e2e-1695644896801)]
从上述演示中，我们可以看到关于 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 的
[图片上传失败...(image-132823-1695644896801)]
代码运行效果如下：
[图片上传失败...(image-ff143a-1695644896801)]
总结
至此，咱们将 Redis 淘汰策略中的 LRU 和 LFU 页面置换算法的思想，演示，以及具体实现都聊了一下，如果有偏差， 还请提出，兄弟们不吝赐教哦
感兴趣的，随时可以下载源码，在你的机器上运行哦，仓库地址如下：
https://github.com/qingconglaixueit/my_lru_lfu
感谢阅读，欢迎交流，点个赞，关注一波 再走吧
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
[图片上传失败...(image-bb6db0-1695644896801)]
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
文中提到的技术点，感兴趣的可以查看这些文章：
网友评论