【哈希链表】LRU缓存机制

• LRU缓存算法的核心数据结构：哈希双向链表
  

• 只有双向链表才有前驱节点的指针，因为我们删除操作不光要找到当前节点的指针，还要操作其前驱节点的指针
  

• 伪代码描述：
  

  - 
  - ![](https://cdn.nlark.com/yuque/0/2021/png/10363855/1618112280153-3a69333f-8040-46bc-a637-411ad92c2542.png#width=328)<br />

  • 代码：
    
  • class LRUCache {
  • private:
  • int cap;
  • list> cache;
  • unordered_map>::iterator> table;
  • public:
  • LRUCache(int capacity) : cap(capacity) {
  • }
  • int get(int key) {
  • if (table.find(key) == table.end())
  • return -1;
  • auto k_v = *table[key];
  • cache.erase(table[key]);
  • cache.push_front(k_v);
  • table[key] = cache.begin();
  • return k_v.second;
  • }
  • void put(int key, int value) {
  • if (table.find(key) == table.end()) {
  • if (cache.size() == cap) {
  • table.erase(cache.back().first);
  • cache.pop_back();
  • }
  • }
  • else
  • cache.erase(table[key]);
  • cache.push_front({key, value});
  • table[key] = cache.begin();
  • }
  • };