用Java实现简单LRU缓存

操作系统中存在虚拟内存的概念,每个进程都会分配到类似4G这样的内存大小,

但其实物理内存只有4G的大小,所以进程分配到的并不是实际的大小,所以叫他虚拟内存。

虚拟内存用页表进行管理,当进程需要的页不在内存中会发生缺页中断,

将需要的页面调入内存中,如果此时内存又满了,自然就会有之前的页被淘汰出去,

至于淘汰的是哪一个页,这就是页面置换算法所负责的了。

常见的页面置换算法有:

  • OPT置换算法(理想置换算法)
  • FIFO置换算法(先进先出置换算法)
  • LRU置换算法(最近最久未被使用置换算法)
  • CLOCK置换算法(时钟置换算法,又称NRU最近未用置换算法)

具体的算法细节可以分别百度,这里就说下LRU吧。

LRU基本思想就是一个页面如果最近很少使用,那么他在将来也会很少被使用,所以最近的最少使用的缓存会被置换出去。

我们用Java数据结构如何模拟呢?

缓存容器很容易可以想到用Map来存储,Map的size到达阈值后就把相应的数据remove掉。

那怎么获取Map中最近最久不被访问的数据呢?

可以给每个缓存加个时间戳,put数据进去的时候记录当前时间戳,然后get数据的时候再更新成当前时间,

put没有空闲空间时执行淘汰策略,就是找到时间戳离当前最久的数据,把他淘汰。

但是要找到这个最久的时间戳不容易,最差需要O(N)的时间复杂度。

所以这里用Map+链表的方式可以很巧妙的实现这个需求。

Map和链表之间互不影响,Map维护他key-value的数据结构,保证取数据时常数级别的时间复杂度,链表维护缓存的优先级,新数据put到链表的头部,get操作时也会把get到的节点移动到链表头部,这样当空间不足时只需要把链表的尾部淘汰掉就ok了,而且链表节点的移动删除都是O(1)级别的,不会有性能上的不足。

其实JDK自带的LinkedHashMap数据结构很好的实现了上述,不过他是个大家伙,下面就自己实现一个简单一点的。

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
import java.util.HashMap;
import java.util.Map;

class LRUNode {
public String key;
public String value;
public LRUNode pre;
public LRUNode next;

public LRUNode(String key, String value) {
this.key = key;
this.value = value;
}
}

class LRUCache {
private Map<String, LRUNode> cache = new HashMap<>();
private int capacity;
private LRUNode head;
private LRUNode tail;

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

public void put(String key, String value) {
LRUNode node = cache.get(key);
if (node != null) {
node.value = value;
removeNode(node);
} else {
node = new LRUNode(key, value);
if (cache.size() >= capacity) {
cache.remove(tail.key);
removeNode(tail);
}
cache.put(key, node);
}
setHead(node);
}

public String get(String key) {
if (cache.containsKey(key)) {
LRUNode node = cache.get(key);
removeNode(node);
setHead(node);
return node.value;
}
return null;
}

@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append('[');
LRUNode node = head;
while (node != null) {
str.append("{" + node.key + "," + node.value + "}");
if (node.next != null) {
str.append(" -> ");
}
node = node.next;
}
str.append(']');
return str.toString();
}

private void setHead(LRUNode node) {
if (head != null) {
node.next = head;
head.pre = node;
}
node.pre = null;
head = node;
if (tail == null) {
tail = node;
}
}

private void removeNode(LRUNode node) {
// 如果是头结点
if (node.pre == null) {
head = node.next;
} else {
// 普通节点next指针处理
node.pre.next = node.next;
}
// 如果是尾节点
if (node.next == null) {
tail = node.pre;
} else {
// 普通节点pre指针处理
node.next.pre = node.pre;
}
// 释放node
node.pre = null;
node.next = null;
}
}

下面再写个main方法测试一下效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Main {

public static void main(String args[]) {
LRUCache cache = new LRUCache(5);
cache.put("1号", "01");
System.out.println(cache.toString());
cache.put("2号", "02");
System.out.println(cache.toString());
cache.put("3号", "03");
System.out.println(cache.toString());
cache.put("4号", "04");
System.out.println(cache.toString());
cache.put("5号", "05");
System.out.println(cache.toString());
cache.put("6号", "06");
System.out.println(cache.toString());
cache.get("2号");
System.out.println(cache.toString());
cache.put("7号", "07");
System.out.println(cache.toString());
}
}

输出:

[{1号,01}]
[{2号,02} -> {1号,01}]
[{3号,03} -> {2号,02} -> {1号,01}]
[{4号,04} -> {3号,03} -> {2号,02} -> {1号,01}]
[{5号,05} -> {4号,04} -> {3号,03} -> {2号,02} -> {1号,01}]
[{6号,06} -> {5号,05} -> {4号,04} -> {3号,03} -> {2号,02}]
[{2号,02} -> {6号,06} -> {5号,05} -> {4号,04} -> {3号,03}]
[{7号,07} -> {2号,02} -> {6号,06} -> {5号,05} -> {4号,04}]

可以看到第一次页面置换时把1号缓存置换出去了,然后正常情况下次应该把2号给置换出去,但是我在下次put之前进行了get(“2号”)的操作,相当于使用了一次2号缓存,所以看到2号被提到了链表最前边,这样下次put其实是把3号给置换了出去。

文章作者: Qug_
文章链接: https://www.qugcloud.cn/2019/04/01/system-lru/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Qug's Blog