文章

09.其他

发表于 更新于
作者 Hacket Zeng
12 分钟阅读
09.其他

哈希表

排序

手写系列

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) 的平均时间复杂度运行。

单链表解法

  1. 用单链表来存储节点；引入哑元节点
  2. put(key, value) 方法
    1. 首先根据 key 查找链表是否存在该元素，如果存在，先删除，然后返回该元素，将新的 value 替换旧的 val，再插入到头节点去
    2. 如果链表不存在该节点，那么看 size 是否超过了 capacity
    3. size 未超过 capacity，插入一个新的节点到头节点，size 加 1
    4. size 超过了 capacity，将尾节点删除，再插入一个新的节点 (key 和 val) 到头节点去
  3. get(key) 先根据 key 去查找是否存在 key 的节点，如果存在就删除并返回，然后插入到头节点去；如果不存在，返回 -1
  4. get 和 put 都是 O(n) 的时间复杂度，最差的情况需要遍历整个链表
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

public class LRUCache {
    // 用链表存储
    private final ListNode dummyNode;
    private final int capacity;
    private int size;
    public LRUCache(int capacity) {
        dummyNode = new ListNode(0);
        this.capacity = capacity;
    }
    public int getSize() {
        return size;
    }
    public int get(int key) {
        ListNode oldNode = deleteNode(key);
        if (oldNode != null) {
            insertHeadNode(oldNode);
            return oldNode.val;
        }
        return -1;
    }
    public void put(int key, int value) {
        // 先看是否存在key
        ListNode oldNode = deleteNode(key);
        if (oldNode != null) { // 存在key，直接替换
            oldNode.val = value;
            insertHeadNode(oldNode);
            return;
        }
        if (size < capacity) { // 容量未满，放在最前面
            // 容量未满&key不存在，插入新的到头节点
            ListNode newNode = new ListNode(value);
            newNode.key = key;
            insertHeadNode(newNode);
            size++;
        } else { // 容量已满
            // 丢弃最久未使用的（最后一个），将元素插入到最前面
            // 找到最后一个节点前一个节点
            ListNode lastPreNode = getLastPreNode();
            ListNode last = lastPreNode.next;
            lastPreNode.next = null;
            last.next = null;
            // 新建一个节点插入到头节点
            ListNode newNode = new ListNode(value);
            newNode.key = key;
            insertHeadNode(newNode);
        }
    }
    private ListNode getLastPreNode() {
        ListNode cur = dummyNode;
        ListNode pre = null;
        while (cur.next != null) {
            pre = cur;
            cur = cur.next;
        }
        return pre;
    }
    /**
     * 插入节点到头节点
     */
    private void insertHeadNode(ListNode n) {
        ListNode next = dummyNode.next;
        dummyNode.next = n;
        n.next = next;
    }
    /**
     * 删除某个key对应的ListNode并返回就ListNode
     */
    private ListNode deleteNode(int key) {
        ListNode pre = dummyNode;
        ListNode cur = dummyNode.next;
        while (cur != null) {
            if (cur.key == key) {
                // 删除cur
                pre.next = cur.next;
                cur.next = null;
                return cur;
            }
            pre = cur;
            cur = cur.next;
        }
        return null;
    }
}

public class ListNode {

    public int val;
    public int key;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

不足

  1. get 和 put 的时间复杂度都是 O(N)
  2. 根据 key 找到某个节点时每次都需要遍历整个链表来找到目标节点，时间复杂度为 O(1)
  3. 删除某个节点也是需要遍历整个链表的，时间复杂度也是 O(1)

哈希表 + 双向链表 (推荐)

算法就像搭乐高：带你手撸 LRU 算法
LRU 算法设计

  1. LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体

哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表 LinkedHashMap。

  1. 双向链表的目的是删除节点时需要找到该节点的前驱节点，否则就需要遍历链表得到前驱节点，不能保证 O(1) 时间复杂度
  2. 哈希表用来根据 key 定位节点，保证在 O(1) 的时间复杂度找到某个 key 对应的节点

image.png
代码实现

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

public class Node {
    public int key, val;
    public Node next, prev;
    public Node(int k, int v) {
        this.key = k;
        this.val = v;
    }
}
public class DoubleList {
    // 头、尾节点
    private Node head;
    private Node tail;
    // 大小
    private int size;
    public DoubleList() {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.prev = null;
        head.next = tail;
        tail.prev = head;
        tail.next = null;
        size = 0;
    }
    // 在链表尾部添加节点 x，时间 O(1)
    public void addLast(Node x) {
        // node→tail→null
        // node→x→tail→null
        x.prev = tail.prev;
        x.next = tail;
        tail.prev.next = x;
        tail.prev = x;
        size++;
    }
    // 删除链表中的 x 节点（x 一定存在）
    // 由于是双链表且给的是目标 Node 节点，时间 O(1)
    public void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
        x.prev = null;
        x.next = null;
        size--;
    }
    // 删除链表中第一个节点，并返回该节点，时间 O(1)
    public Node removeFirst() {
        if (head.next == tail) { // 当前没有节点
            return null;
        }
        Node n = head.next;
        remove(n);
//        Node n = head.next;
//        head.next = n.next;
//        n.next.prev = head;
//        n.next = null;
//        n.prev = null;
        return n;
    }
    // 返回链表长度，时间 O(1)
    public int size() {
        return size;
    }
}
public class LRUCache {
    // key -> Node(key, val)
    private HashMap<Integer, Node> map;
    // Node(k1, v1) <-> Node(k2, v2)...
    private DoubleList cache;
    // 最大容量
    private int cap;
    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        // 将该数据提升为最近使用的
        makeRecently(key);
        return map.get(key).val;
    }
    public void put(int key, int val) {
        if (map.containsKey(key)) {
            // 删除旧的数据
            deleteKey(key);
            // 新插入的数据为最近使用的数据
            addRecently(key, val);
            return;
        }
        if (cap == cache.size()) {
            // 删除最久未使用的元素
            removeLeastRecently();
        }
        // 添加为最近使用的元素
        addRecently(key, val);
    }
    //* 将某个 key 提升为最近使用的 */
    private void makeRecently(int key) {
        Node x = map.get(key);
        // 先从链表中删除这个节点
        cache.remove(x);
        // 重新插到队尾
        cache.addLast(x);
    }
    /* 添加最近使用的元素 */
    private void addRecently(int key, int val) {
        Node x = new Node(key, val);
        // 链表尾部就是最近使用的元素
        cache.addLast(x);
        // 别忘了在 map 中添加 key 的映射
        map.put(key, x);
    }
    /* 删除某一个 key */
    private void deleteKey(int key) {
        Node x = map.get(key);
        // 从链表中删除
        cache.remove(x);
        // 从 map 中删除
        map.remove(key);
    }
    /* 删除最久未使用的元素 */
    private void removeLeastRecently() {
        // 链表头部的第一个元素就是最久未使用的
        Node deletedNode = cache.removeFirst();
        // 同时别忘了从 map 中删除它的 key
        int deletedKey = deletedNode.key;
        map.remove(deletedKey);
    }
}
  • 时间复杂度：get 和 put 的时间复杂度都是 O(1)

LinkedHashMap 解法

用 Java 的内置类型 LinkedHashMap 来实现 LRU 算法

思路

  1. 一个 LinkedHashMap 变量 cache(头部最近最少使用，尾部最近使用)，一个 capacity 最大容量 capacity
  2. get(key) 方法
    1. 判断 cache 是否存在 key，如果不存在返回 -1
    2. 如果 cache 中存在，将改 key 对应的节点更新为最近使用 (先删除，再将节点添加到尾部)
  3. put(key, val) 方法
    1. 判断 cache 中是否存在 key，如果存在，就更新 val，更新为最近使用
    2. 如果 cache 中不存在，再判断是否小于 capacity，是就添加到尾部；如果不小于 capacity，那么需要将头节点删除，再将该节点添加到尾节点去

代码

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

public class LRUCache {
    private LinkedHashMap<Integer, Integer> cache;
    private int capacity;
    public LRUCache(int capacity) {
        this.cache = new LinkedHashMap<>();
        this.capacity = capacity;
    }
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        // 将 key 变为最近使用
        makeRecently(key);
        return cache.get(key);
    }
    public void put(int key, int val) {
        if (cache.containsKey(key)) {
            // 修改 key 的值
            cache.put(key, val);
            // 将 key 变为最近使用
            makeRecently(key);
            return;
        }
        if (cache.size() >= this.capacity) {
            // 链表头部就是最久未使用的 key
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        // 将新的 key 添加链表尾部
        cache.put(key, val);
    }
    // 将key标记为最近使用
    private void makeRecently(int key) {
        Integer val = cache.get(key);
        if (val == null) {
            return;
        }
        cache.remove(key);
        cache.put(key, val);
    }
}
数据结构和算法, 基础
本文由作者按照 CC BY 4.0 进行授权