缓存淘汰算法LRU和LFU( 二 )
文章插图
如上 ， 双哈希表需要维护两个哈希表以及一个最少频次使用的计数minFreq 。
第一个哈希表是 freq_table ， 它的key是访问的频次 ， 它的value是一个双向链表 ， 双向链表的每一个节点包含三个元素：key ， value ， 以及count 。
第二个哈希表是 key_table ， 它的key是双向链表中存储的key ， value是对应节点的指针（这样查找的时间复杂度就是O(1)） 。
【缓存淘汰算法LRU和LFU】类比LRU ， LFU的步骤如下：
- 1.假设LFU缓存容量为3 ， 且一开始初始化插入三个键值对（1 ， 1） ， （2 ， 2） ， （3 ， 3）此时每个键值对的频次都是1 ， 所以它们都在同一个双向链表上 ， 如图四 。
- 2.假设这时候查找key=1 ， 由于key_table存储的是节点的指针 ， 所以可以以O(1)的复杂度得到结果 。
- 2.1 注意此时节点1的频次由1变为2 ， 所以要将节点1移动到频次为2的链表 ， 如图五
- 2.2 另外 ， minFreq也要记得同步更新 ， 不过本次操作不用 。
- 3.假设这时候插入一个新的键值对（4 ， 4） ， 由于它的频次为1 ， 所以对应链表1 ， 它会被插入到链表1的最前面 ， 而由于这种操作 ， 所以同链表的最后一个元素肯定是最晚插入的 。
- 3.1 由于新加的元素导致容量溢出 ， 所以我们要删除频次最少 ， 插入时间最晚的 ， 即图五的（3 ， 3 ， 1）
文章插图推荐阅读
- 向日葵远程控制企业版客户端更新升级，优化远控UI适配SADDC内核算法
- AMD Zen3 APU内核图提前偷跑：三级缓存质变
- 马云又说对了，二维码或将被淘汰，全新支付方式开始兴起
- 马云对未来行业作出预测，4大工作将慢慢淘汰，有你正在做的吗？
- 扫码支付才普及，二维码可能会被淘汰？又一支付方式已兴起
- 锂电池将面临淘汰？超级电池问世，仅需15秒充满电，还不易老化
- 在谷歌算法更新之后2020年盗版网站流量锐减三分之一
- 详解工程师不可不会的LRU缓存淘汰算法
- 今天上海这个比赛上，获奖“程序媛”讲述了自己与算法的爱恨情仇
- Google Chrome开发团队正探索通过扩大浏览器缓存解决性能问题