Simulation problem (below)

设计LFU缓存结构

描述
一个缓存结构需要实现如下功能.
set(key, value)：将记录(key, value)插入该结构
get(key)：返回key对应的value值
But up to put in the cache structureK条记录,如果新的第K+1条记录要加入,就需要根据策略删掉一条记录,然后才能把新记录加入.这个策略为：在缓存结构的K条记录中,哪一个key从进入缓存结构的时刻开始,被调用set或者get的次数最少,就删掉这个key的记录;
如果调用次数最少的key有多个,上次调用发生最早的key被删除
这就是LFU缓存替换算法.实现这个结构,K作为参数给出

解法:双哈希表

需要在O(1)two operations in time,The first thing that comes to our mind is the hash table,Save with hash tableLFU的key值,而哈希表的valueThe value corresponds to the node on the other side that stores the class required by each cache,This enables direct access.

But we also need to find the node with the least frequency that has not been used for the longest time.,At this time, we can consider using a global variable,Track record minimum frequency,with minimum frequency,How to directly find the node with the smallest frequency,or use a hash table,keyvalue records each frequency,而valueThe value is followed by a string of nodes of the same frequency.How to ensure that each time is the longest use with the minimum frequency,We use a doubly linked list to connect nodes of uniform frequency.,Every new to join this frequency in the head,And what needs to be removed is at the end of the linked list.

So that we way is to double hash table.

• Each node needs to be established,Each node represents a joinLFU中的结构,需要频率,key值,val值.

class Node{
     
    int freq;
    int key;
    int val;
    //初始化
    public Node(int freq, int key, int val) {
    
        this.freq = freq;
        this.key = key;
        this.val = val;
    }
}

• Build the first hash tablemp,在每个节点的keyThe value establishes a mapping connection directly with the node,Build a second hash tablefreq_mp,Directly establish a mapping connection between the frequency and the nodes in the doubly linked list at this frequency（That is, to establish a mapping with this doubly linked list）.这样可以根据keyvalue directly access each node,Directly find the least used and longest unused node by frequency.复杂度都是O(1).

//Frequency to two-way linked list hash table
Map<Integer, LinkedList<Node> > freq_mp = new HashMap<>();
//keyhash table to node
Map<Integer, Node> mp = new HashMap<>();

• LFUThe remaining capacity and the current minimum frequency are set as global variables,并初始化.
• 遍历函数的操作数组,检查第一个元素判断是属于set操作还是get操作.
• 对于set操作,If the hash table already haskey值,说明它已经在LFU中了,directly modify the node frequency andval即可.

//found in the hash tablekey值
if(mp.containsKey(key)) 
    //If the hash table has,then update value and frequency
    update(mp.get(key), key, value);

如果哈希表中没有,At this point, consider whether there is still capacity,If there are capacity,Capacity needs to be reduced1;If there is no capacity,Take the doubly linked list of the minimum frequency from the second hash table according to the current minimum frequency,The last one in the linked list is the one that is used the least frequently and has not been used for the longest time.,将其取出：链表中删除,Hash table are deleted,如果链表为空了,Then the corresponding frequency is also deleted in the hash table.

//哈希表中没有,即链表中没有
if(size == 0){
    
    //Full capacity takes the least frequent and earliest deletion
    int oldkey = freq_mp.get(min_freq).getLast().key; 
    //frequency hash table delete from linked list
    freq_mp.get(min_freq).removeLast(); 
    if(freq_mp.get(min_freq).isEmpty()) 
        freq_mp.remove(min_freq); 
    //Delete from linked list hash table
    mp.remove(oldkey); 
}

• 加入的时候,添加新的节点,频次为1,Node joins first hash table,At the same time, add the header of the corresponding frequency linked list of the second hash table.

if(!freq_mp.containsKey(freq + 1))
    freq_mp.put(freq + 1, new LinkedList<Node>());
//Doubly linked list header with insertion frequency plus one,Corresponding in the linked list：freq key value
freq_mp.get(freq + 1).addFirst(new Node(freq + 1, key, value)); 
mp.put(key, freq_mp.get(freq + 1).getFirst());

• 对于get操作,Look directly at the first hash tablekeyvalue found,have access to,then modify the frequency,没有则返回-1.

if(mp.containsKey(key)){
     
    Node node = mp.get(key);
    //Get the value directly from the hash table
    res = node.val;
    //更新频率 
    update(node, key, res); 
}

• when changing the frequency,Take out the node at this frequency,In the hash table with the frequency1The first in the list.If there is no node in the linked list at this frequency,Then delete this frequency from the hash table,At the same time, if the frequency of the linked list before modification is equal to the lowest frequency,Indicates that the minimum has increased.

//find frequency
int freq = node.freq;
//Delete the node from the original frequency
freq_mp.get(freq).remove(node); 
//There are no nodes at this frequency in the hash table,直接删除
if(freq_mp.get(freq).isEmpty()){
     
    freq_mp.remove(freq);
    //If the current frequency to a minimum,Minimum frequency plus1
    if(min_freq == freq) 
        min_freq++;
    }
......//Doubly linked list header with insertion frequency plus one,Corresponding in the linked list：freq key value

class Solution {
    
public:
    //用list模拟双向链表,array in doubly linked list0bit is frequency,第1位为key,第2位为val
    //Frequency to two-way linked list hash table
    unordered_map<int, list<vector<int> > > freq_mp; 
    //keyThe hash table to two-way linked list node
    unordered_map<int, list<vector<int> > ::iterator> mp;
    //Record the current minimum frequency
    int min_freq = 0; 
    //Record cache remaining capacity
    int size = 0; 
    
    vector<int> LFU(vector<vector<int> >& operators, int k) {
    
        //记录输出
        vector<int> res; 
        size = k; 
        //遍历所有操作
        for(int i = 0; i < operators.size(); i++){
    
            auto op = operators[i];
            if(op[0] == 1)
                //set操作
                set(op[1], op[2]);
            else
                //get操作
                res.push_back(get(op[1]));
        }
        return res;
    }
    
    //update frequency when the function is called orval值
    void update(list<vector<int> >::iterator iter, int key, int value) {
     
        //find frequency
        int freq = (*iter)[0];
        //Delete the node from the original frequency
        freq_mp[freq].erase(iter); 
        //There are no nodes at this frequency in the hash table,直接删除
        if(freq_mp[freq].empty()){
     
            freq_mp.erase(freq);
            //If the current frequency to a minimum,Minimum frequency plus1
            if(min_freq == freq) 
                min_freq++;
        }
        //Doubly linked list header with insertion frequency plus one,Corresponding in the linked list：freq key value
        freq_mp[freq + 1].push_front({
    freq + 1, key, value}); 
        mp[key] = freq_mp[freq + 1].begin(); 
    }
    
    //set操作函数
    void set(int key, int value) {
    
        //found in the hash tablekey值
        auto it = mp.find(key); 
        if(it != mp.end())
            //If the hash table has,then update value and frequency
            update(it->second, key, value);
        else{
     
            //哈希表中没有,即链表中没有
            if(size == 0){
    
                //Full capacity takes the least frequent and earliest deletion
                int oldkey = freq_mp[min_freq].back()[1]; 
                //frequency hash table delete
                freq_mp[min_freq].pop_back(); 
                if(freq_mp[min_freq].empty()) 
                    freq_mp.erase(min_freq); 
                //Delete from linked list hash table
                mp.erase(oldkey); 
            }
            //Join directly if you are free,容量减1
            else 
                size--; 
            //The minimum frequency is set to1
            min_freq = 1; 
            //在频率为1Insert the key at the head of the doubly linked list
            freq_mp[1].push_front({
    1, key, value}); 
            //哈希表keyThe value points to this position in the linked list
            mp[key] = freq_mp[1].begin(); 
        }
    }
    
    //get操作函数
    int get(int key) {
    
        int res = -1;
        //查找哈希表
        auto it = mp.find(key);
        if(it != mp.end()){
     
            auto iter = it->second; 
            //Get the value directly from the hash table
            res = (*iter)[2];
            //更新频率 
            update(iter, key, res); 
        }
        return res;
    }
};

时间复杂度：O(n),Depending on the operandsn
空间复杂度：O(k),Depends on cache capacityk