题解 | #设计LRU缓存结构#

哈希表：利用查找O(1)特性，用于记录key对应的键值对在链表中的位置，用指针表示。

双向链表：利用插入和删除操作的O(1)特性。用于模拟缓存，当哈希表给出了操作的位置，就可以直接调整链表结点的指针从而实现O(1)的插入和删除。

class Solution {
  private:
    int capacity;
    unordered_map<int, list<pair<int, int>>::iterator> hash; //{key=iterator}
    list<pair<int, int>> cache; //{"1"="1","2"="2"}
  public:
    Solution(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        if (hash.find(key) != hash.end()) {
            auto kv = hash[key];
            cache.erase(hash[key]);
            cache.push_front(*kv);
            return (*kv).second;
        } else {
            return -1;
        }
    }

    void set(int key, int value) {
        if (hash.find(key) == hash.end()) {
            if (cache.size() == capacity) {
                hash.erase(cache.back().first);
                cache.pop_back();
            }
        } else {
            cache.erase(hash[key]);
        }
        cache.push_front({key, value});
        hash[key] = cache.begin();
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* solution = new Solution(capacity);
 * int output = solution->get(key);
 * solution->set(key,value);
 */