通关剑指 Offer——剑指 Offer II 031. 最近最少使用缓存

1.题目描述

剑指 Offer II 031. 最近最少使用缓存

运用所掌握的数据结构，设计和实现一个 LRU (Least Recently Used，最近最少使用) 缓存机制 。

实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

示例：

输入
["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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.解题思路与代码

2.1 解题思路

这是一道很经典的面试题目。要构建一个 LRU 的缓存，那么就需要考虑到缓存的存储、读取和更新。从题目要求看出，该 LRU 缓存有以下几个特点：

• 设置了最大容量，添加缓存时如果没有超过最大容量，则被插入的缓存项应该是最活跃的缓存；超过容量就需要删除最不常用的缓存，并且将要插入的项加入到缓存中设置为最活跃
• 获取缓存时如果查询的缓存不存在则返回 -1；如果缓存存在，则返回缓存值，并将缓存设置为最活跃

既然是键值对缓存，那么我们就需要使用到哈希表这样的数据就够来进行存放。确定使用哈希表这种结构存放缓存之后，就需要解决缓存活跃度排序的问题了。既然我们要不断刷新缓存的活跃度，并且每取出一次就要让当前缓存变为最活跃的，那么就可以考虑使用链表结构，因为链表结构的添加和删除操作是 O(1) 的。使用链表我们就可以将最活跃的缓存项放在链表头节点，然后让最不活跃的放在链表尾节点，这样就能将将哈希表中的缓存通过链表结构将各个缓存项串起来了。那么使用单向链表能否完成呢？其实单向链表也是能够完成的，但是再维护缓存链表的时候我们需要插入头节点以及当缓存满了的时候删除尾节点，如果使用单向链表，这个删除的的过程就需要遍历整个链表以及维护待删除节点的前一个节点，效率过低，因此使用双向链表来完成，也就是整个 LRU 缓存使用哈希表+双向链表的结构。

首先我们需要自己构建一个双向链表 MyLinkedList，链表节点中包含上一个节点 prev 、下一个节点 next以及该节点存放的缓存的键 key、值 value。

static class MyLinkedList {
    MyLinkedList prev;
    MyLinkedList next;
    int val;
    int key;

    public MyLinkedList(int key, int val) {
        this.key = key;
        this.val = val;
    }
}
1
2
3
4
5
6
7
8
9
10
11

我们在 LRUCache 的构造方法中对整个缓存进行初始化。我们首先创建一个 HashMap 作为数据缓存，同时构建一个虚拟的头节点 head 和尾节点 tail 这样便于后面的首位节点的添加和删除操作，让两个虚拟头尾节点连接起来，并在 LRUCache 内部对头和尾进行维护。因此我们实际的头节点是 tail.next，实际的尾节点是 tail.prev。

class LRUCache {
    MyLinkedList head;
    MyLinkedList tail;
    int capacity;
    Map<Integer, MyLinkedList> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new MyLinkedList(-1, -1);
        tail = new MyLinkedList(-1, -1);
        head.next = tail;
        tail.prev = head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

接下来分析 get 和 put 两个方法。首先看 get 方法，题目要求如果缓存不存在则返回 -1，缓存如果存在就返回缓存值。此时如果缓存存在的话便说明该缓存被使用了，需要将缓存放到头节点位置表示该节点最近活跃了。这就需要两步操作：删除当前节点，并将节点插入到头节点。我们记录获取的节点为 node，删除当前节点就直接让 node.prev 节点的 next 指向 node.next， node.next 的 prev 节点指向 node.prev 即可。将 node 插入到头位置也非常简单，让 head.next 指向 node、node.next 指向原来 head.next节点同时连接三个节点的 prev。比如下图所示，我们当前要将 (2, 1) 这个缓存移动到头节点位置，就需要下面两图的操作。

put 方法相较于 get 方法就复杂一点，首先我们需要判断需要放入的 key 是否存在，如果存在就只需要更新该 node 的 value 值，并将该节点移动到量表头。流程如下所示，原来缓存中存在 (2, 1) 这时 put(2, 3) 到缓存中首先我们更新 node 值为 (2, 3)，并且将该节点移动到链表头部。

如果 key 不存在那么我们就要判断当前缓存是否达到最大容量，如果没有达到最大容量则将需要插入的节点插入到链表头即可，如果达到了最大容量，那么要在插入头节点之前先将队尾节点删除以腾出位置。根据 put 和 get 操作的描述，我们需要两个独立的方法：删除节点和添加头节点，代码如下：

private void delete(MyLinkedList node) {
    MyLinkedList next = node.next;
    node.prev.next = next;
    next.prev = node.prev;

}

private void addHead(MyLinkedList node) {
    MyLinkedList next = head.next;
    head.next = node;
    node.next = next;
    next.prev = node;
    node.prev = head;
    map.put(node.key, node);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

那么按照上面的对 put 流程的描述，整个 put 方法的代码如下：

public void put(int key, int value) {
    if (map.containsKey(key)) {
        MyLinkedList node = map.get(key);
        node.val = value;
        // 删除节点 node
        delete(node);
        // node 添加至头节点
        addHead(node);
    } else {
        MyLinkedList node = new MyLinkedList(key, value);
        if (map.size() == capacity) {
            MyLinkedList prev = tail.prev.prev;
            map.remove(prev.next.key);
            // 删除尾节点
            prev.next = tail;
            tail.prev = prev;
        }
        // node 添加到头节点
        addHead(node);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.2 代码

class LRUCache {
    MyLinkedList head;
    MyLinkedList tail;
    int capacity;
    Map<Integer, MyLinkedList> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new MyLinkedList(-1, -1);
        tail = new MyLinkedList(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        MyLinkedList node = map.get(key);
        // 删除节点 node
        delete(node);

        // node 添加至头节点
        addHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            MyLinkedList node = map.get(key);
            node.val = value;
            // 删除节点 node
            delete(node);
            // node 添加至头节点
            addHead(node);
        } else {
            MyLinkedList node = new MyLinkedList(key, value);
            if (map.size() == capacity) {
                MyLinkedList prev = tail.prev.prev;
                map.remove(prev.next.key);
                // 删除尾节点
                prev.next = tail;
                tail.prev = prev;
            }
            // node 添加到头节点
            addHead(node);
        }
    }

    private void delete(MyLinkedList node) {
        MyLinkedList next = node.next;
        node.prev.next = next;
        next.prev = node.prev;

    }

    private void addHead(MyLinkedList node) {
        MyLinkedList next = head.next;
        head.next = node;
        node.next = next;
        next.prev = node;
        node.prev = head;
        map.put(node.key, node);
    }

    static class MyLinkedList {
        MyLinkedList prev;
        MyLinkedList next;
        int val;
        int key;

        public MyLinkedList(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

2.3 测试结果

通过测试

3.总结

• 使用哈希表加双向链表完成
• 在维护哈希表缓存的时候需要对链表进行更新，主要包括删除节点和插入头节点两个方法