文章目录

在之前我写过一篇LRU的博客，如果不了解的建议先看看这篇

高级数据结构与算法 | LRU缓存机制（Least Recently Used）

LFUCache

LFU（Least Frequently Used），即最不经常使用页置换算法。

如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰，这就是LFU的核心思想。

如果我们想要设计一个LFU缓存算法，就需要满足以下功能

初始化时设置缓存大小，当缓存已满后插入元素时需要淘汰现有元素来置换新元素get(key)：如果缓存中存在key，则获取value，并更新其使用次数put(key, value) ：如果key已经存在，则更新key所对应的value。如果不存在则插入键值对，但是插入时如果缓存已满，则需要将最不常用的键值对淘汰，置换新数据。如果存在多个使用频率相同的键值对，应当选取最久没有使用的。保证get和put的操作时间复杂度都为O(1)

class LFUCache {public:LFUCache(int capacity) {}int get(int key) {}void put(int key, int value) {}};

根据以上条件，我们在上面给出了一个算法的大致框架，下面就结合框架以及条件，来设计我们具体的一个结构

结构设计

由于LFU需要根据使用次数来进行缓存淘汰的判断，因此我们每一项中不仅需要存储key，value，还需要存储使用次数freq

每一项的节点设计如下

class LFUNode{public:LFUNode(int key, int value, int freq): _key(key), _value(value), _freq(freq){}int _key; int _value;int _freq; //访问次数};

在上面列的几个条件中，其中最难处理的地方其实就是O(1)的get和put，因为没有任何一个独立的数据结构能够满足这个条件，因此我们需要组合使用多个结构。

如果要保证put中的插入和删除操作达到O(1)，那么我们只能选择使用链表来记录我们的缓存信息，但是这次与之前的LRU并不相同，我们在保证使用次数最少的同时，还需要保证淘汰的时同次数中最久没有使用的，这就意味这我们需要根据不同的使用次数，来维护多个链表，并且每个链表中按照使用时间进行排序。

上面的设计依旧存在着一些问题，因为我们在对一个元素进行操作后，它的使用次数就会发生变化，那么我们就需要将其从原先的链表中移动到下一个链表，那么我们如何能够保证O(1)的查找到它，并对他进行操作呢？同时，我们如何能够快速的在多个链表中，查找到它所在的那个链表，以及它即将要去的链表呢？因此，我们还需要结合其他的数据结构来完成这个问题

要保证O(1)的查找链表，这时候就需要用到哈希结构了，我们可以将使用次数freq与每个保存该freq节点的链表建立起映射，保证O(1)的获取链表。

如果要保证O(1)的从指定链表中找到元素，并对其进行操作，我们可以将key与链表中对应元素的迭代器建立起映射，当我们通过key找到迭代器的时候，就可以利用迭代器对链表进行操作。

因此，最终LFUCache的结构设计如下

class LFUCache {public:LFUCache(int capacity) : _capacity(capacity), _minFreq(0){}int get(int key) {}void put(int key, int value) {}private:unordered_map<int, list<LFUNode>::iterator> _keyTable; //建立key与节点迭代器的映射unordered_map<int, list<LFUNode>> _freqTable; //建立freq与该值链表的映射int _minFreq; //保存当前最小的freq，便于淘汰操作int _capacity; //缓存最大容量};

LFUCache的实现

接下来就该实现get和put功能了，我先列出这两个功能实现的核心思路

get

根据keyTable查找到节点的迭代器，不存在则直接返回更新使用次数，通过迭代器将节点从原链表中删除，并通过freqTable获取下一个链表，将其头插进链表中，保证最后使用的在最前面，使得链表按照使用时间倒序排序将新链表中该节点的迭代器更新到keyTable中

put

根据keyTable查找到节点的迭代器，存在则说明是更新，不存在则说明是淘汰如果是更新，那么操作的内容和上面的get大体相同如果是插入，需要判断当前缓存是否已满，是否需要淘汰，如果未满则直接插入freq=1的链表中，并将迭代器插入至keyTable中如果缓存已满，则需要根据minFreq在freqTable中找到对应的最小freq链表，并删除队尾，即最久没有使用的元素，同时在keyTable中淘汰该元素

这里我就将每一步的思路写在下面代码的注释中

完整的实现代码如下

class LFUNode{public:LFUNode(int key, int value, int freq): _key(key), _value(value), _freq(freq){}int _key; int _value;int _freq; //访问次数};class LFUCache {public:LFUCache(int capacity) : _capacity(capacity), _minFreq(0){}int get(int key) {if(_capacity == 0){return -1;}auto it = _keyTable.find(key); //查找到对应的节点if(it != _keyTable.end()){list<LFUNode>::iterator node = it->second; //记录节点的value以及freqint value = node->_value, freq = node->_freq;_freqTable[freq].erase(node); //从freq表中的对应链表删除当前节点if(_freqTable[freq].empty() && _minFreq == freq) //如果删除后链表为空，则判断是否需要更新最小freq{_minFreq++;}_freqTable[freq + 1].push_front(LFUNode(key, value, freq + 1)); //将更新后的节点头插入下一个freq的链表中，保证按照插入时间排序it->second = _freqTable[freq + 1].begin(); //更新迭代器return value;}//查找不到直接返回-1else{return -1;}}void put(int key, int value) {if(_capacity == 0){return;}auto it = _keyTable.find(key); //查找key是否存在，判断是更新还是插入if(it != _keyTable.end()) //如果存在，则是更新{list<LFUNode>::iterator node = it->second;int freq = node->_freq;_freqTable[freq].erase(node);if(_freqTable[freq].empty() && _minFreq == freq){_minFreq++;}_freqTable[freq + 1].push_front(LFUNode(key, value, freq + 1));it->second = _freqTable[freq + 1].begin();}else //不存在则是插入{//如果缓存满了，则要先删除后才能插入if(_keyTable.size() == _capacity){//查询freq表，获取freq最少且最久没有使用的节点，即freq链表的尾部节点LFUNode node = _freqTable[_minFreq].back();_keyTable.erase(node._key); //删除key表中的节点_freqTable[node._freq].pop_back(); //删除freq表中的节点}_freqTable[1].push_front(LFUNode(key, value, 1));//在freq表中插入新节点_keyTable.insert(make_pair(key, _freqTable[1].begin()));//在key表中插入新节点_minFreq = 1; //插入新元素，它为最小的}}private:unordered_map<int, list<LFUNode>::iterator> _keyTable; //建立key与节点迭代器的映射unordered_map<int, list<LFUNode>> _freqTable; //建立freq与该值链表的映射int _minFreq; //保存当前最小的freq，便于淘汰int _capacity; //缓存最大容量};

如果觉得《高级数据结构与算法 | LFU缓存机制（Least Frequently Used）》对你有帮助，请点赞、收藏，并留下你的观点哦！