在探讨缓存置换算法时，我们曾详细解读过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_;
};
