LeetCode.146. LRU 缓存

LeetCode.146. LRU 缓存

难度：medium

思路：

        本题是经典的数据结构设计题，LinkedHashMap为双向链表和哈希表的结合，哈希表提供了快速定位链表元素的作用，之所以选用双向链表而不是普通链表的原因是：双向链表因为记录了前后节点信息，可以实现元素删除的功能；

代码：

class LRUCache {
    // 容量
    int capacity = 0;
    // LinkedHashMap
    LinkedHashMap cache = new LinkedHashMap<>();

    public LRUCache(int capacity) {
        if (capacity > 0) {
            this.capacity = capacity;
        }
    }
    
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        makeRecently(key);
        return cache.get(key);
        // getOrDefault 没有 makeRecently
        // return cache.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        // 如果关键字 key 已经存在
        if (cache.containsKey(key)) {
            // 原地修改
            cache.put(key, value);
            // 需要吗？是必要的
            makeRecently(key);
        } else {
        // 如果不存在
            if (cache.size() >= capacity) {
                // 链表头部就是最近未使用的key
                int oldestKey = cache.keySet().iterator().next();
                cache.remove(oldestKey);
            }
            cache.put(key, value);
        }
    }

    public void makeRecently(int key) {
        int val = cache.get(key);
        cache.remove(key);
        // 插入链表尾部即更新为最近使用
        cache.put(key, val);
    }
}

复杂度分析： 

• 时间复杂度：O(1)，哈希表的增查时间复杂度是O(1)，双向链表的头尾增删也是O(1)，更何况通过哈希表快速定为链表中的元素进行操作；
• 空间复杂度：O(n)，n为链表长度和哈希表存储数据的个数；