146.LRU缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

• $1\le capacity\le 3000$
• $0\le key\le 10000$
• $0\le value\le {10}^5$
• 最多调用 $2\times {10}^5$ 次 get 和 put

解法一(哈希表+双向链表)

思路分析:

1. 首先存储的值是键值对的形式, 所以要首先想到使用哈希表来保证get和put来保证获取元素的复杂度是$O(1)$;
2. 然后需要实现 LRU 的定义, 即保证存储的元素都是最近使用的, 当元素数量超过容量时, 应该删除最少使用的元素;
3. 且使用 get 获取节点时, 也需要将该节点设置为最新使用的;
4. 如果使用队列、栈、数组来控制节点是否最近最少, 则位于中间的节点不好控制, 时间复杂度至少为 O(n), 则会对 get 操作有影响;
5. 所以采用链表来控制元素的访问顺序; 如果是最新添加或访问的节点, 则将其移动到链表头部, 最少访问的节点则位于链表尾部;
6. 当需要删除最少访问节点时, 可以直接从尾部删除; 所以使用两个虚节点head、tail来表示链表头部和尾部;
7. 同时链表需要考虑是单向还是双向, 若是单向链表, 则移动链表中间的节点时, 需要遍历链表才能实现, 此时时间复杂度也为 O(n), 所以使用双向链表, 当需要移动中间节点时, 可以O(1)的得到该节点的前后节点;

实现代码

class LRUCache {

    class Node {
        int key;
        int value;
        Node pre;
        Node next;
        public Node() {
        }
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    Map<Integer, Node> data;
    // 首位节点
    Node head;
    Node tail;
    int capacity;

    public LRUCache(int capacity) {
        this.data = new HashMap<>();
        this.capacity = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        if (data.containsKey(key)) {
            // 节点存在则返回
            Node node = data.get(key);
            // 先删除旧节点位置
            deleteNode(node);
            // 最近访问的节点 移动到链表头部
            moveToHead(node);
            // 返回结果
            return node.value;
        } else {
            return -1;
        }
    }

    // 移动链表节点到头部
    public void moveToHead(Node node) {
        node.next = head.next;
        node.next.pre = node;
        head.next = node;
        node.pre = head;
    }

    // 删除节点
    public void deleteNode(Node node) {
        Node pre = node.pre;
        Node next = node.next;
        pre.next = next;
        next.pre = pre;
    }

    public void put(int key, int value) {
        Node oldNode = data.get(key);
        // 判断节点key是否已存在
        if (oldNode != null) {
            // 删除旧节点
            deleteNode(oldNode);
        }
        // 新增节点
        Node node = new Node(key, value);
        data.put(key, node);
        // 新增节点 应该放在链表头部
        moveToHead(node);
        // 判断节点数是否到达容量
        resize();
    }
    public void resize() {
        if (data.size() > capacity) {
            // 去除链表末尾节点
            Node deleteNode = tail.pre;
            deleteNode.pre.next = tail;
            tail.pre = deleteNode.pre;
            data.remove(deleteNode.key);
        }
    }

}

复杂度分析:

• 时间复杂度：无论是get还是put操作都是$O(1)$
• 空间复杂度：则需要存储capacity个节点,所以为 $O(capacity)$