牛客网：设计LRU缓存结构 设计LFU缓存结构

目录

1.设计LRU缓存结构

Get

Set

2.设计LFU缓存结构

Get

Set

Update

---

1.设计LRU缓存结构

 这题，说实话，一开始没看懂他的输入到底是什么...

看看说明，好像又是这么一回事，就是创建一个类然后直接调用里面的方法：

其实是维护一个双向链表，写过XV6操作系统的内存和锁那块的同学应该知道这个LRU到底是个啥。思路如下所示：

整个LRU维护一个链表和一个哈希表两个数据结构，链表可以直接用list双向链表，哈希表用unordered_map来设计，哈希表存的是key和在链表中的迭代器的对应关系。

Get

首先，对于get操作，功能是这样的：对于一个给定的key，我们要在链表中查看其是否存在，这里哈希可以实现O(1)的寻找时间代价，处理流程如下：

1.查找是否存在key对应的节点，没有则直接返回-1

2.否则，我们先根据key在哈希中取出对应的节点，然后将对应节点删除。

因为是LRU，所以我们要把最近使用的放在最前面（虽然用了哈希表但是按照LRU的思路还是得放最前面），所以我们把取出来的节点放到链表头部，然后再在哈希表中建立<key, list.begin()>的映射关系。

最后返回头部节点的value

Set

对于set操作，功能是这样的：对于一个给定的<key, value>，如果在链表中存在key的节点，那么修改并放到链表头，如果不存在，那么直接在前面添加节点当作链表头，还要考虑链表是不是会炸掉的问题，如果容量已经达到了，那么根据LRU的原则，我们先删除链表尾部

代码如下所示：

class Solution {
public:
    list<pair<int, int>> dlist;
    unordered_map<int, list<pair<int, int>>::iterator> map;
    int cap;
    
    Solution(int capacity){
        cap=capacity;
    }
    
    
    int get(int key) {
         // write code here
        if(map.count(key)){
            auto tmp=*map[key];
            dlist.erase(map[key]);
            dlist.push_front(tmp);
            map[key]=dlist.begin();
            return dlist.front().second;
        }
        return -1;
    }
    
    void set(int key, int value){
         if(map.count(key)){
            dlist.erase(map[key]);
         }else if(cap==dlist.size()){
            auto tmp=dlist.back();
             map.erase(tmp.first);
             dlist.pop_back();
         }
            dlist.push_front(pair<int, int>(key, value));
             map[key]=dlist.begin();        
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* solution = new Solution(capacity);
 * int output = solution->get(key);
 * solution->set(key,value);
 */

当然，除了可以用标准库里的数据结构，我们也可以自己手撸一个双向链表，我们需要分离出以一个将节点移动到表头的函数，以便于当我们在进行get操作找到一个节点，或者set的时候将对应的节点放到表头。

代码如下所示，这里面有很多的细节要注意，主要是数据结构的更新和哈希的更新：

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int key;
    int val;
    Node *prev;
    Node *next;
    Node(int key, int val) : key(key), val(val), next(NULL), prev(NULL) {}
};

class Solution {
public:
    unordered_map<int, Node*> hash;
    Node *head;
    Node *tail;
    int cap;
    int size;
    Solution(int capacity){
        head=NULL;
        tail=NULL;
        cap=capacity;
        size=0;
        hash.clear();
    }
    // 将某个节点放到表头
    // 如果位于尾部 需要更新尾节点
    // 移到头部后需要更新指针指向以及更新头节点
    void removeToHead(Node *p){
        // 首先修改
        if(p==head){
            return;
        }
        p->prev->next=p->next;
        if(p==tail){
            tail=p->prev;
        }else{
            p->next->prev=p->prev;
        }
        p->prev=NULL;
        p->next=head;
        head->prev=p;
        head=p;
        return;
    }

    int get(int key) {
        if(hash.find(key)==hash.end()){
            return -1;
        }
        removeToHead(hash[key]);
        return hash[key]->val;
    }

    void set(int key, int value){
        if(hash.find(key)!=hash.end()){
            hash[key]->val=value;
            removeToHead(hash[key]);
        }else if(size>=cap){
            //将尾节点更新为当前节点 移动到头部
            //更新哈希表 删除原来的 增加新的
            int k=tail->key;
            hash.erase(k);
            tail->key=key;
            tail->val=value;
            removeToHead(tail);
            hash[key]=head;
        }else{
            //不存在节点 且容量还没满 直接在头部插入
            Node *node=new Node(key, value);
            if(head==NULL){
                head=tail=node;
            }else{
                node->next=head;
                node->prev=NULL;
                head->prev=node;
                head=node;
            }
            hash[key]=head;
            size++;
        }

    }
};

2.设计LFU缓存结构

上面的LRU是最近最少使用的策略，LFU是least frequently used，从字面上来看貌似也是最近最少使用策略嘛，但是从题目来看，是还让我们记录使用set和get的次数的。

我们这里用一个双哈希表来解决这个题目，同时在题解中看到了一个画的很好的图：

这就是我们要维护的数据结构。首先，对于每个频率，我们维护一个双向链表，这个双向链表代表了对应频率的节点的集合，存储的是{freq, key, value}，这样就形成了频率和链表的哈希表。我们根据这个哈希表可以轻松根据频率找到双向链表，在容量不足的时候用来找删除的节点时十分迅速。其次也方便一些删除插入的更新操作。也由于要在容量不足的时候删除节点，我们需要用一个变量来存储freq最小的节点。

第二个哈希表是key和链表节点的哈希表，这个哈希表对于get操作是十分必须的。

接下来解析一下get和set操作的流程：

Get

get操作的功能是根据key找value，有了哈希表之后，我们可以直接根据key找到对应节点，然后找到value，如果没有找到则返回-1。

Set

set操作的功能是设置<key, value>，处理流程如下：

1.如果之前存在这个映射关系，那么我们更新一下这个映射，关于更新是什么，之后说。

2.如果不存在，我们就要插入这个新的映射，当然，还要考虑当前的链表是否已经满了，因此我们还需要维护一个记录剩余空间的变量。

a.如果已经满了，我们需要做一些事情：

首先要找到频率最低的且最少使用的节点，对于频率最低的节点，由于我们维护了频率和对应节点的集合的哈希，我们很快可以找到，对于最少使用，我们每次更新的时候是放到表头，所以最少使用的就是最后一个节点。

找到节点之后我们要删除这个节点，删除之后我们还得检查这个链表是否为空，是空的话还得直接删除这个映射项。

b.如果没有满，我们维护一下剩余的容量

之后直接向freq=1的双向链表头部插入新的<freq=1, key, value>，之后也要更新对应的<key,value>映射。

Update

更新操作用于在set中已经存在对应的key或者对已存在节点使用了get时，更新其频率。

首先，我们根据key取出链表节点，然后根据链表节点中的freq找到对应的链表，之后直接在链表中删除对应节点。

如果删除后这个链表变成空了：

删除对应映射关系，再看是否需要更新最小频率，如果被删除链表是最小频率对应的链表，那么需要更新

最后将新的<freq+1,key,value>插入对应链表，如果是set还需要更新map

具体代码如下所示：

class Solution {
public:
    /**
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    // 存频率和频率对应节点链表的字典
    unordered_map<int, list<vector<int>>> freq_mp;
    // 存对应键值和节点
    unordered_map<int, list<vector<int>>::iterator> mp;
    // 记录最小频率 用来使用LFU策略找节点
    int min_freq=0;
    // 存剩余容量
    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){
            if(operators[i][0]==1){
                set(operators[i][1], operators[i][2]);
            }else{
                res.push_back(get(operators[i][1]));
            }
        }
        return res;
    }
    
    void update(list<vector<int>>::iterator iter, int key, int value){
        //取出双向链表中的一个节点 即 vector<int>
        int freq=(*iter)[0];
        freq_mp[freq].erase(iter);
        //如果该频率中已经没有节点
        //删除频率双向链表中的对应链表
        //查看是否需要更新最小频率
        if(freq_mp[freq].empty()){
            freq_mp.erase(freq);
            if(freq == min_freq){
                min_freq++;
            }
        }
        //向freq+1的双向链表头部中插入
        //由于原来的节点已经不存在 需要重新设置<key,value>的存储
        freq_mp[freq+1].push_front({freq+1, key, value});
        mp[key]=freq_mp[freq+1].begin();
    }
    
    void set(int key, int value){
        auto it=mp.find(key);
        if(it!=mp.end()){
            //链表中存在节点 更新value和频率
            update(it->second, key, value);
        }else{
            //哈希表中没有该节点
            //如果链表已满 删除频率最低而且最早的删掉
            //频率表中删除最后一个节点
            //删除对应<key,value>的节点
            if(size==0){
                int oldkey=freq_mp[min_freq].back()[1];
                freq_mp[min_freq].pop_back();
                if(freq_mp[min_freq].empty()){
                    freq_mp.erase(min_freq);
                }
                mp.erase(oldkey);
            }else{
                //容量未满 可以直接加入
                size--;
            }
            min_freq=1;
            freq_mp[1].push_front({1, key, value});
            mp[key]=freq_mp[1].begin();
        }
    }
    
    //get操作:没有找到则返回-1
    //找到则更新频率并且取出value返回
    int get(int key){
        int res=-1;
        auto it = mp.find(key);
        if(it==mp.end()){
            return res;
        }
        auto iter = it->second;
        res=(*iter)[2];
        update(iter, key, res);
        return res;
    }
};

不得不说，数据结构和相应的存储结合真是一件巧妙的事情~