0%

从Leetcode的一道LRU算法题说起

在刷Leetcode遇见一道LRU相关的题,原题如下

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

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

进阶:

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

那么什么是LRU呢?LRU是Least recently used的所写,中文意思是最近最少使用,学过操作系统的同学可能对LRU有些印象,常用于页面置换算法。简单来说,根据数据的历史访问记录来进行淘汰数据,如果一个数据被访问到,那么下次被访问的几率比较高;如果长时间不被访问,就面临着被淘汰的危险。结合上面的算法题,我们可以分析到,假设数据是被存储在队列中的,那么每次访问一个元素,都将其移动到队列的头结点,当队列满时(通常有一个最大容量),移除队列尾部的元素。

了解了LRU的基本概念,那么我们该用什么结构去表示数据命中没命中呢?如果限制在O(1) 时间复杂度来完成命中操作的话,我们就首选不能出现遍历了。学过数据结构的都知道哈希表的查找时间复杂度为 O(1) ,所以我们可以哈希表来表示数据什么时候命中了(key 和 value),用一个队列存储数据的key。

get方法流程:

  1. 判断key在哈希表中是否命中
    1. 如果命中,将队列中的key移动到队首,返回哈希表中key对应的value;
    2. 如果没有,直接返回-1

put方法流程:

  1. 判断key在哈希表中是否命中
    1. 如果命中,代表更新,将队列中的key移动到队首
    2. 如果没有,在队首添加新元素
  2. 更新或者新增该key-value到哈希表
  3. 检测队列容量,如果容量超过最大限制,移除队列最后一个元素

好了,实现就不说了,代码如下,都是现成的:

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
package me.mingshan.algorithm.lru;


import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;

/**
* @author mingshan
*/
public class LRUCache {
private static final int DEFAULT_CAPACITY = 16;

private final Map<Integer, Integer> map;
private final LinkedList<Integer> queue;

private final int capacity;

public LRUCache() {
this(DEFAULT_CAPACITY);
}

public LRUCache(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("capacity <= 0");
}
this.map = new LinkedHashMap<>();
this.queue = new LinkedList<>();
this.capacity = capacity;
}

public void put(int key, int value) {
// 首先判断当前数据是否存在
if (!map.containsKey(key)) {
queue.addFirst(key);
} else {
// 如果是修改,则需要将其移动到头部
moveToHead(key);
}

map.put(key, value);
// 如果不存在,首先判断队列中是否已经满了
if (queue.size() > capacity) {
// 移除队列中最后一个结点
map.remove(queue.removeLast());
}
}

public int get(int key) {
if (map.containsKey(key)) {
// 如果是修改,则需要将其移动到头部
int value = map.get(key);
moveToHead(key);
return value;
} else {
return -1;
}
}

private void moveToHead(int key) {
queue.remove(Integer.valueOf(key));
queue.addFirst(Integer.valueOf(key));
}
}

后面准备写一个通用的实现,先挖个坑~

References: