wordpress最簡單的主題濱州seo排名
上一次，相信大家已經(jīng)知道關于 LRU 頁面置換算法的思想和實現(xiàn)了，這里可以一鍵直達：
- 【LRU】一文讓你弄清 Redis LRU 頁面置換算法
Redis 的淘汰策略中，關于 LFU 頁面置換算法，今天咱們來捋一捋到底思想是啥，可以如何去實現(xiàn)它
這就讓我們進入狀態(tài)吧
?LFU 的思想和實現(xiàn)
LFU 全稱為：Least frequently used
含義為：使用頻次最少的，即為 最不經(jīng)常使用的
思想是：如果數(shù)據(jù)在一段時間被訪問的次數(shù)較少，那么在未來的一段時間，這段數(shù)據(jù)被訪問的幾率就會更小
可以看到 LRU 和 LFU 思想上的區(qū)別是非常明顯的
- LRU 強調最近最少使用，關注的是最近有沒有使用過
- LFU 強調的是一段時間的使用次數(shù)，關注的是頻次
實際上， LRU 和 LFU 在實現(xiàn)上也是挺相似的，都要使用到雙向鏈表和 hashmap，只不過，我們需要思考如何很好的處理好頻次這個數(shù)據(jù)
LRU 查詢數(shù)據(jù)的時候，為了將時間復雜度從 O(n) 降低到 O(1)，選擇了使用 hashmap 來存放具體的 key 和對應的 數(shù)據(jù)節(jié)點
那么 LFU 中，也可以如法炮制，可以使用 hashmap 存放 頻次 和 對應的該頻次的節(jié)點組成的鏈表
👀👀簡單來看
- LRU 的實現(xiàn)時用一個雙向鏈表，插入數(shù)據(jù)使用頭插法，從尾部淘汰數(shù)據(jù)
- 那么 LFU 的實現(xiàn)實際上是使用了 2 個 hashmap 和 多個 雙向鏈表，插入數(shù)據(jù)使用尾插法，淘汰數(shù)據(jù)從鏈表頭淘汰
?舉例時刻
還是同樣的方法，咱們舉個例子，就能很好的明白這個思想了
例如，我們還是要插入這些數(shù)據(jù)
set(0,0),set(1,1),set(2,2),set(3,3),set(4,4),get(3) ，set(5,5) ，鏈表的容量為 3
來模擬一下 LFU 的處理過程😁
同理，
先插入前面 3 個節(jié)點數(shù)據(jù)
0, 1, 2，此處 LFU 是使用的尾插法，此處對于首次插入的數(shù)據(jù)，頻次都是 1 ，因此會默認放到頻次為 1 的對應的鏈表上
插入 3，
由于 LFU 容量為 3 ，已經(jīng)滿了，當前發(fā)生了缺頁，需要置換數(shù)據(jù)
淘汰 頻次（最低的）為 1 的鏈表的頭結點，且刪除 hashmap 中的數(shù)據(jù)，同時將 3 這個節(jié)點的數(shù)據(jù)加入到 hashmap 中
插入 4，
由于 LFU 容量為 3 ，已經(jīng)滿了，當前發(fā)生了缺頁，需要置換數(shù)據(jù)
淘汰 頻次（最低的）為 1 的鏈表的頭結點，且刪除 hashmap 中的數(shù)據(jù)，同時將 4 這個節(jié)點的數(shù)據(jù)加入到 hashmap 中
獲取 3，
key 為 3 的節(jié)點在 LFU 中，更新 3 節(jié)點的頻次，從頻次 1 更新到 頻次 2
相當于在頻次為 1 對應得的鏈表中，刪除 3 這個節(jié)點，讓 2 節(jié)點和 4 節(jié)點進行相連，再將 3 這個節(jié)點加入到頻次為 2 的鏈表中，同時更新 hashmap 中 key 為 3 的值
插入 5，
由于 LFU 容量為 3 ，已經(jīng)滿了，當前發(fā)生了缺頁，需要置換數(shù)據(jù)
淘汰 頻次（最低的）當前頻次為 1 的鏈表的頭結點，且刪除 hashmap 中的數(shù)據(jù)，同時將 5 這個節(jié)點的數(shù)據(jù)加入到 hashmap 中
從上述演示中，我們可以看到關于 LRU 的關鍵邏輯
- 實現(xiàn)基本的鏈表，使用一個 hashmap 來存放 key 和對應的節(jié)點，使用另外一個 hashmap 來存放頻次和其對應的鏈表
- 插入的數(shù)據(jù)時，如果 LFU 容量已滿，那么找到頻次最低的那條鏈表，刪除鏈表頭，并插入數(shù)據(jù)到鏈表尾部
- 查詢數(shù)據(jù)的時候，若數(shù)據(jù)已經(jīng)存在于鏈表中，則將該節(jié)點的頻次 +1，且放到對應頻次的鏈表尾部
那么在實現(xiàn)的時候，只需要實現(xiàn)基本的鏈表以及關于兩個 hashmap 的聯(lián)動即可實現(xiàn)我們的 LFU
LFU 相對 LRU 的實現(xiàn)來說，會多維護一個 hashmap ，只不過這個 hashmap 是 key 為 頻次，value 為鏈表 ，即上圖中的 hashmap_freq
知道 LFU 的思想，以及 LFU 中數(shù)據(jù)變動的過程明白了，寫代碼都是很簡單的事情，感興趣的 xdm 可以查看我的 code 地址：https://github.com/qingconglaixueit/my_lru_lfu/blob/main/my_lfu/lfu.go
代碼案例結果
倉庫地址中 main.go 代碼實現(xiàn)和 LRU 的一致，只不過，咱們的句柄和具體實現(xiàn)換成了 LFU 的
代碼運行效果如下：
總結
至此，咱們將 Redis 淘汰策略中的 LRU 和 LFU 頁面置換算法的思想，演示，以及具體實現(xiàn)都聊了一下，如果有偏差， 還請?zhí)岢?#xff0c;兄弟們不吝賜教哦
感興趣的，隨時可以下載源碼，在你的機器上運行哦，倉庫地址如下：
https://github.com/qingconglaixueit/my_lru_lfu
感謝閱讀，歡迎交流，點個贊，關注一波 再走吧
歡迎點贊，關注，收藏
朋友們，你的支持和鼓勵，是我堅持分享，提高質量的動力
好了，本次就到這里
技術是開放的，我們的心態(tài)，更應是開放的。擁抱變化，向陽而生，努力向前行。
我是阿兵云原生，歡迎點贊關注收藏，下次見~
文中提到的技術點，感興趣的可以查看這些文章：
- 【LRU】一文讓你弄清 Redis LRU 頁面置換算法
- 什么是單點登錄？什么又是 OAuth2.0？
- 什么是分布式鎖？他解決了什么樣的問題？
- 【Redis 系列】redis 存儲結構原理 1
- 【Redis 系列】redis 存儲結構原理 2
- 我是如何用 redis 分布式鎖來解決線上歷史業(yè)務問題的
可以進入地址進行體驗和學習：https://xxetb.xet.tech/s/3lucCI