题解 | 设计LRU缓存结构

1、解题思路

为了实现LRU缓存，我们需要满足以下条件：

1. 快速访问：get和set操作的时间复杂度为O(1)。
2. 记录访问顺序：需要快速找到并更新最近使用的key，同时移除最久未使用的key。

数据结构选择：

• 哈希表（Hash Map）：用于快速查找key对应的value。
• 双向链表（Doubly Linked List）：用于维护key的访问顺序，最近使用的放在头部，最久未使用的放在尾部。

2、代码实现

C++

#include <list>
#include <string>
#include <unordered_map>
#include <utility>
class Solution {
  public:
    Solution(int capacity) {
        // write code here
        this->capacity = capacity;
    }

    int get(int key) {
        // write code here
        auto it = cache_map.find(key);
        if (it == cache_map.end()) {
            return -1;
        }
        // 将访问的节点移到链表头部
        cache_list.splice(cache_list.begin(), cache_list, it->second);
        return it->second->second;
    }

    void set(int key, int value) {
        // write code here
        auto it = cache_map.find(key);
        if (it != cache_map.end()) {
            // 更新 value 并移到链表头部
            it->second->second = value;
            cache_list.splice(cache_list.begin(), cache_list, it->second);
        } else {
            // 插入新结点到链表头部
            cache_list.emplace_front(key, value);
            cache_map[key] = cache_list.begin();
            // 如果超出容量, 移除链表尾部节点
            if (cache_map.size() > capacity) {
                cache_map.erase(cache_list.back().first);
                cache_list.pop_back();
            }
        }
    }

  private:
    int capacity;
    unordered_map<int, list<pair<int, int>>::iterator> cache_map;
    list<pair<int, int>> cache_list;
};

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

Java

import java.util.*;


public class Solution {
    private LinkedHashMap<Integer, Integer> cache;
    private int capacity;

    public Solution(int capacity) {
        // write code here
        this.capacity = capacity;
        this.cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        // write code here
        return cache.getOrDefault(key, -1);
    }

    public void set(int key, int value) {
        // write code here
        cache.put(key, value);
    }
}

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

3、复杂度分析

1. 哈希表：用于快速查找key对应的value，时间复杂度为O(1)。
2. 双向链表 ：用于维护key的访问顺序： 最近使用的key放在链表头部。最久未使用的key放在链表尾部。插入和移动操作的时间复杂度为O(1)。
3. 容量控制：当缓存大小超过容量时，移除链表尾部的key-value。