Node(k,v)存储最方便的应当是哈希表,但假设的是内存资源是有限的,所以在到达内存阈值的时候必须淘汰一些旧数据以存放新数据,这个时候的策略最常见的有LRU和LFU。LRU是“最近最久未使用”,淘汰的是最久未使用的数据。LFU是“最近最少使用算法”,淘汰的是使用频度最低的元素。通常有public方法:
int get(int key);
int put(int key, int value);
LRU
一个哈希表+一个双链表
哈希表存储Node(k,v)映射,淘汰则由std::list负责(尾部的是旧数据,头部的是最新数据),实现较为简单:
class LRUCache{
public:
void put(int key, int val);
int get(int key);
private:
struct Node{
public:
Node(int k, int v):key(k),value(v){}
private:
int key;
int value;
};
int ksize;
unordered_map<int,std::list<Node>::iterator> map;
std::list<Node> LRUList;
};
关于更新数据:get和put都会更新最近最久未使用的数据,只需要将对应的Node*转移到list首部
int LRUCache::get(int key){
if(map.find(key)==map.end()){
return -1;
}
LRUList.splice(LRUList.begin(),LRUList,map[key]);
map[key]=LRUList.begin();
return map[key]->val;
}
void LRUCache::put(int key,int val){
if(map.find(key)!=map.end()){
LRUList.splice(LRUList.begin(),LRUList,map[key]);
map[key]=LRUList.begin();
map[key]->val=val;
}else{
if(LRUList.size()==ksize){
map.erase(LRUList.back()->key);
LRUList.pop_back();
}
LRUList.push_front(Node(key,val));
map[key]=LRUList.begin();
}
}
LFU
一个哈希表+用频率哈希映射多个双链表
双向链表节点:
struct Node {
int key;
int val;
int freq;//频率
Node* prev;
Node* next;
Node () : key(-1), val(-1), freq(0), prev(nullptr), next(nullptr) {}
Node (int _k, int _v) : key(_k), val(_v), freq(1), prev(nullptr), next(nullptr) {}
};
频率的双向链表:
struct FreqList {
int freq;
//给双向链表加上了虚拟的头结点和尾结点,并在初始化的时候首尾相接。
Node* head;
Node* tail;
FreqList (int _f) : freq(_f), head(new Node()), tail(new Node()) {
head->next = tail;
tail->prev = head;
}
};
有了两个基本结构,就可以思路较清晰地写出LFU了:
class LFUCache{
public:
LFUCache (int capacity) : size(capacity) {}
void put(int key, int val);
int get(int key);
private:
int size;
unordered_map<int,Node*> kvMap;
unordered_map<int,FreqList*> freqMap;
int min_freq;
private:
bool empty(FreqList* l);
void removeNode(Node* t);
void insertNode(Node* t);
void popMinFreqList();
};
关于min_freq:
每次get() 时,都有可能改变min_freq,所以每次都要查询对应的链表是否为空,为空说明min_freq被操作了一次,需要+1;
每次put() 时,如果是新插入的值,那么其freq一定是1,是最小的,所以此时把min_freq重置为1;
关于更新数据:
由于put和get都会使得节点的频率增加,就需要跨频率链表移动节点,这需要辅助函数的支持:
bool empty(FreqList* l) {
return l->head->next == l->tail ? true : false;
}
void removeNode (Node* t) {
t->prev->next = t->next;
t->next->prev = t->prev;
}
void insertNode (Node* t) {
int freq = t->freq;
if (freqMap.find(freq) == freqMap.end()) {
freqMap[freq] = new FreqList(freq);
}
FreqList* l = freqMap[freq];
t->next = l->head->next;
l->head->next->prev = t;
t->prev = l->head;
l->head->next = t;
}
void popTail () {
Node* t = freqMap[min_freq]->tail->prev;
removeNode(t);
kvMap.erase(t->key);
}
get和put
int get (int key) {
int res = -1;
if (kvMap.find(key) != kvMap.end()) {
Node* t = kvMap[key];
res = t->val;
removeNode(t);
t->freq++;
if (empty(freqMap[min_freq])) min_freq++;//最少频率更新
insertNode(t);
}
return res;
}
void put (int key, int value) {
if (size == 0) return;
if (get(key) != -1) {
kvMap[key]->val = value;
}else {
if (kvMap.size() == size) {
popTail();
}
Node* t = new Node(key, value);
kvMap[key] = t;
min_freq = 1;//新插入的 频率一定最少, 为1
insertNode(t);
}
}