上一次，相信大家已經(jīng)知道關(guān)于 LRU 頁面置換算法的思想和實現(xiàn)了，這里可以一鍵直達(dá)：
Redis 的淘汰策略中，關(guān)于 LFU 頁面置換算法，今天咱們來捋一捋到底思想是啥，可以如何去實現(xiàn)它
[圖片上傳失敗...(image-51c77d-1695644896801)]
這就讓我們進(jìn)入狀態(tài)吧
?LFU 的思想和實現(xiàn)
LFU 全稱為：Least frequently used
含義為：使用頻次最少的，即為 最不經(jīng)常使用的
思想是：如果數(shù)據(jù)在一段時間被訪問的次數(shù)較少，那么在未來的一段時間，這段數(shù)據(jù)被訪問的幾率就會更小
可以看到 LRU 和 LFU 思想上的區(qū)別是非常明顯的
- LRU 強(qiáng)調(diào)最近最少使用，關(guān)注的是最近有沒有使用過
- LFU 強(qiáng)調(diào)的是一段時間的使用次數(shù)，關(guān)注的是頻次
實際上， LRU 和 LFU 在實現(xiàn)上也是挺相似的，都要使用到雙向鏈表和 hashmap，只不過，我們需要思考如何很好的處理好頻次這個數(shù)據(jù)
LRU 查詢數(shù)據(jù)的時候，為了將時間復(fù)雜度從 O(n) 降低到 O(1)，選擇了使用 hashmap 來存放具體的 key 和對應(yīng)的 數(shù)據(jù)節(jié)點
那么 LFU 中，也可以如法炮制，可以使用 hashmap 存放 頻次 和 對應(yīng)的該頻次的節(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 ，因此會默認(rèn)放到頻次為 1 的對應(yīng)的鏈表上
[圖片上傳失敗...(image-439be5-1695644896801)]
插入3，
由于 LFU 容量為 3 ，已經(jīng)滿了，當(dāng)前發(fā)生了缺頁，需要置換數(shù)據(jù)
淘汰 頻次（最低的）為 1 的鏈表的頭結(jié)點，且刪除 hashmap 中的數(shù)據(jù)，同時將 3 這個節(jié)點的數(shù)據(jù)加入到 hashmap 中
[圖片上傳失敗...(image-9e432d-1695644896801)]
插入4，
由于 LFU 容量為 3 ，已經(jīng)滿了，當(dāng)前發(fā)生了缺頁，需要置換數(shù)據(jù)
淘汰 頻次（最低的）為 1 的鏈表的頭結(jié)點，且刪除 hashmap 中的數(shù)據(jù)，同時將 4 這個節(jié)點的數(shù)據(jù)加入到 hashmap 中
[圖片上傳失敗...(image-703517-1695644896801)]
獲取 3，
key 為 3 的節(jié)點在 LFU 中，更新 3 節(jié)點的頻次，從頻次 1 更新到 頻次 2
相當(dāng)于在頻次為 1 對應(yīng)得的鏈表中，刪除 3 這個節(jié)點，讓 2 節(jié)點和 4 節(jié)點進(jìn)行相連，再將 3 這個節(jié)點加入到頻次為 2 的鏈表中，同時更新 hashmap 中 key 為 3 的值
[圖片上傳失敗...(image-5addc-1695644896801)]
插入5，
由于 LFU 容量為 3 ，已經(jīng)滿了，當(dāng)前發(fā)生了缺頁，需要置換數(shù)據(jù)
淘汰 頻次（最低的）當(dāng)前頻次為 1 的鏈表的頭結(jié)點，且刪除 hashmap 中的數(shù)據(jù)，同時將 5 這個節(jié)點的數(shù)據(jù)加入到 hashmap 中
[圖片上傳失敗...(image-ec7e2e-1695644896801)]
從上述演示中，我們可以看到關(guān)于 LRU 的關(guān)鍵邏輯
- 實現(xiàn)基本的鏈表，使用一個 hashmap 來存放 key 和對應(yīng)的節(jié)點，使用另外一個 hashmap 來存放頻次和其對應(yīng)的鏈表
- 插入的數(shù)據(jù)時，如果 LFU 容量已滿，那么找到頻次最低的那條鏈表，刪除鏈表頭，并插入數(shù)據(jù)到鏈表尾部
- 查詢數(shù)據(jù)的時候，若數(shù)據(jù)已經(jīng)存在于鏈表中，則將該節(jié)點的頻次 +1，且放到對應(yīng)頻次的鏈表尾部
那么在實現(xiàn)的時候，只需要實現(xiàn)基本的鏈表以及關(guān)于兩個 hashmap 的聯(lián)動即可實現(xiàn)我們的 LFU
LFU 相對 LRU 的實現(xiàn)來說，會多維護(hù)一個 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
代碼案例結(jié)果
倉庫地址中main.go 代碼實現(xiàn)和 LRU 的一致，只不過，咱們的句柄和具體實現(xiàn)換成了 LFU 的
[圖片上傳失敗...(image-132823-1695644896801)]
代碼運行效果如下：
[圖片上傳失敗...(image-ff143a-1695644896801)]
總結(jié)
至此，咱們將 Redis 淘汰策略中的 LRU 和 LFU 頁面置換算法的思想，演示，以及具體實現(xiàn)都聊了一下，如果有偏差， 還請?zhí)岢?，兄弟們不吝賜教哦
感興趣的，隨時可以下載源碼，在你的機(jī)器上運行哦，倉庫地址如下：
https://github.com/qingconglaixueit/my_lru_lfu
感謝閱讀，歡迎交流，點個贊，關(guān)注一波 再走吧
歡迎點贊，關(guān)注，收藏
朋友們，你的支持和鼓勵，是我堅持分享，提高質(zhì)量的動力
[圖片上傳失敗...(image-bb6db0-1695644896801)]
好了，本次就到這里
技術(shù)是開放的，我們的心態(tài)，更應(yīng)是開放的。擁抱變化，向陽而生，努力向前行。
我是阿兵云原生，歡迎點贊關(guān)注收藏，下次見~
文中提到的技術(shù)點，感興趣的可以查看這些文章：
