在探討緩存置換算法時，我們曾詳細解讀過LRU（Least Recently Used）算法，它憑借 “最近最少使用” 的策略在緩存管理領域大放異彩。今天，讓我們將目光聚焦于另一種重要的緩存置換算法 ——LFU（Least Frequently Used 最不經常使用），深入探究它的原理、實現方式、應用場景以及與 LRU 的差異。
一、LFU 算法核心原理
LFU 算法的核心思想是根據數據的訪問頻率來決定淘汰對象。與 LRU 依據數據最近的訪問時間不同，LFU 更關注數據被訪問的頻繁程度。它認為，在過去一段時間內訪問次數最少的數據，在未來被訪問的可能性也相對較低，因此當緩存空間不足時，優先淘汰這類數據。
想象一下圖書館的藏書管理，有些書籍經常被借閱，而有些則鮮有人問津。LFU 算法就如同圖書館管理員，會定期清理那些借閱次數最少的書籍，為新購入的書籍騰出空間。這樣，圖書館的書架上始終保留著最受歡迎、被借閱可能性最高的書籍，提高了讀者找到所需書籍的效率。在緩存管理中，LFU 算法通過記錄每個數據的訪問次數，在緩存滿時淘汰訪問次數最少的數據，以此來維持緩存的高效運行。
二、LFU 算法的數據結構實現
實現 LFU 算法需要借助合適的數據結構，我們的代碼實現使用的是哈希表和多個雙向鏈表的組合。
-
哈希表：哈希表則用于快速定位數據。它以數據的鍵作為索引，存儲對應數據在雙向鏈表中的節點指針。這樣，在查找數據時，通過哈希表可以在?O(1)?的時間復雜度內找到對應的數據節點，然后根據節點指針在雙向鏈表中進行操作。例如，在一個基于鍵值對存儲的內存緩存中，通過哈希表可以快速找到特定鍵對應的數據，提高緩存的查詢效率。
不清楚哈希表的可以看我以前的文章c++ 手寫STL篇（三）實現hashtable
-
雙向鏈表：在緩存管理中，雙向鏈表常被用于維護數據的訪問順序，鏈表里的每個節點都代表著一個緩存數據。LRU 和 LFU 算法都用到了雙向鏈表，但使用方式有所不同。
在 LRU 算法里，只有一個雙向鏈表。這個鏈表有個很清晰的規則：頭部的節點代表著最近使用的數據，就好像是你剛剛才翻閱過的資料，被放在了最顯眼的位置；而尾部的節點則代表最近最少使用的數據，類似于你很久都沒碰過的舊文件，被放在了最角落。
LFU 算法就不太一樣了。在 LFU 中存在多個雙向鏈表，那些訪問頻次相同的數據節點會被串聯在同一個雙向鏈表中。比如說，有一些數據都只被訪問過 1 次，它們就會被放在一個雙向鏈表；另外一些都被訪問過 3 次的數據，則會在另一個雙向鏈表。為了能快速找到不同訪問頻次對應的雙向鏈表，LFU 通過哈希表將訪問頻次和對應的雙向鏈表建立映射關系，這樣就能很方便地管理和查找數據了。雙向鏈表的優勢在于，插入和刪除操作的時間復雜度都是?O(1)?，這對于頻繁的緩存操作來說非常高效。例如，在一個頻繁讀寫的數據庫緩存中，數據的插入和刪除操作會經常發生，雙向鏈表的這種特性可以保證緩存操作的快速執行。
不清楚雙向鏈表的可以看這篇文章?c++ 手寫STL篇（二） 用雙向鏈表實現list核心功能_c++ 二維鏈表手寫-CSDN博客
通過哈希表和雙向鏈表的協同工作，LFU 算法能夠高效地管理數據的訪問次數，并快速找到訪問次數最少的數據進行淘汰。
三、LFU 算法的操作流程
-
查詢操作：當進行查詢操作時，首先在哈希表中查找數據的鍵。如果找到，說明數據在緩存中，將對應數據的訪問次數加 1，并調整雙向鏈表以保持堆的有序性（因為訪問次數發生了變化）。如果未找到，則說明數據不在緩存中，需要從其他數據源獲取數據（如磁盤），然后將數據插入到緩存中。
-
插入操作：插入操作分為兩種情況。若緩存未滿，直接將數據插入到哈希表和雙向鏈表中，并將其訪問次數初始化為 1。若緩存已滿，則先從訪問頻次最小的雙向鏈表中取出元素，將其從哈希表和雙向鏈表中刪除，然后再將新數據插入到哈希表和雙向鏈表中，并將其訪問次數設置為 1。
-
刪除操作：刪除操作相對簡單，在哈希表中查找要刪除數據的鍵，找到后從哈希表和雙向鏈表中刪除對應的元素即可。
四、LFU 算法的應用場景
-
CDN 緩存優化：內容分發網絡（CDN）的主要任務是將內容緩存到離用戶更近的節點，以加快用戶的訪問速度。在 CDN 中，LFU 算法可用于管理緩存內容。例如，在視頻網站的 CDN 系統中，視頻片段會被緩存到各個節點。隨著用戶觀看不同的視頻，CDN 節點的緩存空間會逐漸被占滿。LFU 算法會根據視頻片段的訪問次數，淘汰那些訪問次數最少的片段，為新的熱門視頻片段騰出空間。這樣，用戶在訪問視頻時，CDN 節點能夠更快地提供熱門視頻內容，提升用戶體驗。（在流媒體中cdn是成本最高環節，因此如何節省資源很重要）
-
搜索引擎緩存管理：搜索引擎在處理大量的搜索請求時，會將經常查詢的關鍵詞及其搜索結果緩存起來。LFU 算法可以幫助搜索引擎決定淘汰哪些緩存內容。當緩存空間不足時，優先淘汰那些搜索次數最少的關鍵詞及其結果。比如，在某一時間段內，一些熱門話題的搜索頻率很高，而一些生僻關鍵詞的搜索次數較少。LFU 算法會將這些生僻關鍵詞的緩存結果淘汰，保證緩存中保留的是更有可能被再次搜索的熱門關鍵詞及其結果，提高搜索引擎的響應速度。
-
游戲資源緩存策略：在游戲運行過程中，會加載大量的資源，如紋理、模型等。為了提高游戲的加載速度和運行效率，游戲會將這些資源緩存到內存中。LFU 算法可以根據資源的使用頻率，淘汰那些使用次數最少的資源。例如，在一款開放世界游戲中，玩家在某個區域頻繁活動，該區域的游戲資源訪問頻率較高，而一些偏遠區域的資源訪問次數較少。LFU 算法會優先淘汰這些偏遠區域的資源，為當前區域更需要的資源騰出空間，確保游戲能夠流暢運行。
五、LFU 與 LRU 的對比分析
-
原理差異：LRU 基于數據的訪問時間，優先淘汰最近最少使用的數據；而 LFU 基于數據的訪問頻率，優先淘汰訪問次數最少的數據。這意味著 LRU 更注重數據的時效性，而 LFU 更關注數據的使用頻繁程度。
-
適用場景差異：LRU 適用于數據訪問具有時間局部性的場景，即近期訪問過的數據在未來一段時間內再次被訪問的概率較高。例如，在瀏覽器緩存中，用戶通常會在短時間內回訪之前瀏覽過的網頁，LRU 算法能夠很好地適應這種場景。而 LFU 適用于數據訪問頻率相對穩定的場景，對于那些訪問頻率變化較大的數據，LFU 可能無法及時適應。比如在電商平臺中，商品的熱門程度可能會隨著時間和促銷活動發生較大變化，此時 LFU 算法可能不太適用。
-
實現復雜度差異：LFU 算法由于需要記錄數據的訪問次數并維護一個有序的數據結構，其實現復雜度相對較高。而 LRU 算法通常借助雙向鏈表和哈希表即可實現，相對來說實現較為簡單。
六、LFU 算法的優缺點
-
優點：能更準確地反映數據的使用頻繁程度，在數據訪問頻率穩定的場景下，能夠有效提高緩存命中率，減少數據的重復讀取。例如在一些數據訪問模式較為固定的企業級應用中，LFU 算法可以充分發揮其優勢，提升系統性能。
-
缺點：需要額外的空間來記錄數據的訪問次數，并且維護有序數據結構的操作也會增加時間復雜度；對于過時的熱點數據，因為其訪問頻次高，難以被淘汰；在高并發環境下，頻繁更新訪問次數和調整有序數據結構可能會帶來性能瓶頸；對于剛加入緩存的數據可能應為頻次很低而被快速淘汰，即便這項是近期熱點數據（短期熱點數據無法及時緩存）。
七、用c++實現LFU算法
LFU 緩存置換算法是一種經典且實用的算法，在眾多領域都有廣泛的應用。通過深入理解其原理、數據結構選擇、操作流程以及應用場景，我們可以更好地將其應用到實際項目中，提升系統的性能。接下來，我們將通過手撕代碼的方式，詳細展示如何實現一個 LFU 緩存。
代碼參考自：https://github.com/youngyangyang04/KamaCache
接口類，對緩存置換算法設計統一接口實現隔離?：
#ifndef CACHEPOLICY_H
#define CACHEPOLICY_Htemplate<typename Key, typename Value>
class CachePolicy
{
public:virtual ~CachePolicy() {};virtual void put(Key key, Value value) = 0;virtual bool get(Key key,Value& value) = 0;virtual Value get(Key key) = 0;
};#endif
雙向鏈表實現，包含節點結構體實現，用于存儲鍵值對和前向后向節點指針，并且實現了雙向鏈表基本功能，例如判斷是否為空，增加、刪除節點、獲取鏈表頭節點等方法
template<typename Key, typename Value> class LfuCache;template<typename Key, typename Value>
class FreqList
{
public: struct Node//節點結構體，存儲鍵值對和前向后向節點指針{int freq;Key key;Value value;std::shared_ptr<Node> pre;std::shared_ptr<Node> next;Node() :freq(1), pre(nullptr), next(nullptr) {}Node(Key key, Value value) :key(key), value(value), freq(1), pre(nullptr), next(nullptr) {}};using NodePtr = std::shared_ptr<Node>;int freq_;NodePtr head_;NodePtr tail_;public: explicit FreqList(int n)://expicit禁止隱式構造freq_(n)//構建虛擬頭節點和虛擬尾節點，然后頭尾相連完成初始化{head_ = std::make_shared<Node>();tail_ = std::make_shared<Node>();head_->next = tail_;tail_->pre = head_;}//判空bool isEmpty() const{return head_->next == tail_;}//增加節點void addNode(NodePtr node){if(!node || !head_ || !tail_) return;node->pre = tail_->pre;node->next = tail_;tail_->pre->next = node;tail_->pre = node;}//刪除節點void removeNode(NodePtr node){if(!node || !head_ || !tail_) return;if(!node->pre || !node->next) return;node->pre->next = node->next;node->next->pre = node->pre;node->pre = nullptr;node->next = nullptr;}//獲取頭節點NodePtr getFirstNode() const {return head_->next;}//類作為友元，方便LfuCache類直接訪問FreqList類的私有成員friend class LfuCache<Key,Value>;
};在 LFU 類中，實現了數據的增刪改查功能。這里要著重講一下計數操作，它是 LFU 算法的關鍵環節。想象一下，緩存就像是一個熱鬧的集市，里面的每個攤位（數據節點）都有自己的客流量（訪問頻次）。如果不對每個攤位的客流量計數加以限制，那些長期火爆的攤位（熱數據），客流量計數就會像火箭一樣不斷飆升。這不僅會占用大量的 “記錄空間”，就好比攤位的賬本越寫越厚，最后可能連存放賬本的地方都沒有了（占用空間甚至計數溢出）。而且，一些曾經很火但現在已經過時的攤位（過期的熱點數據），因為之前積累的客流量太大，很難被擠出這個集市（難以被清除出緩存）。
為了解決這些問題，采用了一種巧妙的辦法 —— 設置最大平均訪問次數限制。它就像是給集市的熱鬧程度設定了一個上限。通過curTotalNum_這個 “總客流量計數器”，把集市里所有攤位的客流量都加起來，再除以攤位總數，就能得到平均每個攤位的客流量（平均訪問次數curAverageNum_）。當這個平均客流量超過了設定的最大平均客流量maxAverageNum_后，就會啟動handleOverMaxAverageNum這個 “攤位熱度調整員”。它會把每個攤位的客流量都減去最大平均客流量的一半，這樣一來，每個攤位的客流量上限就被控制住了，那些長期賴在集市里的過期熱門攤位也終于有機會被清理出去了，集市（緩存）也就能夠保持高效的運營狀態啦。
template<typename Key, typename Value>
class LfuCache : public CachePolicy<Key,Value>
{
public:using Node = typename FreqList<Key,Value>::Node;using NodePtr = std::shared_ptr<Node>;using NodeMap = std::unordered_map<Key,NodePtr>;LfuCache(int capacity, int maxAverageNum = 10):capacity_(capacity),minFreq_(INT8_MAX),maxAverageNum_(maxAverageNum),curAverageNum_(0),curTotalNum_(0) {}~LfuCache() override = default;//存入緩存void put(Key key, Value value) override{if(capacity_ <= 0) return;std::lock_guard<std::mutex> lock(mutex_);auto it = nodeMap_.find(key);if(it != nodeMap_.end()){it->second->value = value;getInternal(it->second,value);return;}putInternal(key,value);}//讀取緩存bool get(Key key, Value& value) override{std::lock_guard<std::mutex> lock(mutex_);auto it = nodeMap_.find(key);if(it != nodeMap_.end()){getInternal(it->second,value);return true;}return false;}//get重載Value get(Key key) override{Value value{};get(key,value);return value;}//清除所有緩存void purge(){nodeMap_.clear();freqToFreqList_.clear();}private:void putInternal(Key key, Value value);void getInternal(NodePtr key,Value& value);void kickOut();//根據最小訪問計數minFreq_清除最不經常使用節點void removeFromFreqList(NodePtr node);//從雙向鏈表中移除節點void addToFreqList(NodePtr node);//向雙向鏈表加入節點void addFreqNum();//訪問頻次總數加1并計算當前平均訪問次數，如果大于最大值調用節點處理函數void decreaseFreqNum(int num);//訪問頻次總數見num并計算當前平均訪問次數void handleOverMaxAverageNum();//節點處理函數，對每個節點訪問計數減去最大平均訪問計數的一半，并調整freqToFreqList_這個哈希表void updateMinFreq();//遍歷所有節點，找出最小訪問計數private:int capacity_;//容量int minFreq_;//所有節點中訪問計數的最小值int maxAverageNum_;//最大平均訪問次數int curAverageNum_;//當前緩存的平均訪問計數int curTotalNum_;//當前緩存中所有節點的訪問計數總和std::mutex mutex_;NodeMap nodeMap_;//節點key與節點指針映射的哈希表std::unordered_map<int,FreqList<Key,Value>*> freqToFreqList_;//訪問計數與雙向鏈表映射的哈希表
};下面是私有成員方法的實現
template<typename Key, typename Value>
void LfuCache<Key,Value>::getInternal(NodePtr node, Value& value)
{value = node->value;removeFromFreqList(node);node->freq++;addToFreqList(node);
//判斷并調整最小訪問計數值if(node->freq - 1 == minFreq_ && freqToFreqList_[node->freq - 1]->isEmpty()){minFreq_++;}addFreqNum();
}template<typename Key, typename Value>
void LfuCache<Key,Value>::putInternal(Key key, Value value)
{
//如果緩存已滿，清除最不經常使用節點if(nodeMap_.size() >= capacity_){kickOut();}NodePtr node = std::make_shared<Node>(key,value);nodeMap_[key] = node;addToFreqList(node);addFreqNum();minFreq_ = std::min(minFreq_,1);
}template<typename Key, typename Value>
void LfuCache<Key,Value>::kickOut()
{NodePtr node = freqToFreqList_[minFreq_]->getFirstNode();removeFromFreqList(node);nodeMap_.erase(node->key);decreaseFreqNum(node->freq);
}template<typename Key, typename Value>
void LfuCache<Key,Value>::addFreqNum()
{curTotalNum_++;if(nodeMap_.empty()){curAverageNum_ = 0;}else{curAverageNum_ = curTotalNum_ / nodeMap_.size();}if(curAverageNum_ > maxAverageNum_){handleOverMaxAverageNum();}
}template<typename Key, typename Value>
void LfuCache<Key,Value>::decreaseFreqNum(int num)
{curTotalNum_ -= num;if(nodeMap_.empty()){curAverageNum_ = 0;}else{curAverageNum_ = curTotalNum_ / nodeMap_.size();}
}template<typename Key, typename Value>
void LfuCache<Key,Value>::removeFromFreqList(NodePtr node)
{if(!node) return;auto freq = node->freq;freqToFreqList_[freq]->removeNode(node);
}template<typename Key, typename Value>
void LfuCache<Key,Value>::addToFreqList(NodePtr node)
{if(!node) return;auto freq = node->freq;if(freqToFreqList_.find(freq) == freqToFreqList_.end()){freqToFreqList_[freq] = new FreqList<Key,Value>(node->freq);}freqToFreqList_[freq]->addNode(node);
}
//這個操作邏輯有點像hashtable的重哈希擴容
template<typename Key, typename Value>
void LfuCache<Key,Value>::handleOverMaxAverageNum()
{if(nodeMap_.empty()) return;for(auto it = nodeMap_.begin(); it != nodeMap_.end(); it++){if(!it->second) continue;NodePtr node = it->second;//因為會改變訪問計數值，其在freqList中的映射位置也會改變，所以先從雙向鏈表內取出removeFromFreqList(node);//遍歷所有節點，對節點訪問計數減去最大平均計數值的一半，如果減后值小于0，則置為1node->freq -= maxAverageNum_ / 2;if(node->freq < 1) node->freq = 1;//插入雙向鏈表addToFreqList(node);}updateMinFreq();
}template<typename Key, typename Value>
void LfuCache<Key,Value>::updateMinFreq()
{minFreq_ = INT8_MAX;for(const auto& pair : freqToFreqList_){if(pair.second && !pair.second->isEmpty()){minFreq_ = std::min(minFreq_,pair.first);}}if(minFreq_ == INT8_MAX)minFreq_ = 1;
}通過以上代碼也可以看出它和LRU有相同的鎖粒度大問題，這樣的話高并發下會消耗大量資源用于線程同步等待，這個問題怎么解決呢？其實可以把一個大的緩存池分成幾個小的緩存池，就好比多個人都要從一個倉庫取貨，但倉庫每次只能進一個人，如果多個人要取貨那就必須得排隊等待，哪怕每個人要取的貨物不同，既然這樣那不如把一個大倉庫分成若干個小倉庫，每個人取得貨物可能分布在不同倉庫內，哪怕仍然有好幾個人要的貨物碰巧在同一個倉庫，那隊伍也不會排的像原先那么長。這樣就實現了分流。
template<typename Key, typename Value>
class HashLfuCache
{
public:HashLfuCache(size_t capacity, int sliceNum, int maxAverageNum = 10): sliceNum_(sliceNum > 0 ? sliceNum : std::thread::hardware_concurrency()),capacity_(capacity){size_t sliceSize = std::ceil(capacity_ / static_cast<double>(sliceNum_));for(size_t i = 0; i < sliceNum_; i++){lfuSliceCaches_.emplace_back(new LfuCache<Key,Value>(sliceSize,maxAverageNum));}}void put(Key key, Value value){size_t sliceIndex = Hash(key) % sliceNum_;return lfuSliceCaches_[sliceIndex]->put(key,value);}bool get(Key key, Value& value){size_t sliceIndex = Hash(key) % sliceNum_;return lfuSliceCaches_[sliceIndex]->get(key,value);}Value get(Key key){Value value{};get(key,value);return value;}void purge(){for(auto& lfuSliceCache : lfuSliceCaches_){lfuSliceCache.purge();}}private:size_t Hash(Key key){std::hash<Key> hashFunc;return hashFunc(key);}private:size_t capacity_;int sliceNum_;std::vector<std::unique_ptr<LfuCache<Key, Value>>> lfuSliceCaches_;
};
![每日一題洛谷P1025 [NOIP 2001 提高組] 數的劃分c++](http://pic.xiahunao.cn/每日一題洛谷P1025 [NOIP 2001 提高組] 數的劃分c++)
