LFU双哈希表实现

LFU即最不经常使用。LFU算法的思想是一定时期内被访问次数最少的节点,在将来被访问到的几率也是最小的。当缓存达到上限,再插入新的数据,需要将访问频次最小的数据删除。LFU强调的是访问次数,而LRU强调的是访问时间。

LFU优点:

  相比LRU,LFU的缓存命中率高;

缺点:

  第一,LFU要记录每个key的频次,会浪费空间;第二,对时间不敏感,某个数据曾经访问频次很高,但是过了时间点,该数据不被访问,由于当初的访问频次高,该数据会在相当长的一段时间内常驻内存。

双哈希表实现LFU

第一个哈希表是 freq_table,它的key是访问的频次,它的value是一个双向链表,双向链表的每一个节点包含三个元素:key,value,freq。

第二个哈希表是 key_table,它的key是双向链表中存储的key,value是对应节点的迭代器。

如图所示,假设缓存的内存是3,初始时连续插入三个键值对,(1,1)(2,2)(3,3),他们的频次都是1,记录最小频次minfreq=1;

LFU双哈希表实现

 

当我们访问了某个键值对,就要将对应的的频次+1,将结点移动到修改后的频次所对应的链表上。例如get(1)后,key1所对应的频次为2,将(1,1,2)结点挂在freq_table上频次为2的链表上。记录最小频次minfreq=1;

LFU双哈希表实现

 当再插入(4,4,1)时,容量已经溢出,要删除频次最少,插入时间最晚的,也就是(3,3,1),记录最小频次minfreq=1;

LFU双哈希表实现

 代码定义链表结点类型

 

struct Node
{
    int key,val,freq;
    Node(int k,int v,int f):key(k),val(v),freq(f){}
};
class Solution {
public:
  
    int minfreq=0;
    unordered_map<int, list<Node>::iterator>key_table;
    unordered_map<int, list<Node>>freq_table;
    void set(int key,int val,int cap)//插入元素
    {
        if(cap==0) return;
        auto it=key_table.find(key);
       case1:缓存中没有待插入的数据
        if(it==key_table.end())
        {
            缓存已经满了
            if(key_table.size()==cap)
            {//找到频次最小的链表中的最后一个数据
                auto it=freq_table[minfreq].back(); 
                //删除key_table中该数据key
                key_table.erase(it.key);
                freq_table[minfreq].pop_back();//删除结点
                //如果该频次所对应的链表为空,删除键值对
                if(freq_table[minfreq].size()==0)
                    freq_table.erase(minfreq);
            }
            //新插入的数据频次都是1
            freq_table[1].push_front(Node(key,val,1));
            //修改迭代器的指向
            key_table[key]=freq_table[1].begin();
            minfreq=1; //修改最小频次
        }else//缓存中有插入数据,修改value和freq即可
        {
            auto it=key_table[key];
            int freq=it->freq;
            freq_table[freq].erase(it);
            if(freq_table[freq].size()==0)
            {
                freq_table.erase(key);
                if(minfreq==freq)
                    minfreq++;
            }
            freq_table[freq+1].push_front(Node(key,val,freq+1));
            key_table[key]=freq_table[freq+1].begin();
        }
    }
   //找到返回对应的value,修改频次,将它挂在正确的freq_table后面,
 //修改key_table的value。没有找到返回-1
    int get(int key)
    {
        auto it=key_table.find(key);
        if(it==key_table.end()) return -1;
        list<Node>::iterator node=it->second;
        int value=node->val;
        int freq=node->freq;
        freq_table[freq].erase(node);
        if(freq_table[freq].size()==0)
        { 
            freq_table.erase(freq);
            if(minfreq==freq)
                minfreq+=1;
        }
        freq_table[freq+1].push_front(Node(key,value,freq+1));
        key_table[key]=freq_table[freq+1].begin();
        return value;
    }

 

上一篇:STM32学习笔记(三 时钟系统 1 时钟系统精讲)


下一篇:【LeetCode】895. 最大频率栈