Node(k,v)存储最方便的应当是哈希表,但假设的是内存资源是有限的,所以在到达内存阈值的时候必须淘汰一些旧数据以存放新数据,这个时候的策略最常见的有LRU和LFU。LRU是“最近最久未使用”,淘汰的是最久未使用的数据。LFU是“最近最少使用算法”,淘汰的是使用频度最低的元素。通常有public方法:

  1. int get(int key);
  2. int put(int key, int value);

LRU

一个哈希表+一个双链表
哈希表存储Node(k,v)映射,淘汰则由std::list负责(尾部的是旧数据,头部的是最新数据),实现较为简单:

  1. class LRUCache{
  2. public:
  3. void put(int key, int val);
  4. int get(int key);
  5. private:
  6. struct Node{
  7. public:
  8. Node(int k, int v):key(k),value(v){}
  9. private:
  10. int key;
  11. int value;
  12. };
  13. int ksize;
  14. unordered_map<int,std::list<Node>::iterator> map;
  15. std::list<Node> LRUList;
  16. };

关于更新数据:get和put都会更新最近最久未使用的数据,只需要将对应的Node*转移到list首部

  1. int LRUCache::get(int key){
  2. if(map.find(key)==map.end()){
  3. return -1;
  4. }
  5. LRUList.splice(LRUList.begin(),LRUList,map[key]);
  6. map[key]=LRUList.begin();
  7. return map[key]->val;
  8. }
  9. void LRUCache::put(int key,int val){
  10. if(map.find(key)!=map.end()){
  11. LRUList.splice(LRUList.begin(),LRUList,map[key]);
  12. map[key]=LRUList.begin();
  13. map[key]->val=val;
  14. }else{
  15. if(LRUList.size()==ksize){
  16. map.erase(LRUList.back()->key);
  17. LRUList.pop_back();
  18. }
  19. LRUList.push_front(Node(key,val));
  20. map[key]=LRUList.begin();
  21. }
  22. }

LFU

一个哈希表+用频率哈希映射多个双链表
LRU和LFU - 图1
双向链表节点:

  1. struct Node {
  2. int key;
  3. int val;
  4. int freq;//频率
  5. Node* prev;
  6. Node* next;
  7. Node () : key(-1), val(-1), freq(0), prev(nullptr), next(nullptr) {}
  8. Node (int _k, int _v) : key(_k), val(_v), freq(1), prev(nullptr), next(nullptr) {}
  9. };

频率的双向链表:

  1. struct FreqList {
  2. int freq;
  3. //给双向链表加上了虚拟的头结点和尾结点,并在初始化的时候首尾相接。
  4. Node* head;
  5. Node* tail;
  6. FreqList (int _f) : freq(_f), head(new Node()), tail(new Node()) {
  7. head->next = tail;
  8. tail->prev = head;
  9. }
  10. };

有了两个基本结构,就可以思路较清晰地写出LFU了:

  1. class LFUCache{
  2. public:
  3. LFUCache (int capacity) : size(capacity) {}
  4. void put(int key, int val);
  5. int get(int key);
  6. private:
  7. int size;
  8. unordered_map<int,Node*> kvMap;
  9. unordered_map<int,FreqList*> freqMap;
  10. int min_freq;
  11. private:
  12. bool empty(FreqList* l);
  13. void removeNode(Node* t);
  14. void insertNode(Node* t);
  15. void popMinFreqList();
  16. };

关于min_freq:

  1. 每次get() 时,都有可能改变min_freq,所以每次都要查询对应的链表是否为空,为空说明min_freq被操作了一次,需要+1
  2. 每次put() 时,如果是新插入的值,那么其freq一定是1,是最小的,所以此时把min_freq重置为1

关于更新数据:

由于put和get都会使得节点的频率增加,就需要跨频率链表移动节点,这需要辅助函数的支持:

  1. bool empty(FreqList* l) {
  2. return l->head->next == l->tail ? true : false;
  3. }
  4. void removeNode (Node* t) {
  5. t->prev->next = t->next;
  6. t->next->prev = t->prev;
  7. }
  8. void insertNode (Node* t) {
  9. int freq = t->freq;
  10. if (freqMap.find(freq) == freqMap.end()) {
  11. freqMap[freq] = new FreqList(freq);
  12. }
  13. FreqList* l = freqMap[freq];
  14. t->next = l->head->next;
  15. l->head->next->prev = t;
  16. t->prev = l->head;
  17. l->head->next = t;
  18. }
  19. void popTail () {
  20. Node* t = freqMap[min_freq]->tail->prev;
  21. removeNode(t);
  22. kvMap.erase(t->key);
  23. }

get和put

  1. int get (int key) {
  2. int res = -1;
  3. if (kvMap.find(key) != kvMap.end()) {
  4. Node* t = kvMap[key];
  5. res = t->val;
  6. removeNode(t);
  7. t->freq++;
  8. if (empty(freqMap[min_freq])) min_freq++;//最少频率更新
  9. insertNode(t);
  10. }
  11. return res;
  12. }
  1. void put (int key, int value) {
  2. if (size == 0) return;
  3. if (get(key) != -1) {
  4. kvMap[key]->val = value;
  5. }else {
  6. if (kvMap.size() == size) {
  7. popTail();
  8. }
  9. Node* t = new Node(key, value);
  10. kvMap[key] = t;
  11. min_freq = 1;//新插入的 频率一定最少, 为1
  12. insertNode(t);
  13. }
  14. }