要求

这也是leetcode的题目之一——《146. LRU缓存设计》

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

解答：双链表 + 哈希表

可以使用 HashMap 存储 key，这样可以做到 save 和 get key 的时间都是 O(1)，而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点

  • 用队列可以吗

    不行，队列只能做到先进先出，但是重复用到中间的数据时无法把中间的数据移动到顶端。

  • 用单链表不行吗

    单链表能实现新来的放头部，最久不用的在尾部删除。但删除的时候需要遍历到尾部，因为单链表只有头指针。在用到已经用到过的数据时，还要遍历整合链表，来确定是否用过，然后再遍历到响应位置来剔除的节点，并重新放在头部

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <list>
#include <iostream>
#include <unordered_map>
using namespace std;

class LRUCache {
public:
    LRUCache(int capacity) {
        capacity_ = capacity;
    }
    
    int get(int key) {
        if (hash.count(key)) {
            int val = hash[key]->second;
            put(key, val);
            return val;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if (hash.count(key)) { // 存在，先删除
            hot_list.erase(hash[key]);
        }
        if (hot_list.size() >= capacity_) { // 逐出最后元素
            hash.erase(hot_list.back().first);
            hot_list.pop_back();
        }
        // 更新最热kv
        hot_list.push_front(pair<int, int>(key, value));
        hash[key] = hot_list.begin();
    }
private:
    int capacity_;
    list<pair<int, int>> hot_list;
    unordered_map<int, list<pair<int, int>>::iterator> hash; // key -> host_list node
};