LFU缓存

题目描述

设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。

 示例

LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );

 思路：

LFU的节点采用双链表结构进行存储，利用两个hash_map分别存储节点数据以及每个节点访问的频率。

struct List_node{ int key, value; int count; int size; List_node *next, *prev; }; void list_add_after(List_node* prev_node, List_node* node) { prev_node->next->prev = node; node->next = prev_node->next; node->prev = prev_node; prev_node->next = node; } List_node* list_remove(List_node* node) { node->prev->next = node->next; node->next->prev = node->prev; node->prev = node->next = node; return node; } List_node* list_create() { List_node* node = new List_node(); node->next = node->prev = node; return node; } void count_hash_table_add_node(unordered_map 
  
    & count_hash_table, List_node* node) { if (count_hash_table.find(node->count) == count_hash_table.end()) { count_hash_table.insert(make_pair(node->count, node)); node->size = 1; return; } List_node* head = count_hash_table.find(node->count)->second; list_add_after(head->prev, node); head->size++; } void count_hash_table_remove_node(unordered_map 
   
     & count_hash_table, List_node* node) { List_node* head = count_hash_table.find(node->count)->second; if (head->size != 1) { if (head == node) { count_hash_table[head->count] = head->next; head->next->size = head->size - 1; } else { head->size = head->size - 1; } list_remove(node); node->size = 0; } else { list_remove(node); node->size = 0; count_hash_table.erase(node->count); } } class LFUCache { public: int _size; int _capacity; int min_count; unordered_map 
    
      key_hash_table; unordered_map 
     
       count_hash_table; LFUCache(int capacity) { _size = 0; _capacity = capacity; } int get(int key) { if (key_hash_table.find(key) == key_hash_table.end()) { return -1; } List_node* node = key_hash_table.find(key)->second; count_hash_table_remove_node(count_hash_table, node); if (min_count == node->count && count_hash_table.find(node->count) == count_hash_table.end()) { min_count = node->count + 1; } node->count++; count_hash_table_add_node(count_hash_table, node); return node->value; } void put(int key, int value) { if (get(key) != -1) { List_node* node = key_hash_table.find(key)->second; node->value = value; } else if (_size < _capacity) { List_node* node = list_create(); node->key = key; node->value = value; node->count = 0; node->size = 0; count_hash_table_add_node(count_hash_table, node); min_count = 0; _size++; key_hash_table.insert(make_pair(key, node)); } else if (_capacity > 0) { List_node* node = count_hash_table.find(min_count)->second; count_hash_table_remove_node(count_hash_table, node); key_hash_table.erase(node->key); node->key = key; node->value = value; node->count = 0; node->size = 0; count_hash_table_add_node(count_hash_table, node); min_count = 0; key_hash_table.insert(make_pair(key, node)); } } }; 
      
     
    
  

运行结果