【Leetcode Top 100】146. LRU 缓存

问题背景

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

• LRUCache(int capacity) 以 正整数 作为容量 c a p a c i t y capacity capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 k e y key key 存在于缓存中，则返回关键字的值，否则返回 − 1 -1 −1。
• void put(int key, int value) 如果关键字 k e y key key 已经存在，则变更其数据值 v a l u e value value；如果不存在，则向缓存中插入该组 k e y − v a l u e key - value key−value。如果插入操作导致关键字数量超过 c a p a c i t y capacity capacity，则应该 逐出 最久未使用的关键字。
  函数 get 和 put 必须以 O ( 1 ) O(1) O(1) 的平均时间复杂度运行。

数据约束

• 1 ≤ c a p a c i t y ≤ 3000 1 \le capacity \le 3000 1≤capacity≤3000
• 0 ≤ k e y ≤ 10000 0 \le key \le 10000 0≤key≤10000
• 0 ≤ v a l u e ≤ 1 0 5 0 \le value \le 10 ^ 5 0≤value≤105
• 最多调用 2 ≤ 1 0 5 2 \le 10 ^ 5 2≤105 次 get 和 put

解题过程

数据结构设计题，以积累记忆为主。
LRU 是一种典型的页面淘汰策略，显然增删改的操作频率是比较高的，这应该用链表处理。这样一来，加入新页面的操作可以看作在链表头部插入，淘汰旧页面的操作可以看作删除链表的尾节点。
为了方便找到链表的尾节点，可以选择实现一个头尾循环的双向链表结构，这样一来，统一的头节点 d u m m y dummy dummy 的前一个节点就是尾节点。注意区别于一般的循环链表，这里双向链表是强调头尾节点的，而一般的循环链表最大的特征就是无所谓头尾，给定任意一个节点即可遍历整个链表。
还有一个问题，如果某个数据项已经存在，要求更新它的值和频率，也就是要将它的值更改为给定的新值并把这个节点移动到链表头部。但是在链表中按值查找的时间复杂度是 O ( N ) O(N) O(N) 量级的，不符合题目要求。为此，需要再引入查询效率为 O ( 1 ) O(1) O(1) 的哈希表。
综合来看，所有操作的时间复杂度是 O ( 1 ) O(1) O(1)，需要 O ( m i n ( p u t , c a p a c i t y ) ) O(min(put, capacity)) O(min(put,capacity)) 的额外空间（可能出现记录的页面数量少，没有达到过 c a p a c i t y capacity capacity 的情况）。

具体实现

class LRUCache {

    // 自定义双向链表
    private static class ListNode {
        int key, value;
        ListNode pre, next;

        ListNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final ListNode dummy = new ListNode(0, 0);
    private final Map<Integer, ListNode> map = new HashMap<>();

    // 初始状态下头节点的前后指针指向自己
    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy.pre = dummy;
        dummy.next = dummy;
    }

    // 自己实现的方法一：双向链表的头插法
    private void pushFront(ListNode node) {
        node.pre = dummy; // 新节点的前驱是头节点
        node.next = dummy.next; // 新节点的后继是之前头节点的后继
        node.pre.next = node; // 新节点的前驱（就是头节点）的后继是新节点
        node.next.pre = node; // 新节点的后继的前驱是新节点
    }

    // 自己实现的方法二：双向链表中删除某个节点
    private void remove(ListNode node) {
        node.pre.next = node.next; // 当前节点前驱的后继是当前节点的后继
        node.next.pre = node.pre; // 当前节点后继的前驱是当前节点的前驱
    }

    // 自己实现的方法三：从哈希表中获取某个键对应的链表节点
    private ListNode getNode(int key) {
        // 该节点不存在则返回空
        if(!map.containsKey(key)) {
            return null;
        }
        // 存在则取出该节点，先删除，再从链表头部插入
        ListNode node = map.get(key);
        remove(node);
        pushFront(node);
        return node;
    }
    
    public void put(int key, int value) {
        // 根据相应的键取数据项，若存在则更新它的值
        ListNode node = getNode(key);
        if(node != null) {
            node.value = value;
            return;
        }
        // 若相应的数据项不存在，那么新建节点，更新哈希表并从链表头部插入
        node = new ListNode(key, value);
        map.put(key, node);
        pushFront(node);
        // 维护的页面数量超过规定值，进行淘汰
        if(map.size() > capacity) {
            // 头节点的前驱就是要淘汰的尾节点
            ListNode leastUsed = dummy.pre;
            // 从哈希表和链表中移除
            map.remove(leastUsed.key);
            remove(leastUsed);
        }
    }
        
    public int get(int key) {
        ListNode node = getNode(key);
        return node != null ? node.value : -1;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */