qrcode

马上订阅,开启修仙之旅

最常见面试算法之 LRU 缓存机制

一、题目描述

运用你所掌握的数据结构,设计和实现一个 LRU(最近最少使用)缓存机制。它应该支持以下操作:

  • 获取数据 get(key):如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
  • 写入数据 put(key, value) :如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作?

示例:

1
2
3
4
5
6
7
8
9
10
11
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

二、题解

LRU 是 Least Recently Used 的缩写,这种算法认为最近使用的数据是热门数据,下一次很大概率将会再次被使用。而最近很少被使用的数据,很大概率下一次不再用到。当缓存容量满的时候,优先淘汰最近很少使用的数据。

实现 LRU 缓存的常用方法是使用有界队列。实现 LRU 的关键是将所有最近使用的数据放在队列的开头。在每次插入之前,我们检查队列是否已满。如果队列已满,我们将删除其最后一个元素,并将新节点插入队列的开头。如果队列未满,我们只需将数据添加到队列的开头。

为了方便理解,我们借助前面的示例来演示一下上述的处理流程:

lru-cache-demo

当我们想要删除节点或更新节点时,我们需要快速找到该节点在队列中的位置。因此,可以使用 HashMap 支持快速查找操作。在这种情况下,get 操作的时间复杂度为 O(1)。

由于我们还需要有效地删除队列中间的节点,因此需要一个双向链表。在两种情况下,我们需要删除队列中间的节点:

  • 客户端指定需要删除一个节点。
  • 节点已更新,需要将其删除并插入队列的开头。

通过使用双向链表,一旦我们通过 HashMap 定位了要删除的节点的位置,就可以在 O(1) 时间从队列中删除该节点。

当我们需要更新键的缓存时,我们首先使用 HashMap 定位相应的节点,更新值,然后从队列中删除该节点,并将该节点放置在 Doubly Linked List 的开头。

lru-doubly-linked-list

LRU 算法 Java 实现

下面我们先用 Java 来实现 LRU 缓存算法。

首先定义个双向链表的节点:

1
2
3
4
5
6
7
8
9
10
11
class Node {
int key;
int value;
Node pre;
Node next;

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

每次执行操作时,我们都使用 HashMap 定位节点在队列中的位置,然后删除该节点并将其插入链表头。因此最好定义两个方法:

  • remove(node):从双向链表中删除指定 node 节点;
  • setHead(node):把指定 node 节点插入到双向链表表头。

定义 LRUCache 类

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
public class LRUCache {
int capacity;
Map<Integer, Node> map = new HashMap<>();
Node head = null;
Node tail = null;

public LRUCache(int capacity) {
this.capacity = capacity;
}

/**
* 根据指定key查找其对应的值
*
* @param key
* @return
*/
public int get(int key) {
if (map.containsKey(key)) {
Node node = map.get(key);
remove(node);
setHead(node);
return node.value;
}
return -1;
}

/**
* 移除指定n节点
*
* @param n
*/
public void remove(Node n) {
if (n.pre != null) { // 非头节点
n.pre.next = n.next;
} else { // 头节点
head = n.next;
}
if (n.next != null) { // 非尾节点
n.next.pre = n.pre;
} else { // 尾节点
tail = n.pre;
}
}

/**
* 设置双向链表的头节点
*
* @param n
*/
public void setHead(Node n) {
n.next = head;
n.pre = null;
if (head != null)
head.pre = n;
head = n;
if (tail == null)
tail = head;
}

/**
* 把指定key和value添加到缓存中
*
* @param key
* @param value
*/
public void put(int key, int value) {
// key对应的节点已存在,先更新节点值,然后将其删除并插入到链表头
if (map.containsKey(key)) {
Node old = map.get(key);
old.value = value;
remove(old);
setHead(old);
} else {
// 基于key和value创建新的节点
Node created = new Node(key, value);
// 若链表已满,则先移除链表尾元素,然后再把新元素添加到链表头
if (map.size() >= capacity) {
map.remove(tail.key);
remove(tail);
setHead(created);
} else {
setHead(created);
}
map.put(key, created);
}
}
}

定义 LRUCacheDemo 测试类

1
2
3
4
5
6
7
8
9
10
11
12
public class LRUCacheDemo {
public static void main(String[] args) {
LRUCache cache = new LRUCache(2);

cache.put(1, 1);
cache.put(2, 2);
System.out.println("cache.get(1): " + cache.get(1));
cache.put(3, 3);
System.out.println("cache.get(2): " + cache.get(2));
System.out.println("cache.get(3): " + cache.get(3));
}
}

以上代码成功运行后,输出以下结果:

1
2
3
cache.get(1): 1
cache.get(2): -1
cache.get(3): 3

三、参考资源


欢迎小伙伴们订阅前端全栈修仙之路,及时阅读 Angular、TypeScript、Node.js/Java和Spring技术栈最新文章。

qrcode