1. LRU 缓存

题目链接: https://leetcode.cn/problems/lru-cache/

---

1.1 LRU 算法描述

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

也就是说：我没认为最近使用过的数据是 有用的，而那些很久都没有使用过的数据是 无用的，在缓存容量不够的时候，就会删去 无用的数据，这样就可以为新加入的 有用的 数据提供空间。

题目要求：

首先需要接收一个 capacity 参数最为缓存的容量，然后实现put(key, val) 方法存入键值对、实现 get(key) 方法获取 key 对应的 val，如果 key 不存在则返回 -1。

注意：题目要求 get 函数和 put 函数的时间复杂度都是1。我们先来看看按照题目的意思大概的工作流程。

---

1.2 LRU 算法分析

题目要求 get 函数和 put 函数的时间复杂度都是1，这就指明了需要用的 Map（哈希表）去实现元素的存储和访问。

题目要求淘汰最久没有被使用的元素，说明元素之间是按照一定的顺序存储的。我们可以用双向链表来存储数据。每次访问 缓存 中的某个 key，需要将这个元素变为最近使用的，也就是说 缓存 要支持在任意位置快速插入和删除元素。双向链表也可以很好的满足这个需求（删除一个节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持直接查找前驱，保证操作的时间复杂度 O(1)）。

所以LRU缓存的结构是由 哈希表 和 双向链表构成的。

---

1.3 代码实现

完整的代码实现：

class LRUCache {
    private final Map<Integer, Node> cache;
    private final DoubleLikedTable doubleLikedTable;
    private final int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        doubleLikedTable = new DoubleLikedTable();
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            Node ans = cache.get(key);
            doubleLikedTable.delete(ans);
            doubleLikedTable.add(ans);
            return ans.value;
        }

        return -1;
    }

    public void put(int key, int value) {
        Node cur = cache.get(key);
        if (cur == null) {
            cur = new Node(key, value);
            if (doubleLikedTable.size >= capacity) {
                Node node = doubleLikedTable.deleteHead();
                cache.remove(node.key);
            }
        } else {
            cur.value = value;
            doubleLikedTable.delete(cur);
        }
        doubleLikedTable.add(cur);
        cache.put(key, cur);
    }

    // 链表头部的元素是最久没有使用的
    class DoubleLikedTable {
        Node head, tail;
        int size;

        public DoubleLikedTable() {
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.prev = head;
            size = 0;
        }

        // 1. 添加元素 (队尾添加元素)
        public void add(Node cur) {
            if (cur != null) {
                cur.next = tail;
                cur.prev = tail.prev;
                tail.prev.next = cur;
                tail.prev = cur;
                size++;
            }
        }

        // 2. 删除元素
        public void delete(Node cur) {
            if (cur != null) {
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
                size--;
            }
        }

        // 3. 删除队首的元素
        public Node deleteHead() {
            Node headEle = head.next;
            delete(head.next);
            return headEle;
        }

        // 3. 返回长度
        public int getSize() {
            return size;
        }


    }

    class Node {
        public int key, value;
        public Node next, prev;

        public Node() {
        }

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

力扣运行结果：

实现分析：

首先是双向链表的结点类：这里没有用 private 和 geter/seter 封装代码是为了简化代码。

    class Node {
        public int key, value;
        // next 指向下一个结点，prev指向上一个结点
        public Node next, prev;

        public Node() {
        }

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

下面是双向链表的实现类：首先定义2个空结点 head、tail。head的next指向头结点，tail的prev指向尾结点。

    // 链表头部的元素是最久没有使用的
    class DoubleLikedTable {
        Node head, tail;
        int size;

        public DoubleLikedTable() {
            head = new Node();
            tail = new Node();
            // head的next指向头结点，tail的prev指向尾结点。
            head.next = tail;
            tail.prev = head;
            // 初始化链表的长度为0
            size = 0;
        }

        // 1. 添加元素 (队尾添加元素)
        public void add(Node cur) {   
                cur.next = tail;
                cur.prev = tail.prev;
                tail.prev.next = cur;
                tail.prev = cur;
                size++;
        }

        // 2. 删除元素
        public void delete(Node cur) {
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
                cur.next = null;
                cur.prev = null;
                size--;
        }

        // 3. 删除队首的元素，并返回被删除的元素
        public Node deleteHead() {
        	// head.next 指向的就是队首的元素
            Node headEle = head.next;
            delete(head.next);
            return headEle;
        }

        // 3. 返回长度
        public int getSize() {
            return size;
        }
    }
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

1. 添加元素 (队尾添加元素)

        // 1. 添加元素 (队尾添加元素)
        public void add(Node cur) {   
                cur.next = tail;
                cur.prev = tail.prev;
                tail.prev.next = cur;
                tail.prev = cur;
                size++;
        }
1
2
3
4
5
6
7
8

2. 删除元素

        // 2. 删除元素
        public void delete(Node cur) {
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
                cur.next = null;
                cur.prev = null;
                size--;
        }
1
2
3
4
5
6
7
8

3. 初始化缓存

class LRUCache {
    private final Map<Integer, Node> cache;
    private final DoubleLikedTable doubleLikedTable;
    private final int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        doubleLikedTable = new DoubleLikedTable();
    }
}
1
2
3
4
5
6
7
8
9
10
11

4. 实现 get 方法

• 如果缓存里面不存在指定的元素，返回 -1。
• 如果缓存里面存在指定的元素，先在链表里面删去该元素，然后再次添加（保证刚刚访问的元素在链表的末尾），然后返回结果即可。

    public int get(int key) {
        if (cache.containsKey(key)) {
            Node ans = cache.get(key);
            doubleLikedTable.delete(ans);
            doubleLikedTable.add(ans);
            return ans.value;
        }
		
        return -1;
    }
1
2
3
4
5
6
7
8
9
10

5. 实现 put 方法

• 如果缓存里面不存在该元素cur == null)， 则新建一个结点。如果链表长度超过缓存容量，则删去链表的头结点，并从缓存中删除刚刚删去的头结点相关的数据。
• 如果缓存里面存在该元素，则更新缓存的值，并把新加的结点放在链表的尾部（doubleLikedTable.delete(cur); doubleLikedTable.add(cur);）

    public void put(int key, int value) {
        Node cur = cache.get(key);
        if (cur == null) {
            cur = new Node(key, value);
            if (doubleLikedTable.size >= capacity) {
                Node node = doubleLikedTable.deleteHead();
                cache.remove(node.key);
            }
        } else {
            cur.value = value;
            doubleLikedTable.delete(cur);
        }
        doubleLikedTable.add(cur);
        cache.put(key, cur);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

---